Hamming Ideals and Grobner Bases for ISD-like Syndrome Decoding
Researchers combine Grobner bases with Information Set Decoding for syndrome decoding, testing feasibility against Classic McEliece NIST Category 1 parameters.
The paper proposes GBDecode, an ISD-like decoding algorithm that fixes only a subset of an information set and solves the resulting multivariate nonlinear systems via MultiSolve, which replaces one Grobner basis computation with many computations on simpler systems. Hamming weight constraints are reformulated using elementary symmetric functions and Lucas' identity factorizations to bound equation degree. Experiments on random binary linear codes use parameters matching the NIST Security Category 1 set of the Classic McEliece cryptosystem, assessing practical feasibility rather than breaking the scheme.
- GBDecode generalizes ISD by fixing only a subset of an information set, reducing combinatorial search space.
- MultiSolve replaces single Grobner basis computations with many smaller systems via exhaustive finite-field assignments.
- Hamming variety equations derived via elementary symmetric functions; bounded degree achieved using Lucas' identity factorizations.
- Evaluated on Classic McEliece NIST Security Category 1 parameters; feasibility assessed, cryptosystem not broken.
Full article241 words · extracted from arxiv.org · click to collapse
We investigate an algebraic approach to the Syndrome Decoding Problem, based on a reformulation of the Hamming weight constraint and its integration with the Information Set Decoding paradigm. We begin with a systematic analysis of the Hamming variety, deriving its defining equations in terms of elementary symmetric functions. Since these equations may have high degree, we exploit convolution identities for elementary symmetric functions, together with factorizations based on Lucas' identity, to derive an equivalent formulation with auxiliary variables and equations of bounded degree. Building on this modeling, we generalize the ISD paradigm through an ISD-like decoding strategy, implemented by the GBDecode algorithm, in which only a subset of an information set is fixed. This approach reduces the size of the combinatorial search space at the cost of solving the associated multivariate nonlinear systems. To handle this algebraic component, we employ the MultiSolve algorithm, which replaces a single Grobner basis computation with a collection of computations on simpler systems, obtained by exhaustively assigning a varying number of indeterminates over the finite field. This provides a tunable balance between combinatorial search and algebraic solving. We evaluate the resulting approach experimentally on instances of the Syndrome Decoding Problem for random binary linear codes, using parameters corresponding to the NIST Security Category 1 parameter set of the Classic McEliece cryptosystem. The experiments assess the feasibility of this combinatorial-algebraic approach and provide insights into the practical behavior of Grobner basis techniques within an ISD-like decoding framework.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.18866