Hamming Ideals and Grobner Bases for ISD-like Syndrome Decoding

1. Introduction

• Exact Syndrome Decoding asks for an error vector of prescribed Hamming weight matching a given syndrome, a problem tied to code-based cryptographic security.The paper situates this problem in a setting where random-looking linear codes are regarded as difficult to decode.Source: §1 · pp. 1–2
• ISD remains an optimized combinatorial search over information sets, motivating exploration of algebraic methods for decoding.The paper notes that no sub-exponential algorithm is known for the cryptographic parameter regime.Source: §1 · p. 2
• The work derives Hamming-variety equations from elementary symmetric functions and reduces their number.It then uses auxiliary variables, convolution identities, and Lucas-identity factorizations to obtain an equivalent bounded-degree formulation.Source: §1 · p. 3
• GBDecode fixes only a subset of an information set, reducing combinatorial search while adding the cost of solving nonlinear systems.The paper uses MultiSolve to replace one Gröbner basis computation with simpler systems formed by exhaustively assigning varying numbers of indeterminates over the finite field.Source: §1 · p. 3
• The experiments use random binary linear codes with n = 3488, k = 2720, and t = 64, corresponding to the NIST Security Category 1 Classic McEliece setting.The introduction identifies these experiments as an investigation of the practical behavior of the MultiSolve strategy within an ISD-like attack.Source: §1 · p. 3

2. The Hamming ideals

• The section asks whether the number of generators of the ideal I_t + F can be reduced.Here F is the field-equations ideal, and the Hamming ideal combines it with weight-dependent equations.Source: §2 · p. 5
• The cutoff condition is equivalent to 2^(L+1) > max(t, n − t), and for n = 2m the minimal L is m at t ∈ {0, n} and m − 1 otherwise.The section uses this cutoff to identify which higher-degree generators can be omitted.Source: §2 · pp. 5–6
• The Hamming ideal's generators corresponding to elementary symmetric polynomials of degree 2^k can be omitted for k > L modulo the field equations.The section gives L as the minimal cutoff for which the stated weight-identification conditions hold.Source: §2 · pp. 5–6

3. Convolution Hamming ideals

• Explicit computation of e_{2^k} rapidly becomes infeasible as n increases, motivating a lifted-ideal characterization using recursive elementary-symmetric-function identities.The section adopts balanced variable splits in its recursive construction.Source: §3 · pp. 6–7
• Balanced recursive convolution generates O(nL) elementary-symmetric-function instances for the degrees used in the construction.The bound follows from counting the instances across the recursive binary decomposition tree.Source: §3 · pp. 7–8
• The Convolution Hamming ideal uses auxiliary variables while eliminating back to the original Hamming ideal and projecting onto the same Hamming variety.The auxiliary variables are recursively determined, so adjoining them introduces no new algebraic relations among the original variables.Source: §3 · p. 9

4. Factorized Convolution Hamming ideals

• The factorized convolution identity combines Lucas' theorem with convolution to restrict recursive contributions to degrees compatible with powers of two.At each step, only contributions compatible with powers-of-two degrees are propagated through the balanced decomposition tree.Source: §4 · pp. 10, 12
• The factorized recursive construction generates O(n) elementary-symmetric-function instances.This bound is uniform in the truncation parameter L.Source: §4 · pp. 10, 12
• The Factorized Convolution Hamming ideal is a compact lifted formulation whose elimination and projection recover the original Hamming ideal and variety.The section names the lifted construction the Factorized Convolution Hamming ideal of weight t.Source: §4 · pp. 12–13

5. Quadratic Factorized Convolution Hamming ideals

