Regular Syndrome Decoding Is Easier Than Previously Estimated

1 Introduction

• RSD requires exactly one nonzero coordinate per prescribed block, a structure that enables more efficient cryptographic constructions than unstructured decoding.RSD and related regular-noise assumptions underlie PCGs, VOLE protocols, zero-knowledge systems, MPC frameworks, and MPC-in-the-Head signatures.Source: §1 · p. 2

1.1 Algebraic attacks on the RSD problem

• Algebraic attacks can outperform ISD in some low-rate regimes by encoding within-block regularity as quadratic equations x_i x_j = 0 alongside the syndrome equation.Hybrid attacks guess support information, eliminate variables using syndrome equations, then solve the reduced polynomial system; the placement of guesses and eliminations across blocks matters.Source: §1.1 · p. 3

1.2 Our contribution

• The attack coordinates zero guessing, syndrome-based elimination, preprocessing, and algebraic solving as coupled blockwise operations rather than optimizing them separately.This approach addresses an avoidable imbalance in the placement of these operations across regular blocks.Source: §1.2 · p. 3, A globally balanced guess–reduce–solve… · p. 4

The source of the previous complexity loss

• Concentrating zero guesses within a block can incur a larger guessing penalty, and Wang et al.’s unbalanced guesses and eliminations amplify that loss.A zero guess also removes quadratic equations from its block, so the attack balances guess success probability against the equations retained for solving.Source: The source of the previous complexity… · pp. 3–4

A globally balanced guess–reduce–solve technique

• Balancing the pipeline across blocks improves overall success probability while retaining enough equations for linearization.The method balances syndrome eliminations to preserve more uniformly sized candidate sets for subsequent guesses; AM–GM underlies its probability analysis.Source: A globally balanced guess–reduce–solve… · p. 4
• The paper also tightens preprocessing-cost estimates and uses fewer excess equations to reject incorrect guesses in the final overdetermined system.These refinements complement blockwise balancing by reducing the estimated algebraic cost of processing each resulting system.Source: A globally balanced guess–reduce–solve… · p. 4

Concrete security consequences

• Across seven applications, estimated security losses reach 66 bits; none of the refined 128-bit parameter sets of [20] achieves its claimed level.For [20], estimated losses range from 27 to 47 bits over non-binary fields and 17 to 48 bits over binary fields.Source: Concrete security consequences · p. 5
• Up to 29 bits over non-binary fields and 25 bits over binary fields, the refined attack lowers previous best benchmark costs and is best on 12 of 14 binary parameters.For benchmark instances from [7, 20], it has the lowest estimated complexity except in two binary cases; R-ISD was previously best on 10 of 14 binary parameters.Source: Concrete security consequences · p. 5

2.1 Notation

• The notation uses F_q for a finite field, bold uppercase and lowercase for matrices and vectors, and x_I and A_I for coordinates and columns indexed by I.Vectors are column vectors; |x| denotes Hamming weight, and [a] denotes {1,…,a}.Source: §2.1 · p. 7

2.2 The regular syndrome decoding problem

• RSD(n,k,h) asks for x partitioned into h blocks of length n/h, each with Hamming weight 1, such that Hx=s; q=2 is binary RSD.The blocks satisfy x_i ∈ F_q^(n/h) for i ∈ [h].Source: §2.2 · p. 8
• Plain SD(n,k,h) seeks a weight-h solution to Hx=s and is NP-complete; a security reduction relates SD to RSD [13, Theorem 1].When the error rate is sufficiently small, RSD difficulty can be guaranteed by SD difficulty; with low code rate too, instances are vulnerable to RSD-specific attacks.Source: §2.2 · p. 8

Gaussian elimination

