CS Paper Radar

Hamming Ideals and Grobner Bases for ISD-like Syndrome Decoding

Roberto La Scala, Marco Marchesin, Sharwan K. Tiwari

cs.CR cs.SCmath.AC ·submitted 2026-09-16 16:05 UTC · v3

Abstract

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.

Comment
30 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Symmetric Models for Syndrome Decoding

cs.CR math.AC ·2026-09-12 ·Elisa Gorla, Simone Trebiani
similarity 0.63
Abstract · 35 pages

This paper introduces a new polynomial model for the exact variant of the Syndrome Decoding Problem (SDP) in the binary case. The model is based on elementary symmetric polynomials. We estimate the computational complexity of solving the corresponding polynomial system by establishing bounds on the degree of regularity and on the solving degree of the ideal associated to the model. The complexity estimate is lower than for previous polynomial models. We also provide a variant of the model whose complexity depends directly on the specific instance of the SDP and is lower than for the first model. Finally, we discuss how to apply our approach to solve other variants of the SDP.

0.30

Multiple-Function Approximated Coded Computing: Constructions and Error Bounds

cs.IT ·2026-10-12 ·Rimpi Borah, Wilton Kim, J. Harshan, Stanislav Kruglik, Han Mao Kiah
similarity 0.57
Abstract · 11 pages in two-column format. This updated version contains proofs of Theorem 1, Theorem 2 and Lemma 1 in Appendix

Coded computing mitigates stragglers in distributed computation. While Lagrange coded computing (LCC) enables exact polynomial computation over finite fields, Berrut approximated coded computing (BACC) enables approximate computation of arbitrary, including non-polynomial, functions in the analog domain. In applications such as multi-task learning and inference, multiple functions must be evaluated over different subsets of a common dataset, making single-round computation desirable to reduce communication overhead. An existing LCC approach addresses this requirement but is restricted to polynomial functions over finite fields, leaving single-round multi-function computation in the analog domain an open problem. In this work, we develop a single-round construction for computing multiple arbitrary functions using BACC. We first extend the existing multi-function computation approach in LCC to the BACC setting and derive an approximation-error bound. Building on this, we propose a construction based on Berrut basis functions for computing multiple arbitrary functions and derive its approximation-error bound. We analyze the scaling of both bounds with the number of functions and the number of data points per function, and numerically compare the two constructions over a wide range of arbitrary functions. The results demonstrate that the proposed construction achieves lower relative errors than the existing approach in the tested settings.

0.27

Regular Syndrome Decoding Is Easier Than Previously Estimated

cs.CR ·2026-10-21 ·Jiseung Kim, Minkyu Kim, Changmin Lee, Hochang Lee
similarity 0.57
Abstract · 42 pages. Comments are welcome

The Regular Syndrome Decoding (RSD) problem is a structured variant of classical Syndrome Decoding and underlies a growing number of efficient cryptographic constructions, including zero knowledge protocols, pseudorandom correlation generators, and MPC in the Head signatures. Although RSD is generally believed to be computationally hard, recent works have shown that algebraic attacks can outperform information set decoding on important RSD parameter regimes. Building on this line of work, we revisit the concrete hardness of RSD and show that many widely used parameter sets are substantially easier to solve than previously estimated. This improvement stems from a refined hybrid algebraic attack that exposes and removes a previously overlooked source of concrete complexity: the joint blockwise placement of zero coordinate guesses and syndrome based variable eliminations. Rather than treating the two guessing stages and linear elimination as largely separate choices, our method coordinates them across all regular blocks so that the guessing penalty is balanced while sufficient equations are retained for linearization. This gives a systematic block balancing principle for the entire guess reduce solve pipeline. We reassess several RSD based applications, including Ferret, Wolverine, and committed VOLE. Our estimates place at least one parameter set per application below its 128 bit target, with losses approaching 67 bits. On PCG benchmarks, we improve previous best attack costs by up to 29.77 and 25.91 bits over non binary and binary fields, respectively. Moreover, for the revised 128 bit PCG parameter sets of Liu et al. evaluated here, estimated attack costs are all below $2^{111}$ field operations. These results substantially revise the concrete security landscape of RSD and indicate that several existing parameter choices overestimate the hardness of their underlying RSD instances.

0.36

LDPC Fractus Codes: Sparse Codes with Recursive Structure

cs.IT math.CO ·2026-09-28 ·Jesús Carrillo-Pacheco
similarity 0.56
Abstract · 43 pages