• The quadratic convolution identity relates elementary symmetric functions to recursively defined auxiliary polynomials.The section introduces polynomials recursively and states a quadratic identity for elementary symmetric functions of degree d.Source: §5 · p. 13
• The construction encodes recursive quadratic factorized convolution along the balanced binary decomposition tree T_n as a lifted Hamming ideal for each weight t.The paper names this construction the Quadratic Factorized Convolution Hamming ideal.Source: §5 · p. 15
• The quadratic factorized convolution Hamming ideal uses O(nL) auxiliary variables, and every generator has degree at most 2.The Factorized Convolution Hamming ideal uses fewer auxiliary variables, but its generators have higher degree.Source: §5 · p. 15
• The computational experiments compare the Convolution, Factorized Convolution, and Quadratic Factorized Convolution Hamming ideals on random binary codes with cryptographic parameters.Source: §5 · p. 15

6. Syndrome Decoding Problem and Information Sets

• The paper focuses on exact Syndrome Decoding, where the recovered vector has weight t; exact- and bounded-weight formulations are polynomially equivalent.The hardness of recovering such vectors underlies the security of code-based cryptography.Source: §6 · p. 16
• An Information Set consists of the free variables from a variable ordering, and an Evaluation Set is any subset of that Information Set.Source: §6 · p. 16
• Under the assumption that the syndrome variety contains at most one solution, a Gröbner basis can represent either the unique solution or the empty set.Source: §6 · p. 17
• The Hamming ideal can contain high-degree polynomials that increase Gröbner-basis solving degree; lifted Hamming ideals are proposed to mitigate this issue.Source: §6 · p. 17
• The hybrid strategy assigns values to an Evaluation Set and solves a family of systems, each involving only n − r variables.It considers assignments u with wt(u) ≤ t.Source: §6 · p. 17
• For each assignment u, the reduced syndrome-decoding variety uses residual weight t′ = t − wt(u), and computing these reduced varieties is equivalent to computing the original variety.Source: §6 · p. 18

7. An ISD-like strategy

• GBDecode samples an Evaluation Set and tests assignments with fixed weight t̄, solving reduced systems; if none succeeds, it updates the set.The residual weight is t′ = t − t̄.Source: §7 · pp. 18–19
• Classical ISD corresponds essentially to an Evaluation Set containing an Information Set, whereas this approach uses an Evaluation Set contained in an Information Set.Source: §7 · p. 19
• A single sampled Evaluation Set succeeds when the solution’s restriction to that set has weight t̄.Source: §7 · p. 19
• The expected Gröbner-basis call cost of GBDecode is minimized at t̄ = 0, and under unit-cost accounting this setting requires no more calls than the hybrid strategy.Source: §7 · pp. 19–20
• The Prange-like choice is suggested by the unit-cost model, but practical analysis must account for Gröbner-basis costs varying with r and residual weight t′.Source: §7 · p. 22

8. MultiSolve Algorithm

• MultiSolve is a general method for solving polynomial systems with at most one solution over a finite field.Source: §8 · p. 22
• The algorithm combines Gröbner-basis computations up to a prescribed solving degree with recursive branching called the multistep strategy.Source: §8 · p. 22
• Although MultiSolve is defined over arbitrary finite fields, the paper presents it over F2.Source: §8 · p. 22
• For the systems considered, a Gröbner basis has degree at most one when the solution set is either empty or a singleton.Source: §8 · p. 22

• GroebnerSafe runs a truncated Gröbner-basis computation up to degree d and timeout τ, returning tame only when it obtains a complete basis of maximum degree at most 1.Otherwise it returns wild, allowing MultiSolve to continue the recursive search.Source: §2 · p. 23
• MultiSolve uses an oracle to decide whether to run GroebnerSafe on a partially assigned system, otherwise recursively exploring both binary extensions.The procedure is depth-first; its assignment vector records values for the first ℓ variables.Source: §2 · p. 23
• MultiSolve terminates after at most n recursive steps, and may terminate earlier when GroebnerSafe computes a basis at an intermediate search-tree node.Its oracle generalizes exhaustive search when it always returns wild and recovers the classical hybrid strategy under the stated oracle condition.Source: §2 · p. 23
• Under the no-solution assumption, MultiSolve explores the full binary recursion tree, and its cost is modeled by the number of tame nodes, each requiring a complete Gröbner-basis computation.The analysis treats each GroebnerSafe execution as unit cost because calls share a fixed timeout.Source: §2 · p. 24
• The maximum speedup from a perfect oracle over an always-tame oracle is strictly less than a factor of 2.In the binary case, the always-tame oracle requires one GroebnerSafe execution per tree node, while a perfect oracle requires executions only at leaves.Source: §2 · p. 24
• In GBDecode, combinatorial cost C(t̄) is adjusted by a multiplicative factor equal to the average number of tame cases encountered during MultiSolve, and assignments with b = 1 are bounded by residual weight t′ = t − t̄.Source: §2 · pp. 24–25