• Algebraic-attack costs depend on Gaussian elimination: standard elimination costs O(m·N·min{m,N}), while Strassen costs O(max{m,N}^cmm) with cmm≈2.8.When m is sufficiently larger than q, striped elimination costs O(m²/log_q m) row operations and O(m²N/log_q m) total, and is useful over F2. The analysis excludes cmm=2.3713 because of huge hidden constants, consistently with prior RSD work.Source: Gaussian elimination · p. 8

Invertibility of random matrices

• For fixed q, random m×m matrix invertibility probability approaches a limit as m grows, and that limit increases with q: 0.2889 at q=2, 0.5605 at q=3, and 0.9170 at q=13.Source: Invertibility of random matrices · p. 9

Overdetermined linear system

• Setting m−N≥ξ(N) makes a random matrix full-rank with overwhelming probability and bounds the expected number of solutions for random b by q^-ξ(N).If the matrix is full-rank, there is at most one solution; for q=2^128, the text takes ξ(N)=c_excess for a constant c_excess.Source: Overdetermined linear system · p. 9

3.1 Overview

• The attack tightens its concrete cost estimate by identifying preprocessing operations that are essentially negligible, without changing the preprocessing algorithm.This refined accounting contributes to the improved concrete complexity alongside balanced blockwise allocation.Source: §3.1 · p. 11

3.2 Balanced strategy for guessing and eliminating variables

• Balancing zero guesses and syndrome-based variable eliminations so that removals differ by at most one per block improves aggregate guessing probability without sacrificing equations for the algebraic solve.The overview explains that even distribution is favorable for minimizing total guessing cost by the AM–GM inequality.Source: §3.1 · p. 10, §3.2 · p. 11

Distributing linear equations.

• For non-binary fields, the n − k syndrome equations are distributed across h blocks with each block assigned either ⌊(n − k)/h⌋ or one more eliminated variable.This distributes the linear eliminations as evenly as possible when the number of equations is not divisible by the number of blocks.Source: §3.2 · p. 11, Distributing linear equations · p. 12

3.3 Refined attack procedure

• The procedure uses outer first-stage zero-guess trials, preprocesses each resulting system once, then reuses that preprocessing across inner second-stage guesses.A candidate system is solved by linearization when it has at least as many equations as monomials; candidate solutions are verified against the original RSD instance.Source: §3.1 · p. 10, Step 1. First stage of zero guessing · pp. 14–15, Step 2. Preprocessing via Gaussian… · pp. 16–17

Step 3. Second stage of zero guessing

• Incorrect second-stage zero guesses make the resulting system inconsistent with overwhelming probability, an assumption supported by experiments.The proposed intuition is that an incorrect guess removes the true error-support structure, leaving a random overdetermined system.Source: Step 3. Second stage of zero guessing · p. 18

3.4 Complexity analysis

• The nested guessing strategy incurs separate repetition factors: p^-η1 for first-stage preprocessing and p^-η for second-stage trials.Preprocessing is reused across second-stage guesses for a fixed first-stage guess.Source: §3.4 · p. 19
• The attack has a concrete complexity bound when the final system has at least N′′_2 + c_excess equations, η + η_pre ≤ k, and the block-size constraint holds.The stated constraint is ⌈(n − k + η + η_pre)/h⌉ ≤ β.Source: §3.4 · pp. 19–21

3.5 Asymptotic consequences

• When k ≤ n − h, setting η1 = 0, η = k, and η_pre = 0 makes each trial polynomial-time and gives total cost poly(n) · 2^(ρn log2(1/(1−R))) under the continuous approximation.The exact rounded blockwise exponent is Λβ.Source: §3.5 · p. 21

4.1 Differences from the non-binary case

• Binary regularity adds one block-sum equation per block, and binary quadratic monomials involving a single variable reduce to linear monomials, changing the filtering constraint.The refined attack otherwise retains the non-binary blockwise construction and procedure.Source: §4.1 · p. 22

4.2 Complexity analysis

• The binary complexity analysis mirrors the non-binary attack, with differences only in variable counts, monomial counts, and Gaussian-elimination costs.Its elimination stage additionally uses the h block-wise linear equations.Source: §4.2 · pp. 22–23

