Hamming Ideals and Grobner Bases for ISD-like Syndrome Decodingnew
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.