Setup

• All experiments use the NIST Security Category 1 parameter set of the Classic McEliece cryptosystem; each configuration runs 200 instances at r = k − 10 = 2710 and r = k = 2720, using multiple CPUs.A single integer seed determines the code, error vector, Evaluation Set, and vector u, making each run exactly reproducible; the same seeds allow instance-by-instance comparisons across the three Hamming ideals.Source: §9 · p. 25, Setup · p. 25

One iteration of GBDecode

• Every root GroebnerSafe call returned wild because its basis was not completed within the timeout, so MultiSolve replaced each original system with simpler assigned-variable systems.The experiments use a 20-minute timeout and degree bound 20; the FC-Hamming generators have maximum degree 10.Source: Setup · p. 25, One iteration of GBDecode at r = k −10 · p. 26
• FC-Hamming requires the fewest tame calls on average, and a tame GroebnerSafe run with it takes about 10 minutes.FC-Hamming and QFC-Hamming averages use 200 instances; C-Hamming uses 50 because its computations were significantly more time-consuming.Source: One iteration of GBDecode at r = k −10 · p. 26, Table 1 · p. 26

Recovering the Prange algorithm

• At r = k and t̄ = 0, GBDecode reproduces Prange’s behavior: the recursion tree has one tame node, and an FC-Hamming GroebnerSafe call takes about 1 second on average.The Evaluation Set is an entire Information Set, the remaining X-variables are determined by the code equations, and only the weight condition remains.Source: Recovering the Prange algorithm · p. 27

Choosing r and t̄

• Among the tested choices, r = k and t̄ = 0 is most efficient; lowering r to k − 10 gains 1.24 bits but raises average tame calls from 1 to 6.2.At r = 2710, t̄ = 2 and 30 give 6.3 and 7.4 tame calls on average, while log2 C(t̄) rises by about 7 and 117 bits relative to t̄ = 0.Source: Choosing r and ¯t · p. 27, Table 3 · p. 27

Stability of the experiments

• The observed averages remain fairly stable as instances are added; the two 100-instance batches yield 5.9 and 6.5 FC-Hamming calls, and 6.8 QFC-Hamming calls each.Across 200 instances, the reported approximate confidence intervals are ±0.5 tame calls.Source: Stability of the experiments · p. 27

Discussion

• The measured cost combines combinatorial search with MultiSolve tame calls, and their balance depends on the Hamming ideal and solver.A Hamming ideal requiring fewer calls or a faster solver could make smaller values of r competitive.Source: Stability of the experiments · p. 28

• GBDecode and MultiSolve combine ISD with algebraic solving, trading combinatorial search against solving simpler systems formed by progressively assigning variables.Source: §10 · p. 28
• For the tested parameter choices, the Prange-like configuration r = k and t̄ = 0 yielded the lowest overall cost.Source: §10 · p. 28
• The choice of Hamming representation significantly affected computational cost, and FC-Hamming required the fewest Gröbner basis computations on average.Source: §10 · p. 28
• The results support the framework’s viability and point to improved Hamming representations, more efficient Gröbner basis strategies, and broader exploration of GBDecode’s trade-off for further study.Source: §10 · p. 28