4.3 Asymptotic consequences

• For R > ρ, the continuous-approximation dominant exponential term is 2ρn log2(1/(1−R+ρ)); for R ≤ ρ, syndrome and block-sum equations remove all asymptotic degrees of freedom.For R > ρ, the remaining variable count is (R−ρ)n, and no zero guessing is needed in the polynomial-time region.Source: §4.3 · p. 24
• When R and ρ are constants, the exponent is ρn log2(1/(1−R+ρ)); when R is constant and ρ=o(1), it is ρn log2(1/(1−R))+o(ρn).The expansions make explicit that the exponent decreases when regular weight scales below the code rate.Source: §4.3 · p. 24

5 Concrete security reassessment of existing RSD parameters

• Table 1 summarizes the complexity estimates and corresponding parameters, with non-integral n/h cases handled by assuming the final n−h⌊n/h⌋ coordinates are zero, as in prior works.Some parameter sets require a different ξ(N) choice to satisfy the condition used for the estimates.Source: §5 · p. 25

PCG/COT/VOLE

• Four non-binary and four binary stationary-syndrome parameter sets proposed in fall short of 128-bit security by 23–32 bits and 30–51 bits, respectively.These instances consist of multiple RSD instances sharing a supporter.Source: PCG/COT/VOLE · p. 25
• None of the Beaver-triple PCG parameter sets [22] reaches 128-bit security, with losses of 41–63 bits; five committed-VOLE instances fall short by 37–66 bits.The committed-VOLE analysis covers three parameters from and two from.Source: PCG/COT/VOLE · pp. 25–26
• Up to 29 bits in the non-binary case and up to 25 bits in the binary case: the attack improves on prior best attacks for benchmark instances.For refined 128-bit parameter sets from [20], estimated security losses are 27–47 bits over non-binary fields and 17–48 bits over the binary field.Source: PCG/COT/VOLE · p. 26
• For Ferret and Wolverine, no proposed parameter set reaches 128-bit security: one instance in each improves prior attack complexity by 28 bits, while another has a 17-bit security loss.The 28-bit improvements apply to instances already shown by prior attacks to fall below the claimed security level.Source: PCG/COT/VOLE · p. 26
• One full-version TinyKeys instance falls 9 bits short of its claimed 128-bit security level under the proposed attack.Source: PCG/COT/VOLE · p. 26

Signature from MPC-in-the-Head

• The evaluated 128-bit parameter set for the MPC-in-the-Head signature scheme is estimated to provide approximately 2 bits less security than claimed.Source: Signature from MPC-in-the-Head · p. 27

6 Conclusion

• The attack jointly balances zero guesses and syndrome-based eliminations across regular blocks, refines shared-preprocessing accounting, and sharpens analysis of the final overdetermined system.These refinements improve hybrid-algebraic complexities without introducing a fundamentally new solving paradigm.Source: §6 · p. 27
• By up to 29 bits over non-binary fields and 25 bits over binary fields, the previous best attack complexity drops on standard benchmark instances.These reductions are reported for the standard benchmark instances.Source: §6 · p. 27
• Across seven analyzed cryptographic applications, at least one parameter set per application falls below its claimed 128-bit target, with estimated losses of up to 66 bits.The conclusion recommends accounting for refined hybrid-algebraic complexity when selecting parameters for RSD-based constructions.Source: §6 · pp. 27–28

Experimental evidence for heuristic assumptions