We introduce a new family of recursively constructed sparse matrices, termed Fractus matrices, and investigate their use in constructing low-density parity-check (LDPC) codes. Generated through a self-similar recursive process, these matrices yield regular sparse parity-check matrices while preserving key structural properties across successive iterations. This recursive structure enables an efficient encoding algorithm with computational complexity that is nearly linear in the block length. Decoding is performed using standard iterative message-passing algorithms, thereby retaining the low-complexity decoding characteristic of LDPC codes. The proposed construction produces Tanner graphs with girth six and guarantees a minimum Hamming distance of at least $\ell+1$. We establish several algebraic properties of Fractus matrices, including sparsity, regularity, recursive decomposition, and symmetry under the flip-transpose operation. In addition, we show that the family of Fractus matrices admits a natural lattice structure and that the associated LDPC codes inherit corresponding lattice-theoretic properties. These results establish a connection between order theory and coding theory. Overall, the proposed framework integrates recursive matrix constructions, efficient encoding, graph-theoretic analysis, and lattice theory into a unified algebraic approach to the design and analysis of scalable LDPC codes.

0.28

Galois Hulls of Generalized Roth-Lempel Codes and Their Applications to EAQECCs

cs.IT ·2026-09-17 ·Xuefei Wu, Qi Liu, Yingchun Chen, Haiyan Zhou
similarity 0.56
Abstract

The dimension of a Galois hull is an important parameter in the construction of entanglement-assisted quantum error-correcting codes. In this paper, we study generalized Roth-Lempel (GRL) codes with prescribed Galois hull dimensions over finite fields of arbitrary characteristic. We develop a common construction method based on normalized Lagrange coefficients and suitable choices of column multipliers, and obtain six explicit constructions from multiplicative cosets, trace fibers, additive-subspace cosets, and mixed additive--multiplicative fibers. For extension sizes $s=2$ and $s=3$, we construct MDS and AMDS GRL codes with Galois hulls of specific dimensions. The resulting codes provide EAQECCs with explicit dimension, entanglement consumption, and relatively large minimum distance. Taking zero-dimensional hulls also gives Hermitian LCD GRL codes and the corresponding maximally entangled EAQECCs.

0.23

Decoding Algorithms for MDS Array Codes

cs.IT math.CO ·2026-08-27 ·Sara D. Cardell, Gustavo Terra Bastos, Cintya Wink de Oliveira Benedito
similarity 0.55
Abstract

We study decoding procedures for a family of MDS array codes previously constructed from the Kronecker product of a superregular matrix and a non-singular matrix over a finite field. By exploiting the particular structure of their parity-check matrices, we develop decoding algorithms for different channel models. For the erasure channel, we provide an algorithm capable of recovering any pattern of up to $n-k$ symbol erasures. For the $q$-ary symmetric channel, we investigate the decoding of one and two symbol errors and give explicit procedures for determining their locations and values. We also consider the particular case in which the superregular matrix is a Vandermonde matrix, showing how its additional algebraic structure can be exploited in the decoding process. Explicit examples over different finite fields are provided to illustrate the proposed procedures.

0.27

Efficient construction of subspace design codes over constant alphabet

cs.IT ·2026-10-14 ·Shu Liu
similarity 0.55
Abstract

Subspace-design codes form a central unifying framework in coding theory, connecting probabilistic existence results and explicit algebraically structured constructions. The two core families are folded Reed-Solomon codes and univariate multiplicity codes, both possessing the subspace-design property. These codes reach list-decoding capacity with polynomial-size lists, but their alphabet size grows with code length and hurts practical efficiency. Goyal, Guruswami, and Hsieh achieved a major breakthrough: they constructed the first explicit subspace-design codes over constant-size alphabets via the Alon-Edmonds-Luby expander framework, settling an open problem and showing subspace-design properties can hold without large alphabets. Despite recent progress, constructing subspace-design codes with low-complexity efficient encoding remains a critical open challenge. This work gives an explicit construction of r-dimensional subspace-design codes over a constant alphabet whose size grows exponentially with r. By comparison, Goyal et al. (FOCS 2026) built r-dimensional subspace-design codes with alphabet size doubly exponential in r squared. Our construction is computationally efficient: encoding scales quadratically with block length and linearly with dimension r in field operations. We use modified algebraic geometry codes, replacing rational evaluation points with higher-degree places to obtain a valid additive code. To confirm parameter bounds, we use Moore matrices to analyze determinants with many zero entries. We also generalize univariate multiplicity codes, originally built from Reed-Solomon codes, to algebraic geometry codes, and prove these AG-multiplicity codes achieve optimal parameters.

0.16

Generalized Hamming weights of codes arising from complete intersection

cs.IT math.AC ·2026-08-20 ·Eduardo Camps Moreno, Flavio Salizzoni, Rodrigo San-José
similarity 0.55
Abstract · 5 pages

We provide a positive answer to a conjecture proposed by Tohǎneanu and Van Tuyl regarding the minimum distance of codes whose underlying set of points is a reduced complete intersection. Despite the technical nature of the conjecture, we show that it follows directly from a not-well-known refinement of the classical Bézout bound for overdetermined polynomial systems. For completeness, this paper presents a self-contained proof of this refined bound. Furthermore, we show that using the same approach, it is possible to obtain a bound on the generalized Hamming weights of such a code and, more generally, to control the minimum distance of the codes obtained by evaluating forms of degree $d$ on the points of a zero-dimensional complete intersection.

0.32