• The binary field provides an informative test because its random-matrix invertibility probability is about 0.2889 and incorrect-guess rejection remains observable empirically.By contrast, invertibility over a large field is essentially certain, and expected solutions for an overdetermined random system decrease as field size increases.Source: Experimental evidence for heuristic… · p. 31
• These binary experiments test qualitative behavior rather than exhaustively validating the assumptions across the full parameter range in Table 1.The large-field estimates instead rely on the random-matrix and random-system analyses; the experiments provide evidence, not proof, that incorrect guesses are rejected with high probability.Source: Experimental evidence for heuristic… · pp. 31–32
• Across tested sizes n = 100 to 1000, the Step 1 submatrix was invertible with probability approximately 0.289, matching the random-matrix prediction of 0.2889.The experiment used 10,000 instances per size at fixed k/n = 0.2 and h/n = 0.04.Source: Experimental evidence for heuristic… · p. 31
• In 10,000-instance tests, incorrect-guess inconsistency rose with equation excess and instance size, approaching or nearing one in the tested ranges.The tests used RSD(100, 20, 2) while varying ξ(N) = aN, and RSD(n, 0.2n, 0.04n) for n from 50 to 300 with a = 1.Source: Experimental evidence for heuristic… · p. 32

Recovery conditioned on correct zero guesses

• With both guessing stages conditioned on a known solution, the algebraic procedure recovered valid solutions in all 10 tested binary RSD(512, 256, 16) instances.The procedure included syndrome-based elimination, preprocessing, linearization, and reconstruction; each recovered vector satisfied Hx = s and had exactly one nonzero coordinate per regular block.Source: Recovery conditioned on correct zero… · pp. 32–33
• The recovery tests are a sanity check under correct zero guesses, not an empirical measurement of the cost of finding those guesses or the total attack complexity.The full attack’s estimated complexity for the tested parameters was approximately 2^34.73 field operations.Source: Recovery conditioned on correct zero… · pp. 32–33

• For the binary instance (n, k, h) = (18, 10, 3), block-sum constraints and pairwise products enforce one nonzero coordinate per block.The first zero guess yields eleven linear equations in sixteen remaining coordinates; the successful partition leaves five variables after affine substitution.Source: A toy example of the refined attack · pp. 33, 35
• Preprocessing selects a shared subsystem, and the second zero guess makes five of its thirteen equations vanish, leaving eight nonzero equations in five monomials.The final linearization uses four equations and three monomial columns; its solution is followed by recovery and verification.Source: A toy example of the refined attack · pp. 36–37
• The successful guess recovers x with Hx = s and exactly one nonzero coordinate in each of the three blocks.The recovered variables also satisfy the mixed-monomial identities and the quadratic equation set aside during Step 2.Source: A toy example of the refined attack · p. 37
• The example demonstrates recovery for a successful guess only and does not establish an overwhelming rejection probability for incorrect guesses.Consistency of a selected linearized subsystem is not a substitute for checking the solution against the original RSD instance.Source: A toy example of the refined attack · p. 38

Non-binary fields

• Non-binary RSD is polynomial-time solvable when R^2ρn + 3Rρ ≤ 1−ρ, coarsely R^2ρ ≤ n^-1.Source: Non-binary fields · pp. 39–40
• For non-binary RSD with k≤n−h, guessing all k zero positions leaves an empty linearized system, so each trial is polynomial-time and balanced guesses succeed.Source: Non-binary fields · p. 40

Binary fields

• Binary RSD is polynomial-time solvable when R≤ρ or, coarsely, (R−ρ)^2ρ≤n^-1.Source: Binary fields · pp. 40–41
• For binary RSD with R>ρ, guessing k−h zeros yields cost poly(n)·2^{ρnΛ_β(R−ρ)+O(1)}, with polynomial work per trial.Source: Binary fields · p. 41
• For constant R,ρ, T_total ≤ poly(n)·2^{ρn log2(1/(1−R+ρ))}; for constant R and ρ=o(1), the exponent uses log2(1/(1−R)) plus o(ρn).Source: Binary fields · p. 42
• When R=o(1), ρ=o(R), log2 T_total ≤ ρnR^2/ln 2; when ρ=λR for 0<λ<1, log2 T_total ≤ ρn(1−λ)R^2/ln 2.Source: Binary fields · p. 42