HAMMING IDEALS AND GRÖBNER BASES FOR ISD-LIKE SYNDROME DECODING
arXiv:2609.18866v1 [cs.CR] 16 Sep 2026
ROBERTO LA SCALA∗ , MARCO MARCHESIN∗∗ , AND SHARWAN K. TIWARI†
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 ISDlike 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 Gröbner 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 Gröbner basis techniques within an ISD-like decoding framework.
1. Introduction Random-looking linear codes are widely regarded as difficult to decode. This observation, already formalized by Berlekamp, McEliece, and van Tilborg through the NP-completeness of the general decoding problem [4], has provided the theoretical foundation for code-based cryptography for almost fifty years. The basic idea, introduced by McEliece in 1978 [17] and later reformulated by Niederreiter in terms of parity-check matrices [20], consists of hiding the structure of a code with an efficient decoding algorithm so that it appears to be a random linear code. In practice, this is achieved by multiplying the generator or parity-check matrix by invertible and permutation matrices, obtaining an equivalent representation of the code that hides its original structure. 2020 Mathematics Subject Classification. Primary 94B35; Secondary 94A60, 11T71, 13P10. Key words and phrases. Syndrome decoding; Information set decoding; Gröbner bases; Hamming varieties; Polynomial systems over finite fields. The first and second authors were supported by the MUR PRIN 2022SC project, Grant No. 2022RFAZCJ. The first author was also co-funded by the University of Bari through the “Fondo acquisto e manutenzione attrezzature per la ricerca”, Grant No. DR 3191. 1
2
R. LA SCALA, M. MARCHESIN, AND S.K. TIWARI
From the perspective of an adversary, the resulting instance is therefore expected to resemble a generic decoding problem, for which no efficient algorithms are currently known, even in the presence of a quantum computer. This aspect has become especially important since Shor’s discovery of polynomial-time quantum algorithms for integer factorization and discrete logarithms [22], which showed that the security assumptions of RSA and elliptic-curve cryptography can be broken by quantum computers. As a consequence, interest in post-quantum cryptography has grown considerably, and code-based cryptographic schemes have emerged as some of the most promising candidates for long-term deployment. This is reflected in the NIST post-quantum standardization process, where code-based cryptography has played a prominent role, with schemes such as Classic McEliece, HQC, and BIKE being among the most extensively studied candidates [19, 5, 1, 2]. The security of code-based cryptographic constructions relies on the hardness of the Syndrome Decoding Problem (SDP), and in particular of its exact-weight variant, the Exact Syndrome Decoding Problem (ESDP). Given a random parity-check matrix H and a syndrome s, the goal is to recover an error vector e of prescribed Hamming weight satisfying He = s. Understanding exactly how hard this problem is, and for which parameters, is therefore not just a theoretical question: it directly determines the security level of cryptosystems used in practice. For decades, Information Set Decoding (ISD) has been the dominant approach to attacking the SDP in the generic setting. The original algorithm, proposed by Prange [21], introduced the fundamental idea underlying all subsequent developments. One selects a set of free variables, referred to as an information set, for the linear system corresponding to the matrix equation He = s, and assumes that the solution is zero on these variables. Equivalently, one extends the linear system with additional linear equations imposing these zero constraints, thereby obtaining a linear system with a unique solution that, under the assumption, has the prescribed weight. The Syndrome Decoding Problem can therefore be solved using linear algebra alone. Since Prange’s assumption is satisfied only with a certain probability, ISD repeatedly changes the information set until a suitable one is found. This success probability consequently determines the combinatorial complexity of the ISD attack. A major further development came with Stern, who introduced a meet-in-themiddle technique that substantially reduced the exponential complexity of Prange’s ISD algorithm [23]. Dumer subsequently refined this approach using generalized birthday techniques [8]. The representation techniques introduced by May, Meurer, and Thomae [15], and later refined by Becker, Joux, May, and Meurer [3], led to further improvements in asymptotic complexity. More recent advances have incorporated nearest-neighbor search and sieving techniques [16]. Despite these successive refinements, however, the underlying algorithmic paradigm has remained essentially unchanged: ISD is still, at its core, an optimized combinatorial search over information sets. No sub-exponential algorithm is known for the cryptographic parameter regime, and this remarkable persistence is one of the main reasons why decoding problems remain attractive as hardness assumptions. At the same time, the relatively stable complexity of ISD also suggests exploring alternative algorithmic paradigms that may provide a complementary perspective on the computational structure of decoding.
HAMMING IDEALS AND GRÖBNER BASES FOR SYNDROME DECODING
3
One such paradigm is provided by algebraic methods. In [18] and [7], the Hamming weight constraint is shown to admit an algebraic modeling, in which the coordinates of an arbitrary vector are regarded as variables and constrained by a system of multivariate nonlinear equations. Thus, the (Exact) Syndrome Decoding Problem can be formulated as a problem of solving a multivariate polynomial system, in which the linear equations corresponding to He = s are supplemented with nonlinear equations defining the Hamming variety, namely, the set of vectors having a prescribed Hamming weight. Note that [18] actually establishes an equivalence between the Syndrome Decoding Problem and the Multivariate Quadratic (MQ) problem, while [24] investigates the reduction of the MQ problem to SDP through MRHS representations. A first contribution of the present work is a systematic analysis of the Hamming variety, leading to the derivation of its defining equations in terms of elementary symmetric functions and to a reduction in their number. This analysis is presented in Section 2. Since these equations may have high degree, Sections 3–5 develop a degree-reduction strategy based on auxiliary variables, convolution identities for elementary symmetric functions, and factorizations derived from Lucas’ identity, ultimately yielding an equivalent formulation with equations of bounded degree. We further extend the ISD approach to this algebraic formulation of the Syndrome Decoding Problem. In Sections 6 and 7, we investigate the use of subsets of information sets, at the cost of solving multivariate nonlinear systems, for instance by means of Gröbner basis techniques. This approach, implemented in the GBDecode algorithm in Section 7, reduces the combinatorial complexity of the ISD search, while introducing the additional cost of solving the resulting nonlinear systems. To explore this trade-off, we employ the MultiSolve algorithm [12, 13], described in Section 8, which replaces the computation of a single Gröbner basis by a collection of Gröbner basis computations for simpler systems, obtained by exhaustively assigning a varying number of indeterminates over the finite field. The practical behavior of this strategy within an ISD-like attack is investigated experimentally in Section 9 on Syndrome Decoding instances for random binary linear codes, using the NIST Security Category 1 setting of the Classic McEliece cryptosystem, with n = 3488, k = 2720, t = 64. 2. The Hamming ideals Let F2 = GF(2) denote the binary field and let n > 0 be an integer. Consider the vector space V = Fn2 . The Hamming weight of a vector v = (v1 , . . . , vn ) ∈ V is defined as wt(v) = #{i | vi = 1} ∈ {0, 1, . . . , n} Let t = wt(v) and set l = ⌊log2 (n)⌋. Consider the binary expansion X t= tk 2k (tk ∈ F2 ) 0≤k≤l
A first goal is to express the binary digits tk as Boolean functions of the coordinates v1 , . . . , v n . Let F be any field and let F[x1 , . . . , xn ] denote the algebra of the multivariate polynomials with coefficients in F. For each integer d ≥ 0, the elementary symmetric
4
R. LA SCALA, M. MARCHESIN, AND S.K. TIWARI
function of degree d in the variables x1 , . . . , xn is by definition the polynomial X xi1 · · · xid ∈ F[x1 , . . . , xn ] ed (x1 , . . . , xn ) = 1≤i1 <···<id ≤n
with the convention that e0 = 1 and ed = 0 for d < 0 or d > n. Throughout the paper, ESF stands for elementary symmetric function. When F = F2 , these are referred to as Boolean elementary symmetric functions. Lemma 2.1. Let v = (v1 , . . . , vn ) ∈ V and put t = wt(v). Then t ed (v1 , . . . , vn ) ≡ mod 2 d Proof. By definition, we have X
ed (v1 , . . . , vn ) =
vi1 · · · vid ∈ F2
1≤i1 <···<id ≤n
Since vi ∈ F2 , a monomial vi1 · · · vid equals 1 if and only if all the chosen indices correspond to nonzero coordinates of v. Equivalently, {i1 , . . . , id } ⊂ {i | vi = 1} = S If t = wt(v) = #S, the number of such d-tuples is exactly
t d .
□
Lucas’ theorem (1878) is a well-known result describing the reduction of binomial coefficients modulo a prime p in terms of their base-p expansions. In the case p = 2, it yields the following. P P Theorem 2.2 (Lucas’ Theorem modulo 2). Let t = k tk 2k and d = k dk 2k be the binary expansions of two integers t, d ≥ 0. Then Y tk t ≡ mod 2 d dk k
As an immediate application of Lucas’ theorem, we obtain the following result. Theorem 2.3. Let v = (v1 , . . . , vn ) ∈ V and let X t= tk 2k 0≤k≤l
be the binary expansion of the Hamming weight t = wt(v), where l = ⌊log2 (n)⌋ and tk ∈ F2 . Then, for each k, one has tk = e2k (v) where e2k denotes the Boolean ESF of degree 2k . Proof. By Lucas’ Theorem modulo 2, applied for d = 2k (0 ≤ k ≤ l), one has t ≡ tk mod 2 2k Since e2k (v) = 2tk mod 2, the claim follows. Based on the previous results, we introduce the following notions.
□
HAMMING IDEALS AND GRÖBNER BASES FOR SYNDROME DECODING
5
Definition 2.4. For any integer 0 ≤ t ≤ n, the Hamming variety of weight t is defined as Ht = {v ∈ V | wt(v) = t} Let R = F2 [x1 , . . . , xn ] and let F = ⟨x2i − xi | 1 ≤ i ≤ n⟩ be the field equations ideal of R. Write the binary expansion of t as X t= tk 2k (l = ⌊log2 (n)⌋) 0≤k≤l
Then, the Hamming ideal of weight t is defined as the ideal It + F ⊂ R where It = ⟨e2k − tk | 0 ≤ k ≤ l⟩ Let J ⊂ R be an ideal and let F̄2 denote the algebraic closure of the field F2 . If V̄ = F̄n2 , one defines V (J) = {v ∈ V̄ | f (v) = 0, ∀f ∈ J}, VF2 (J) = V (J) ∩ V. By a well-known consequence of the Nullstellensatz over finite fields (see, for instance, [11]), one has VF2 (J) = V (J + F) with J + F a radical ideal. Combining these results with Theorem 2.3 shows that the Hamming variety and the Hamming ideal are related by VF2 (It ) = V (It + F ) = Ht An interesting question is whether the number of generators of the ideal It + F can be reduced. Recall that V = Fn2 denotes the n-dimensional vector space over the binary field. P Theorem 2.5. Let 0 ≤ t ≤ n and write t = 0≤k≤l tk 2k (l = ⌊log2 (n)⌋). For an integer 0 ≤ L ≤ l, the following properties are equivalent: P (1) ∀v ∈ V , if wt(v) = 0≤k≤l t′k 2k and t′0 = t0 , . . . , t′L = tL then wt(v) = t; (2) 2L+1 > max(t, n − t). In particular, the minimal integer L for which these equivalent properties hold is L = ⌈log2 (max(t, n − t) + 1)⌉ − 1. m
When n = 2 , this minimal L is equal to m for t ∈ {0, n}, and to m − 1 otherwise. Proof. Since the Hamming weight wt : V → {0, 1, . . . , n} is a surjective map, the condition (1) is equivalent to the following arithmetical statement (1′ ) if 0 ≤ t′ ≤ n and t′ ≡ t mod 2L+1 then t′ = t. Assume by contradiction that condition (2) does not hold, that is 2L+1 ≤ max(t, n − t) Hence, either t + 2L+1 ≤ n or t − 2L+1 ≥ 0. In the first case, let t′ = t + 2L+1 ; in the second case, let t′ = t − 2L+1 . In both cases, we have 0 ≤ t′ ≤ n, t′ ̸= t, and t′ ≡ t mod 2L+1 This contradicts condition (1′ ), which states that t is the unique integer in {0, 1, . . . , n} modulo 2L+1 . Therefore, condition (1′ ) necessarily implies condition (2).
6
R. LA SCALA, M. MARCHESIN, AND S.K. TIWARI
In a similar way, assume now that condition (2) holds, that is 2L+1 > max(t, n − t) Then t − 2L+1 < 0 and t + 2L+1 > n, so there exists no integer 0 ≤ t′ ≤ n, t′ ̸= t, such that t′ ≡ t mod 2L+1 . Thus (1′ ) holds, and consequently condition (1) is satisfied. Finally, condition (2) is equivalent to L + 1 > log2 (max(t, n − t)) and the minimal integer L for which this inequality holds is L = ⌈log2 (max(t, n − t) + 1)⌉ − 1 The final claim for the case n = 2m follows immediately.
□
Using the above result, the generators of the Hamming ideal corresponding to the elementary symmetric polynomials of degree 2k with k > L can be omitted modulo F. Hence, the Hamming ideal It + F can equivalently be defined by It = ⟨e2k − tk | 0 ≤ k ≤ L⟩ P where L = ⌈log2 (max(t, n − t) + 1)⌉ − 1 and t = 0≤k≤L tk 2k is the binary representation of the weight 0 ≤ t ≤ n. 3. Convolution Hamming ideals As n increases, the explicit computation of the polynomial e2k rapidly becomes infeasible, due to the presence of 2nk monomials. Therefore, we look for an alternative characterization of the Hamming ideal It + F as the elimination ideal of a larger lifted ideal. In this context, recursive definitions of the elementary symmetric functions provide a natural approach. We start with combinatorial identities that hold over an arbitrary field F. To simplify the notation, we introduce the following convention. For any integers d ≥ 0 and 1 ≤ a ≤ b ≤ n, we set (a,b)
ed
= ed (xa , . . . , xb ) ∈ F[x1 , . . . , xn ]
where ed (xa , . . . , xb ) denotes the elementary symmetric polynomial of degree d in the variables xa , . . . , xb . We have the following well-known combinatorial identity (see, for instance, [14]) Proposition 3.1 (Convolution identity). Let n ≥ 2, 0 ≤ d ≤ n and 1 ≤ m < n be integers. It holds X (1,m) (m+1,n) (1,n) ed = ek ed−k 0≤k≤d (a,b)
(a,b)
where we adopt the convention that e0 = 1 and ek Equivalently, the sum can be restricted to
= 0 for k > b − a + 1.
max(0, d − (n − m)) ≤ k ≤ min(d, m) As a special case, taking m = n − 1 yields the classical Stifel identity. Proposition 3.2 (Stifel identity). Let 0 ≤ d ≤ n. Then (1,n)
ed
(1,n−1)
= ed
(1,n−1)
+ xn ed−1
HAMMING IDEALS AND GRÖBNER BASES FOR SYNDROME DECODING
7
In contrast to Stifel’s choice m = n − 1, one may take m = ⌊(1 + n)/2⌋ = ⌈n/2⌉, in which case n − m = ⌊n/2⌋, yielding a balanced partition of the variables. We consider the construction of the elementary symmetric functions appearing (1,n) in the definition of the Hamming ideal It + F (0 ≤ t ≤ n), namely e2k for all 0 ≤ k ≤ L, where L = ⌈log2 (max(t, n − t) + 1)⌉ − 1 We seek to bound the number of ESFs produced by the recursive convolution scheme obtained by splitting each set of variables into two balanced blocks. The starting point is the following lemma. Lemma 3.3. Let n ≥ 2, and let Tn be the set of intervals generated by the recursive binary decomposition of {1, . . . , n}, where each interval (a, b) = {a, . . . , b} (a < b) is split into (a, m) ∪ (m + 1, b) with m = ⌊ a+b 2 ⌋. Let 0 ≤ L ≤ ⌊log2 (n)⌋ be an integer, and define X N (n, L) = min(|(a, b)|, 2L ) (a,b)∈Tn
where |(a, b)| = b − a + 1 denotes the length of the interval (a, b). Then N (n, L) = O(nL) Proof. Let D be the depth of the decomposition binary tree Tn , so that D = ⌈log2 (n)⌉ For each 0 ≤ k ≤ D, let Zk denote the set of intervals at level k of the decomposition. We observe two structural properties. First, note that |Zk | ≤ 2k for all k. Second, for each fixed k, the intervals in Zk are pairwise disjoint and contained in {1, . . . , n}, hence X |I| ≤ n I∈Zk
We write N (n, L) =
X
X
min(|I|, 2L )
0≤k≤D I∈Zk
and split the sum into two ranges. Case 1: 0 ≤ k ≤ D − L. Using min(|I|, 2L ) ≤ 2L and |Zk | ≤ 2k , we obtain P P P L k L 0≤k≤D−L 2 ) 2 0≤k≤D−L I∈Zk min(|I|, 2 ) ≤ ( = (2D−L+1 − 1) 2L = 2D+1 − 2L < 2D+1 Since D = ⌈log2 (n)⌉, we have n ≤ 2D ≤ 2n, and consequently 2D+1 ≤ 4n. Therefore, it holds X X min(|I|, 2L ) ≤ 4n 0≤k≤D−L I∈Zk
Case 2: D − L + 1 ≤ k ≤ D. Since min(|I|, 2L ) ≤ |I|, we have X X min(|I|, 2L ) ≤ |I| ≤ n I∈Zk
I∈Zk
8
R. LA SCALA, M. MARCHESIN, AND S.K. TIWARI
There are at most L such levels, so X X
min(|I|, 2L ) ≤ Ln
D−L+1≤k≤D I∈Zk
Combining the two estimates gives N (n, L) ≤ 4n + Ln = n(L + 4) which proves the claim.
□
An immediate consequence of the above result is the following proposition. Proposition 3.4. Let n ≥ 2 and 0 ≤ L ≤ ⌊log2 (n)⌋ be integers. Consider the (1,n) recursive construction of the elementary symmetric functions e2k for 0 ≤ k ≤ L, obtained by repeated application of the convolution identity with balanced splits. Then, the total number of ESF instances generated by this recursion is X min(|(a, b)|, 2L ) N (n, L) = (a,b)∈Tn
where the sum ranges over all intervals (a, b) in the recursive binary decomposition tree Tn . Moreover, it holds N (n, L) = O(nL) (a,b)
Proof. For each interval (a, b) ∈ Tn , the convolution formula for e2k involves intermediate degrees 0 ≤ d ≤ 2k . Since 2k ≤ 2L for every 0 ≤ k ≤ L, the recursive computation at node (a, b) requires all ESFs (a,b)
ed
(1 ≤ d ≤ min(|(a, b)|, 2L )) (a,b)
Thus, excluding the trivial constant term e0 = 1, the number of ESF instances generated at node (a, b) is min(|(a, b)|, 2L ). Summing over all nodes gives X N (n, L) = min(|(a, b)|, 2L ) (a,b)∈Tn
The bound N (n, L) = O(nL) follows directly from the previous lemma.
□
We now translate the recursive construction from Proposition 3.4 into an algebraic setting. P Theorem 3.5. Let 0 ≤ t ≤ n be an integer and let t = 0≤k≤L tk 2k be its binary expansion where L = ⌈log2 (max(t, n−t)+1)⌉−1. Consider the two sets of variables X = {x1 , . . . , xn }, (a,b) Y = {yd | 1 ≤ d ≤ min(|(a, b)|, 2L ), (a, b) ∈ Tn } Let R = F2 [X] and R′ = F2 [X ∪ Y ] be the corresponding polynomial algebras, and let F and F ′ denote their respective field equations ideals. Define the following sets of polynomials (a,a)
A = {y1 − xa | 1 ≤ a ≤ n}, P (a,b) (a,m) (m+1,b) B = {yd − 0≤k≤d yk yd−k | 1 ≤ d ≤ min(b − a + 1, 2L ), (a, b) ∈ Tn , a < b, m = ⌊ a+b 2 ⌋}, (1,n) C = {y2k − tk | 0 ≤ k ≤ L}
HAMMING IDEALS AND GRÖBNER BASES FOR SYNDROME DECODING (a,b)
(a,b)
For polynomials in B, we adopt the convention that y0 = 1 and yd d > b − a + 1. Moreover, we put X N = N (n, L) = min(b − a + 1, 2L )
9
= 0 for
(a,b)∈Tn
By considering the ideal Jt = ⟨A ∪ B ∪ C⟩ ⊂ R′ , we obtain (Jt + F ′ ) ∩ R = It + F , φ(VF2 (Jt )) = VF2 (It ) = Ht where φ : Fn+N → Fn2 denotes the canonical projection onto the X-coordinates. 2 Proof. By construction, the polynomials in B encode the balanced convolution identities, so recursively (a,b) (a,b) yd = ed for all 1 ≤ d ≤ min(b − a + 1, 2L ) and every (a, b) ∈ Tn . The polynomials in C impose (1,n) e2k = tk (0 ≤ k ≤ L) according to the binary expansion of t. Hence It + F ⊆ (Jt + F ′ ) ∩ R. (a,b) Conversely, each auxiliary variable yd is uniquely determined by the relations in A ∪ B, recursively along the binary decomposition tree Tn . More precisely, the variables attached to leaves are fixed by A, while those attached to internal intervals are determined recursively from previously defined variables. Thus, adjoining the variables in Y introduces no new algebraic relations among the variables in X, and therefore (Jt + F ′ ) ∩ R = It + F . □ We call the ideal Jt + F ′ defined in Theorem 3.5 the Convolution Hamming (1,n) ideal of weight t. Since the elementary symmetric functions e2k are the only ones appearing in the Hamming ideal It + F, one can use Lucas’ Theorem to factor any ESF in terms of ESFs of degree a power of 2, modulo the field-equation ideal F. 4. Factorized Convolution Hamming ideals An immediate consequence of Lucas’ Theorem modulo 2 is the following factorization identity among Boolean elementary symmetric functions. P Theorem 4.1 (Factorization identity). Let 0 ≤ d ≤ n and let d = k dk 2k be its binary expansion. Then Y ed (x1 , . . . , xn ) ≡ e2k (x1 , . . . , xn ) mod F k|dk =1
Proof. Let v = (v1 , . . . , vn ) ∈ V and put t = wt(v). By Lemma 2.1, we have t ed (v) ≡ mod 2 d Moreover, by Lucas’ theorem Y t tk ≡ mod 2 d dk k
10
R. LA SCALA, M. MARCHESIN, AND S.K. TIWARI
where t =
k k tk 2 . We conclude that
P
ed (v) = 1 ⇐⇒ tk ≥ dk , ∀ k ⇐⇒ dk = 1 implies that tk = 1, ∀ k By using again Lemma 2.1 and Lucas’ Theorem, we obtain t mod 2 ≡ tk mod 2 e2k (v) ≡ 2k It follows that e2k (v) = 1 ⇐⇒ tk = 1 Let us consider the product Y
e2k (v)
k|dk =1
This product is equal to one if and only if e2k (v) = 1 for all k such that dk = 1, or equivalently tk = 1 for all such k. We conclude that Y ed (v) = 1 ⇐⇒ e2k (v) = 1 k|dk =1
Q
In other words, we have that ed (v) = k|dk =1 e2k (v), for all v ∈ V and therefore Y ed (x1 , . . . , xn ) ≡ e2k (x1 , . . . , xn ) mod F k|dk =1
□ Applying the factorization identity to the convolution identity yields the following result. Theorem 4.2 (Factorized Convolution identity). Let n ≥ 2 and 1 ≤ m < n be integers. Let 0 ≤ d ≤ n. The following identity holds X Y (1,m) Y (1,n) (m+1,n) ed ≡ ( e2k )( e2k ) mod F 0≤j≤d k|jk =1
where j = k jk 2k and d − j = d − j, respectively. P
k|(d−j)k =1 k k (d − j)k 2 are the binary expansions of j and
P
We now estimate the number of ESFs arising in the factorized convolution scheme obtained by recursively partitioning the variables into two balanced blocks. The following combinatorial lemma provides the key bound. Lemma 4.3. Let n ≥ 2, and let Tn be the set of intervals in the recursive binary decomposition tree of {1, . . . , n} defined in Lemma 3.3. Let 0 ≤ L ≤ ⌊log2 (n)⌋. For each interval I ∈ Tn , denote by |I| its length and define ρ(I, L) = #{k ≥ 0 | 2k ≤ min(|I|, 2L )} = min(⌊log2 (|I|)⌋, L) + 1 P Set M (n, L) = I∈Tn ρ(I, L). Then M (n, L) = O(n) uniformly in L, that is, there exists an absolute constant C > 0 such that M (n, L) ≤ Cn for all n ≥ 2 and all 0 ≤ L ≤ ⌊log2 (n)⌋.
HAMMING IDEALS AND GRÖBNER BASES FOR SYNDROME DECODING
11
Proof. Recall that the set Tn is constructed recursively by splitting each interval I = (a, b) (a < b) into (a, m) ∪ (m + 1, b) a+b where m = ⌊ 2 ⌋. Hence every internal node has exactly two children, and the depth of the tree is D = ⌈log2 (n)⌉. For every interval I ∈ Tn , we have ρ(I, L) = min(⌊log2 (|I|)⌋, L) + 1 ≤ log2 (|I|) + 1 Therefore, it holds X
M (n, L) ≤
(log2 (|I|) + 1)
I∈Tn
For each depth 0 ≤ d ≤ D, let Zd denote the set of intervals at depth d. Since every node has at most two children, we have |Zd | ≤ 2d Moreover, by construction of the balanced decomposition, every interval I ∈ Zd satisfies lnm n |I| ≤ d ≤ d + 1 2 2 Hence n log2 (|I|) ≤ log2 ( d + 1) 2 Since D = ⌈log2 (n)⌉, we have n ≤ 2D and therefore 2nd + 1 ≤ 2D−d + 1. Because d ≤ D, we have 2D−d ≥ 1, hence 2D−d + 1 ≤ 2D−d+1 . We conclude log2 (|I|) ≤ D − d + 1 Summing over all intervals at depth d, we obtain X (log2 (|I|) + 1) ≤ 2d (D − d + 2) I∈Zd
Summing over all depths, M (n, L) ≤
X
2d (D − d + 2)
0≤d≤D D
Factoring out 2 , we have M (n, L) ≤ 2D ·
X D−d+2 2D−d
0≤d≤D
Setting r = D − d, we obtain M (n, L) ≤ 2D ·
X r+2 2r
0≤r≤D
Since
∞ X r+2 r=0
2r
=
∞ X r
∞ X 1 + 2 =2+4=6 r r 2 2 r=0 r=0
we conclude that M (n, L) ≤ 6 · 2D Finally, since 2D ≤ 2n, we obtain M (n, L) ≤ 12n □
12
R. LA SCALA, M. MARCHESIN, AND S.K. TIWARI
An immediate consequence of Lemma 4.3 and the factorized convolution identity is the following proposition. Proposition 4.4. Let n ≥ 2 and 0 ≤ L ≤ ⌊log2 (n)⌋ be integers. Consider the (1,n) recursive construction of the elementary symmetric functions e2k for 0 ≤ k ≤ L obtained by repeated application of the factorized convolution identity along the recursive binary decomposition tree Tn . Let M (n, L) denote the total number of ESF instances generated by this construction. Then X ρ(I, L) M (n, L) = I∈Tn k
where ρ(I, L) = #{k ≥ 0 | 2 ≤ min(|I|, 2L )} = min(⌊log2 (|I|)⌋, L) + 1. By Lemma 4.3, it follows that M (n, L) = O(n) uniformly in L. Proof. For each interval I ∈ Tn , the factorized convolution formula for eI2k decomposes the computation into contributions from the two balanced subintervals of I. Unlike the standard convolution, the factorized version ensures that, at each recursive step, only contributions compatible with powers of two degrees are propagated through the tree. Since 0 ≤ k ≤ L, the recursion at node I generates ESF instances corresponding to all levels k such that the degree 2k is admissible with respect to both |I| and the truncation degree 2L . The number of such levels is therefore ρ(I, L) = #{k ≥ 0 | 2k ≤ min(|I|, 2L )} Summing over all intervals I ∈ Tn , we obtain X M (n, L) = ρ(I, L) I∈Tn
The bound M (n, L) = O(n) follows directly from Lemma 4.3.
□
Using the complexity compression provided by Lemma 4.3 applied to the recursive construction of Proposition 4.4, we obtain a compact version of a Convolution Hamming ideal. The proof follows the same arguments as in Theorem 3.5. P Theorem 4.5. Let 0 ≤ t ≤ n be an integer and let t = 0≤k≤L tk 2k be its binary expansion, where L = ⌈log2 (max(t, n − t) + 1)⌉ − 1. Let Tn be the recursive binary decomposition tree of {1, . . . , n}. For each interval I = (a, b) ∈ Tn , we define ρ(I, L) = min(⌊log2 |I|⌋, L) + 1 Consider the sets of variables X = {x1 , . . . , xn }, (a,b) Y = {y2k | (a, b) ∈ Tn , 0 ≤ k < ρ((a, b), L)} Let R = F2 [X] and R′ = F2 [X ∪ Y ], and define the following sets of polynomials (a,a)
A = {y1 − xa | 1 ≤ a ≤ n}, (a,b) (a,b) B = {y2k − f2k | (a, b) ∈ Tn , a < b, 0 ≤ k < ρ((a, b), L)}, (1,n) C = {y2k − tk | 0 ≤ k ≤ L}
HAMMING IDEALS AND GRÖBNER BASES FOR SYNDROME DECODING
13
where (a,b)
f2k
X
=
(
(a,m)
Y
y2h
0≤j≤2k h|jh =1
)(
Y
(m+1,b)
y2h
)
h|(2k −j)h =1
P P k h k h with m = ⌊ a+b h jh 2 , 2 − j = h (2 − j)h 2 denoting the binary 2 ⌋ and j = expansions of the integers j, 2k − j, respectively. As usual, we adopt the convention (a,b) that yd = 0 whenever d > b − a + 1. Finally, put X M = M (n, L) = ρ(I, L) I∈Tn ′
and define the ideal Jt = ⟨A ∪ B ∪ C⟩ ⊂ R . We have (Jt + F ′ ) ∩ R = It + F , φ(VF2 (Jt )) = VF2 (It ) = Ht where φ : Fn+M → Fn2 denotes the canonical projection onto the X-coordinates. 2 We refer to the ideal Jt + F ′ constructed in Theorem 4.5 as the Factorized Convolution Hamming ideal of weight t. 5. Quadratic Factorized Convolution Hamming ideals A straightforward consequence of the factorized convolution formula is the following result. Corollary 5.1 (Quadratic Factorized Convolution identities). Let n ≥ 2 and 1 ≤ m < n. For every subset S ⊂ N, we define polynomials in R = F2 [x1 , . . . , xn ] by Y (1,m) (1,m) cS = e2k k∈S (1,m)
with the convention that c∅ recursively by
(1,m)
= 1. Equivalently, the polynomials cS
(1,m)
are defined
(1,m) (1,m) (k ∈ / S) e2k
cS∪{k} = cS
(m+1,n)
Similarly, we define polynomials cS ∈ R. Then, the elementary symmetric function of degree d ≥ 0 satisfies the following quadratic identity X (1,m) (1,n) (m+1,n) ed ≡ c{k|jk =1} c{k|(d−j)k =1} mod F 0≤j≤d (a,b)
We now study the number of non-constant polynomials cS (S ̸= ∅) arising in the quadratic factorized convolution scheme obtained by recursively partitioning the intervals into two balanced blocks. A quantitative bound is provided by the following result. Lemma 5.2. Let n ≥ 2, and consider Tn , the set of intervals in the recursive binary decomposition tree of {1, . . . , n} defined in Lemma 3.3. Let also 0 < L ≤ ⌊log2 (n)⌋. For each interval I ∈ Tn , define as in Lemma 4.3 ρ(I, L) = min(⌊log2 (|I|)⌋, L) + 1 By defining C(n, L) =
X I∈Tn
we have that C(n, L) = O(nL).
(2ρ(I,L) − 1)
14
R. LA SCALA, M. MARCHESIN, AND S.K. TIWARI
Proof. The set Tn is obtained from a recursive binary decomposition of {1, . . . , n}, where each interval I = (a, b) (a < b) is split as I = (a, m) ∪ (m + 1, b) with m = ⌊ a+b 2 ⌋. Hence, the resulting tree has depth D = ⌈log2 (n)⌉, and at each depth 0 ≤ d ≤ D there are at most 2d intervals. For an interval I ∈ Tn at depth d, as in the Lemma 4.3 we obtain ⌊log2 (|I|)⌋ ≤ D − d + 1 Consequently, ρ(I, L) = min(⌊log2 (|I|)⌋, L) + 1 ≤ min(D − d + 1, L) + 1 We aim to estimate X
C(n, L) =
(2ρ(I,L) − 1) ≤
X
2ρ(I,L)
I∈Tn
I∈Tn
We split the sum by depth d and denote by Zd the set of intervals at depth d. Then |Zd | ≤ 2d , and we have X X X C(n, L) ≤ 2ρ(I,L) ≤ 2d · 2min(D−d+1,L)+1 0≤d≤D I∈Zd
X
≤
d
2 ·2
0≤d≤D min(D−d+2,L+1)
0≤d≤D
We distinguish two cases. Case 1: d ≤ D − L. Then D − d + 2 ≥ L + 2, hence min(D − d + 2, L + 1) = L + 1, and X 2ρ(I,L) ≤ 2d · 2L+1 I∈Zd
Summing over 0 ≤ d ≤ D − L, we obtain X X 2d 2L+1 ≤ 2L+1 · 2d ≤ 2L+1 · 2D−L+1 = 2D+2 ≤ 8n 0≤d≤D−L
0≤d≤D−L
Case 2: d > D − L. Let r = D − d. Then 0 ≤ r < L, and min(D − d + 2, L + 1) ≤ D − d + 2 = r + 2 Thus, since d + r = D X
2ρ(I,L) ≤ 2d · 2r+2 = 2D+2
I∈Zd
Summing over the L deepest levels, X 2D+2 ≤ L · 2D+2 ≤ 8nL D−L+1≤d≤D
Combining both cases, we obtain C(n, L) ≤ 8n + 8nL = 8n(L + 1) which proves the claim.
□
Combining Lemma 5.2 and Proposition 4.4, we derive the following result on the recursive application of quadratic factorized convolution identities.
HAMMING IDEALS AND GRÖBNER BASES FOR SYNDROME DECODING
15
Proposition 5.3. Let n ≥ 2 and 0 < L ≤ ⌊log2 (n)⌋ be integers. Consider the (1,n) recursive construction of the elementary symmetric functions e2k for 0 ≤ k ≤ L obtained by repeated application of the quadratic factorized convolution scheme along the recursive binary decomposition tree Tn . Let M ′ (n, L) denote the total number of elementary symmetric functions eI2k together with non-constant polynomials cIS (I ∈ Tn , S ⊂ {0, . . . , ρ(I, L) − 1}) generated by this construction. Then M ′ (n, L) = O(nL) Proof. The number of elementary symmetric functions eI2k generated in the construction has already been shown to be O(n) in Proposition 4.4. We now consider the auxiliary non-constant polynomials cIS . In the recursive application of the quadratic factorized convolution along the binary decomposition tree Tn , for each interval I ∈ Tn , we have defined ρ(I, L) = #{k ≥ 0 | 2k ≤ min(|I|, 2L )} = min(⌊log2 (|I|)⌋, L) + 1 As a consequence, only elementary symmetric functions of degrees 2k with k < ρ(I, L) can appear in the Lucas factorization at the node I. Hence, each nonconstant polynomial cIS is indexed by a non-empty subset S ⊂ {0, . . . , ρ(I, L) − 1} Using the estimate of Lemma 5.2 for the combinatorial number X C(n, L) = (2ρ(I,L) − 1) I∈Tn
we obtain that the total number of non-constant polynomials cIS is in O(nL). Combining both contributions yields M ′ (n, L) = O(nL). □ For each weight 0 ≤ t ≤ n, as in Theorem 3.5 and Theorem 4.5, we encode the recursion based on the quadratic factorized convolution identities along the balanced binary tree Tn as a lifted Hamming ideal, which we call the Quadratic Factorized Convolution Hamming ideal of weight t. The number of auxiliary variables required to define such an ideal is O(nL), by Proposition 5.3, and all its generators have degree at most 2. Note that, although the Factorized Convolution Hamming ideal requires fewer auxiliary variables, its generators have higher degree. We will refer to the Convolution, Factorized Convolution, and Quadratic Factorized Convolution Hamming ideals as C-Hamming, FC-Hamming, and QFCHamming ideals, respectively. In our computational experiments, we will compare the performance of these schemes on random binary linear codes with cryptographic parameters. 6. Syndrome Decoding Problem and Information Sets Let 0 ≤ k ≤ n and consider the binary vector spaces V = Fn2 and W = Fn−k . 2 A binary linear code of dimension k and length n is by definition a k-dimensional subspace C ⊂ V . Any such code is defined as C = Ker (L), where L : V → W is a linear map of maximal rank. We call L a parity-check mapping of the code C. Given a vector v ∈ V , we define the syndrome of v as the image s = L(v) ∈ W . Consider the polynomial algebra R = F2 [x1 , . . . , xn ], and denote by l1 , . . . , ln−k ∈ R the n−k
16
R. LA SCALA, M. MARCHESIN, AND S.K. TIWARI
independent linear forms defining L. Let s = (s1 , . . . , sn−k ) ∈ W be a syndrome. We define the linear ideal Ls = ⟨l1 − s1 , . . . , ln−k − sn−k ⟩ ⊂ R We call Ls the syndrome ideal corresponding to s. Note that VF2 (Ls ) = L−1 (s). For any weight 0 ≤ t ≤ n, let It + F be the Hamming ideal of weight t, so that VF2 (It ) = Ht . The syndrome decoding ideal of syndrome s and weight t is defined as the sum Js,t = Ls + It It follows that Hs,t = VF2 (Js,t ) = L−1 (s) ∩ Ht . We call Hs,t the syndrome decoding variety corresponding to s and t. The Syndrome Decoding Problem, in its exact and bounded-weight variants, is a fundamental computational problem in coding theory and code-based cryptography. In particular, the security of the McEliece cryptosystem and several of its variants relies on the presumed hardness of recovering a vector v ∈ V of weight wt(v) ≤ t from its syndrome L(v) = s. In this paper, we focus on the exact variant of the Syndrome Decoding Problem, that is, wt(v) = t since the exact and bounded-weight formulations are polynomially equivalent. Considering the system of polynomial equations corresponding to the vector equations L(v) = s and wt(v) = t, one has that solving the Exact Syndrome Decoding Problem, briefly ESDP, amounts to computing some element of the variety Hs,t . By definition, the minimum distance of the code C is d = min{wt(u) | u ∈ C, u ̸= 0} It follows immediately from the definition of the minimum distance that two distinct error vectors of weight at most t = ⌊(d − 1)/2⌋ cannot have the same syndrome. The integer t is called the error-correcting capability of the code C. In what follows, we assume that the parameter t defining the syndrome variety Hs,t is the error-correcting capability of C. Therefore, for every syndrome s ∈ W , #Hs,t ≤ 1 In the McEliece cryptosystem, encryption with respect to the code C is performed by mapping u ∈ C 7→ w = u + v ∈ V , where v ∈ Hs,t and s = L(w). An unauthorized decryption u = w − v thus amounts to solving the ESDP instance associated with syndrome s. A fundamental concept in the complexity analysis of the Syndrome Decoding Problem is the notion of Information Set. With respect to a fixed variable ordering, we apply Gaussian elimination, or equivalently compute a Gröbner basis, to the code equations l1 = 0, . . . , ln−k = 0 This yields a partition of the variable set {x1 , . . . , xn } into a set of n − k pivot variables and a set of k free variables. With respect to the chosen variable ordering, an Information Set of the code C is by definition the set of free variables. Different variable orderings generally yield different Information Sets. Given an Information Set of the code C, an Evaluation Set is any subset of it.
HAMMING IDEALS AND GRÖBNER BASES FOR SYNDROME DECODING
17
To solve an ESDP instance, namely to compute Hs,t = VF2 (Js,t ), one may compute a Gröbner basis G of the ideal Js,t + F where F = ⟨x21 − x1 , . . . , x2n − xn ⟩ is the field equations ideal of R. Indeed, since we assume that #Hs,t ≤ 1, for any monomial ordering of R we have {x1 − v1 , . . . , xn − vn } if Hs,t = {(v1 , . . . , vn )}, G= {1} if Hs,t = ∅ To compute a Gröbner basis of the ideal Js,t +F is, in general, a computationally demanding task for parameter sets arising in practical code-based cryptography. Since Js,t = Ls + It one problem is that the Hamming ideal It + F is generated by high-degree polynomials, which may significantly increase the Gröbner basis solving degree. A possible way to mitigate this issue is to replace It + F with a suitable lifted Hamming ideal, such as C-Hamming, FC-Hamming, and QFC-Hamming ideals, introduced in the previous sections. A second challenge is the potentially large number of variables involved. Fix an Evaluation Set and, for ease of notation, assume that it is {x1 , . . . , xr }. Let u = (u1 , . . . , ur ) ∈ Fr2 with wt(u) ≤ t, and define an evaluation ideal Eu = ⟨x1 − u1 , . . . , xr − ur ⟩ By definition of Evaluation Set, the partial assignment encoded by Eu is consistent with the syndrome constraints encoded by Ls . Equivalently, VF2 (Eu + Ls ) ̸= ∅ or, in ideal-theoretic terms, 1 ∈ / Eu + Ls . If Hs,t cannot be computed in practice, we can consider the identity [ Hs,t = VF2 (Js,t + Eu ) wt(u)≤t
Hence, instead of solving a single polynomial system in n variables, one may solve a family of systems, indexed by the vectors u ∈ Fr2 with wt(u) ≤ t, each involving only n − r variables. We refer to this approach as a hybrid strategy for the Exact Syndrome Decoding Problem. Fix a vector u = (u1 , . . . , ur ) ∈ Fr2 such that wt(u) ≤ t. We now study how assigning the variables x1 , . . . , xr of the Evaluation Set to the values u1 , . . . , ur , and thereby eliminating them from the system, affects the computation of VF2 (Js,t +Eu ). Consider the injective polynomial map ψu : Fn−r → Fn2 such that 2 (v1 , . . . , vn−r ) 7→ (u1 , . . . , ur , v1 , . . . , vn−r ) Put t′ = t − wt(u) and denote by Ht′′ ⊂ Fn−r the Hamming variety of weight t′ . It 2 is immediate that ψu (Ht′′ ) = Ht ∩ ψu (Fn−r ) 2 where ψu (Fn−r ) = VF2 (Eu ). 2 The algebraic counterpart of this result is obtained as follows.
18
R. LA SCALA, M. MARCHESIN, AND S.K. TIWARI
Proposition 6.1. Denote R′ = F2 [xr+1 , . . . , xn ] and let F ′ be the field equations ideal of the subalgebra R′ ⊂ R. Consider the surjective algebra homomorphism φu : R → R′ such that ui if i ≤ r, xi 7→ xi otherwise Note that Eu = Ker φu and ψu is the polynomial map corresponding to the algebra homomorphism φu , namely φu (f )(v) = f (ψu (v)) for all f ∈ R and v ∈ Fn−r . We have that 2 It′′ + F ′ = φu (It + Eu + F ) where It′′ + F ′ ⊂ R′ is the Hamming ideal of weight t′ . Proof. It is sufficient to consider the variety identity ψu (Ht′′ ) = Ht ∩ ψu (Fn−r ), 2 together with the fact that It′′ +F ′ , It +F and Eu +F are radical ideals corresponding to varieties Ht′′ , Ht and ψu (Fn−r ), respectively. □ 2 By defining L′s,u = φu (Ls ) and ′ ′ ′ ′ ′ Js,t ′ ,u = Ls,u + It′ , Hs,t′ ,u = VF2 (Js,t′ ,u )
we obtain ′ ′ Js,t ′ ,u + F = φu (Js,t + Eu + F )
or equivalently n−r ′ ψu (Hs,t ) ′ ) = Hs,t ∩ ψu (F2
where ψu (Fn−r ) = VF2 (Eu ). 2 This identity reduces the Exact Syndrome Decoding Problem, namely the com′ putation of the syndrome variety Hs,t , to the computation of the varieties Hs,t ′ ,u r ′ corresponding to each choice of u ∈ F2 with wt(u) ≤ t and t = t − wt(w). We refer ′ ′ to Js,t ′ ,u and Hs,t′ ,u as the reduced syndrome decoding ideal and reduced syndrome decoding variety, respectively. 7. An ISD-like strategy A more precise notation for the evaluation ideal should indicate its dependence on the choice of an Evaluation Set S = {xi1 , . . . , xir } ⊂ X = {x1 , . . . , xn }. Accordingly, we define Eu,S = ⟨xi1 − u1 , . . . , xir − ur ⟩. ′ ′ Similarly, we write Js,t ′ ,u,S and Hs,t′ ,u,S to make their dependence on S explicit. ′ We have shown that to compute Hs,t is equivalent to compute Hs,t ′ ,u,S for a r fixed Evaluation Set S and for all vectors u ∈ F2 , wt(u) ≤ t. We have called this approach an hybrid strategy. Since, in the Syndrome Decoding Problem, the weight t denotes the errorcorrecting capability of the code C, this parameter is typically small compared to the code length n. Therefore, it is generally more efficient to fix a weight t̄ ≤ min(r, t) ′ r and check whether Hs,t ′ ,u,S ̸= ∅ for some vector u ∈ F2 with wt(u) = t̄. If this is not the case, the Evaluation Set S is updated. We call this approach an ISD-like strategy, inspired by Information Set Decoding methods.
HAMMING IDEALS AND GRÖBNER BASES FOR SYNDROME DECODING
19
We remark that, in ISD methods, an Evaluation Set typically contains an Information Set (r ≥ k), thereby reducing the decoding step to linear algebra. In our approach, instead, an Evaluation Set is contained in an Information Set (r ≤ k), since we allow the solution of non-linear polynomial systems, for instance via Gröbner basis techniques. An ISD-like strategy is described by the following algorithm. We assume that the parameters s, t are such that #Hs,t = 1. Algorithm 7.1 GBDecode Require: Ideal Js,t ⊂ R = F2 [X], parameters r ≤ k and t̄ ≤ min(r, t) Ensure: Unique vector v ∈ Fn2 such that Hs,t = {v} 1: Set t′ = t − t̄ 2: while true do 3: Sample uniformly an Evaluation Set S = {xi1 , . . . , xir } ⊂ X 4: Let S c = {xj1 , . . . , xjn−r } be the complement of S 5: for each u ∈ Fr2 with wt(u) = t̄ do ′ c ′ 6: Construct a generating set for the ideal Js,t ′ ,u,S ⊂ R = F2 [S ] ′ ′ 7: Compute a Gröbner basis G of the ideal Js,t′ ,u,S + F ′ } then 8: if G = {xj1 − v1′ , . . . , xjn−r − vn−r 9: Reconstruct v = (v1 , . . . , vn ) by setting 10: viα = uα (1 ≤ α ≤ r), vjβ = vβ′ (1 ≤ β ≤ n − r) 11: return v 12: end if 13: end for 14: end while In the above algorithm, the Evaluation Set S is obtained by first sampling an Information Set {xi1 , . . . , xik }, and then setting S = {xi1 , . . . , xir } (r ≤ k). This is done by extracting the free variables of the linear system defining the code C, namely l1 = 0, . . . , ln−k = 0 after performing Gaussian elimination on a randomly permuted ordering of the variable set X = {x1 , . . . , xn }. We will show that, under a unit-cost model for Gröbner basis computations, the ISD-like strategy with t̄ = 0 requires no more such computations than the hybrid strategy. Recall that the latter fixes the Evaluation Set S and then performs an exhaustive search over all vectors u ∈ Fr2 satisfying wt(u) ≤ t. Proposition 7.1. A single random choice of the Evaluation Set S in algorithm GBDecode, leads to successful recovery of v ∈ Hs,t with probability t n−t P (t̄) =
t̄
r−t̄ n r
Proof. Denote S = {xi1 , . . . , xir } and u = (vi1 , . . . , vir ). A single iteration of the algorithm succeeds when the uniformly random set S is such that wt(u) = t̄. Since wt(v) = t, there are exactly t coordinates of v equal to 1 and n − t coordinates equal to 0. Therefore, a successful Evaluation Set S is obtained by
20
R. LA SCALA, M. MARCHESIN, AND S.K. TIWARI
choosing t̄ variables among the t positions where v has value 1 and r − t̄ variables among the n − t remaining positions. The number of successful choices is thus t n−t t̄ r − t̄ Since the total number of subsets of {x1 , . . . , xn } of cardinality r is nr , the claimed probability follows. □ Given the success probability P (t̄), the expected number of Gröbner basis computations performed by the GBDecode algorithm, that is, the average cost of this algorithm under the assumption that each Gröbner basis has unit cost, is given by n r r 1 r t̄ = t n−t C(t̄) ≈ · P (t̄) t̄ t̄ r−t̄ Proposition 7.2. The expected cost C(t̄) of algorithm GBDecode is minimized at t̄ = 0. Proof. It suffices to minimize r t̄ t n−t t̄ r−t̄
F (t̄) =
since nr does not depend on t̄. For integer arguments, the ratio of consecutive terms is given by n−t r t F (t̄ + 1) r−t̄ t̄+1 t̄ R(t̄) = = r · t · n−t F (t̄) t̄ t̄+1 r−t̄−1 =
r − t̄ t̄ + 1 n − t − r + t̄ + 1 n − t − r + t̄ + 1 · · = t̄ + 1 t − t̄ r − t̄ t − t̄
We have F (t̄ + 1) > F (t̄) if and only if R(t̄) > 1, that is n−r+1 2 Since t is, by hypothesis, the error-correction capability guaranteeing uniqueness of the solution to the Syndrome Decoding Problem, the code C has minimum distance d ≥ 2t + 1. By the Singleton bound, we have d ≤ n − k + 1, and hence 2t + 1 ≤ n − k + 1, that is n−k t≤ 2 Since r ≤ k, we obtain n − t − r + t̄ + 1 > t − t̄ ⇐⇒ t̄ > t −
t−
n−r+1 n−k+1 ≤t− 2 2
Moreover, using t ≤ n−k 2 we get t−
n−k+1 n−k n−k+1 1 ≤ − =− <0 2 2 2 2
Thus the inequality t̄ > t − n−r+1 holds for every t̄ ≥ 0, so F (t̄ + 1) > F (t̄) for all 2 0 ≤ t̄ < min(r, t). Hence F (t̄) is strictly increasing and its minimum is attained at t̄ = 0. □
HAMMING IDEALS AND GRÖBNER BASES FOR SYNDROME DECODING
21
We finally compare the complexity of the ISD-like strategy of the GBDecode algorithm, run with the optimal parameter t̄ = 0 established in Proposition 7.2, with the complexity of the hybrid strategy, given by X r C′ = t̄ 0≤t̄≤min(r,t)
Proposition 7.3. It holds that n ′ r n−t ≤ C r
C(0) = with strict inequality whenever r, t ≥ 1. Proof. Since
n n!(n − t − r)! r = n−t = (n − r)!(n − t)! r
n t n−r t
we may rewrite n t n−r t
C(0) =
Consider now the Vandermonde’s identity, X rn − r n = t t̄ t − t̄ 0≤t̄≤t where rt̄ = 0 for t̄ > r, so the sum effectively ranges over 0 ≤ t̄ ≤ min(r, t). As in the proof of Proposition 7.2, the code C has minimum distance d ≥ 2t + 1. Moreover, by the Singleton bound, we have d ≤ n − k + 1 and therefore n−r n−k ≤ t≤ 2 2 since r ≤k. It follows that t lies in the increasing region of the unimodal sequence i 7→ n−r . Consequently, for every 0 ≤ t̄ ≤ t, we have t − t̄ ≤ t ≤ n−r i 2 , and hence n−r n−r ≤ t − t̄ t Substituting this estimate into Vandermonde’s identity yields X X n r n−r n−r r n−r = ≤ = C′ t t̄ t − t̄ t t̄ t 0≤t̄≤min(r,t) 0≤t̄≤min(r,t) n−r Hence, dividing by t > 0, we obtain C(0) ≤ C ′ . Finally, assume r, t ≥ 1. Since t − 1 < t ≤ (n − r)/2, we have n−r n−r < t−1 t r while 1 = r > 0. Therefore the inequality in the Vandermonde sum is strict, which implies C(0) < C ′ . □ Note that the classical Information Set Decoding methods (see, for instance, [9]) essentially correspond to choosing r = k. In particular, also setting t̄ = 0 in algorithm GBDecode reduces to the Prange algorithm [21], which pioneered the ISD paradigm.
22
R. LA SCALA, M. MARCHESIN, AND S.K. TIWARI
The above results suggest that a Prange-like strategy is a natural candidate for the optimization of the GBDecode algorithm. This conclusion, however, relies on the simplifying assumption that all Gröbner basis computations have the same cost. In practice, one should investigate how this cost varies with the choice of the parameter r ≤ k and the residual weight t′ = t − t̄. A more refined analysis must therefore account for the actual cost of the individual Gröbner basis computations. In the following sections, we start addressing this issue by analyzing the average number of Gröbner basis calls required by the GBDecode algorithm when implemented using the MultiSolve procedure [12, 13]. In fact, the number of such calls provides a first approximation of the computational complexity of the algorithm. We then experimentally investigate the effect of tuning GBDecode for a random binary linear code with the NIST Security Category 1 parameter set of the Classic McEliece cryptosystem. 8. MultiSolve Algorithm In this section, we briefly review the MultiSolve algorithm, a general method for solving polynomial systems having at most one solution over a finite field. The algorithm combines Gröbner basis computations up to a prescribed solving degree with a recursive branching strategy known as the “multistep strategy”. Although the algorithm is defined over arbitrary finite fields, we present it here only over the binary field F2 , consistently with the framework adopted throughout this paper. For a complete description of the algorithm, we refer the reader to [13]. Let R = F2 [x1 , . . . , xn ] and let F = ⟨x21 − x1 , . . . , x2n − xn ⟩ be the field equations ideal. Consider J = ⟨f1 , . . . , fm ⟩ ⊂ R an ideal such that #VF2 (J) ≤ 1. Since J + F is a radical ideal, a Gröbner basis G of the ideal J + F, with respect to any monomial order of R, is either G = {1} if VF2 (J) = ∅, or G = {x1 − v1 , . . . , xn − vn } where v = (v1 , . . . , vn ) ∈ Fn2 such that VF2 (J) = {v}. Hence, in both cases, all polynomials in the Gröbner basis have degree at most one. Let 0 ≤ ℓ ≤ n and let u = (u1 , . . . , uℓ ) ∈ Fℓ2 . We define the evaluation ideal Eu = ⟨x1 − u1 , . . . , xℓ − uℓ ⟩ and the corresponding ideal Ju = J + Eu . By convention, when ℓ = 0, we set E() = 0 and J() = J. If VF2 (J) = {v}, then VF2 (J) if u = (v1 , . . . , vℓ ), VF2 (Ju ) = ∅ otherwise Therefore, we have VF2 (Ju ) = VF2 (J(u,0) ) ∪ VF2 (J(u,1) ) which motivates a binary divide-and-conquer strategy along the tree of partial assignments. Given a generating set H of an ideal and an integer d ≥ 0, we denote by Groebner(H, d) the truncated Gröbner basis computation with degree bound d, namely the computation obtained by restricting the Macaulay matrices to degree at most d. For a sufficiently large value of d, this procedure computes a complete Gröbner basis. The smallest such value is called a solving degree of H.
HAMMING IDEALS AND GRÖBNER BASES FOR SYNDROME DECODING
23
A first subroutine of algorithm MultiSolve is the GroebnerSafe procedure, which performs a truncated Gröbner basis computation up to a prescribed degree d, limited by a timeout τ . It returns the flag tame if a complete Gröbner basis is obtained, and wild otherwise. Algorithm 8.1 GroebnerSafe Require: Generating set H of J + F ; integer d; timeout τ > 0 Ensure: (wild, ∅) or (tame, G) with G = Groebner(H, d) and maxdeg(G) ≤ 1 1: Compute G ← Groebner(H, d) within timeout τ 2: if the computation terminates within τ and maxdeg(G) ≤ 1 then 3: return tame, G 4: end if 5: return wild, ∅ The MultiSolve algorithm is a depth-first recursive procedure. Given a partial assignment u ∈ Fℓ2 of the first ℓ variables, it uses the predictive function Oracle to decide whether to invoke GroebnerSafe. If a Gröbner basis of Ju + F cannot be computed, the algorithm recursively explores the two possible binary extensions of the vector u. The objects H, Oracle, d and τ are treated as global parameters. Algorithm 8.2 MultiSolve(u) Require: A vector u ∈ Fℓ2 (0 ≤ ℓ ≤ n) Ensure: A Gröbner basis of Ju + F 1: G ← {x1 − u1 , . . . , xℓ − uℓ } ∪ H 2: if Oracle(G, ℓ) = tame then 3: status, G ← GroebnerSafe(G, d, τ ) 4: if status = tame then 5: return G 6: end if 7: end if 8: for b ∈ F2 do 9: G′ ← MultiSolve((u, b)) 10: if maxdeg(G′ ) = 1 then 11: return G′ 12: end if 13: end for 14: return {1} Termination is guaranteed since, in the worst case, after n recursive steps all variables are assigned. In practice, however, the recursion is typically terminated much earlier, as GroebnerSafe may already compute a Gröbner basis of Ju +F at an intermediate node of the search tree. The algorithm generalizes both exhaustive search over Fn2 , obtained for an oracle that always returns wild, and the classical hybrid strategy, recovered by the oracle wild if ℓ < B, OracleHB (G, ℓ) = tame otherwise
24
R. LA SCALA, M. MARCHESIN, AND S.K. TIWARI
We briefly recall the complexity analysis of the MultiSolve algorithm given in [13], in the simplified setting of a binary finite field. The recursive calls of MultiSolve form a full binary tree T , where each internal node has exactly two children corresponding to the two recursive calls generated by a wild case. This tree represents the execution in the case where no solution exists, since all branches must be explored. If a solution exists, the algorithm stops as soon as a successful branch is found, and only a portion of the tree is visited. Proposition 8.1. Let N , M , and L denote the total number of nodes, internal nodes, and leaves of a full binary tree T , respectively. The following relations hold N = 2L − 1, M = L − 1 The above is a well-known result. For a proof in the general (non-binary) case, we refer the reader to [13]. Definition 8.2. An oracle function Oracle is accurate if it correctly predicts the wild status of a GroebnerSafe call. It is perfect if it correctly predicts the outcome of every GroebnerSafe call, whether tame or wild. Such a perfect oracle minimizes the total number of GroebnerSafe executions among all possible oracle functions. We also define OracleT as the oracle function that always returns the tame status. It represents the worst-case behavior of MultiSolve, as GroebnerSafe is invoked at every node of the recursion tree. On the other hand, a perfect oracle represents the best-case scenario, where only the necessary calls to GroebnerSafe are performed. For simplicity, in the following analysis, we assume that the polynomial systems under consideration have no solutions. Hence, MultiSolve explores the full recursion tree. Proposition 8.3. Let N be the number of GroebnerSafe executions under OracleT and let L be the number of executions under a perfect oracle. Then 1 N =2− L L In particular, the maximum possible speedup is strictly smaller than a factor of 2. Proof. Under OracleT, every node of the full binary recursion tree T requires a GroebnerSafe execution, while a perfect oracle avoids all internal nodes and requires only the computations associated with the leaves. Hence, N and L are respectively the number of nodes and leaves of T . Since T is a full binary tree, we have N = 2L − 1, and the result follows. □ This result extends to arbitrary finite fields [13]. The preceding analysis shows that the cost of MultiSolve is essentially dominated by the number of tame nodes in the recursion tree, since each of them corresponds to a complete Gröbner basis computation performed by GroebnerSafe. Since all calls to GroebnerSafe are subject to the same fixed timeout, we adopt a simplified cost model in which each execution of GroebnerSafe has unit cost. In the next section, we apply MultiSolve within the GBDecode algorithm for computing Gröbner bases. For different choices of parameters, such as r ≤ k, the combinatorial cost C(t̄) of the algorithm is therefore adjusted by a multiplicative factor given by the average number of tame cases encountered during the execution of MultiSolve. Note that, when applying MultiSolve to GBDecode, the
HAMMING IDEALS AND GRÖBNER BASES FOR SYNDROME DECODING
25
number of variable assignments with b = 1 must be bounded by the residual weight t′ = t − t̄. 9. Experimental results We have implemented in Magma [6] the C-Hamming, FC-Hamming, and QFCHamming ideals introduced in Sections 3, 4, and 5, together with the MultiSolve and GBDecode algorithms. We investigate the performance of this algebraic approach when the solving step of GBDecode is carried out by MultiSolve. All experiments use the NIST Security Category 1 parameter set of the Classic McEliece cryptosystem [5], namely n = 3488, k = 2720, t = 64 for a binary linear code drawn uniformly at random with these parameters. No structure of the code is exploited by GBDecode. The expected number of additional vectors of weight t having the same syndrome is given by (see, for instance, [10]) n t −1 ≈ 2−312 2n−k Thus, with overwhelming probability, there is no other vector of weight t with the same syndrome, so the solution is unique, as assumed in Section 7. Setup. One run of the implementation corresponds to one iteration of the while loop of GBDecode. An Evaluation Set S = xi1 , . . . , xir ⊂ X is obtained from the free variables resulting from Gaussian elimination applied to a randomly permuted ordering of X, and one vector u ∈ Fr2 with wt(u) = t̄ is examined. For t̄ = 0, this vector is u = 0. For t̄ > 0, it is chosen uniformly at random among the rt̄ vectors of weight t̄. The algorithm GBDecode examines all such vectors, resulting in the combinatorial cost C(t̄) defined in Section 7. A single integer seed determines the binary linear code, the error vector, the Evaluation Set, and the vector u, making each run exactly reproducible. The same seeds are used for the three Hamming ideals, allowing them to be compared instance by instance. Each configuration is run on 100 instances for each value of r, namely r = k−10 = 2710 and r = k = 2720, using multiple CPUs. The parameters of GroebnerSafe are a timeout τ = 20 minutes and a degree bound d = 20. Note that for the FC-Hamming ideal, the maximal degree of the generators is 10. The oracle used is OracleT, so that the nodes of the recursion tree of MultiSolve are exactly the calls to GroebnerSafe: the wild calls are its internal nodes and the tame calls its leaves, as in Section 8. A call is wild either because the timeout expires or because Groebner(H, d) is computed but is not linear. The MultiSolve recursion progressively assigns values to at most k − r variables in the Information Set that do not belong to S. All results are obtained using the degree reverse lexicographic order XRev-BitFold, in which the X-variables come first, in decreasing order of their index, followed by the auxiliary variables. A second order, XRev-PeakFold, differing only in the ordering of the auxiliary variables, produced almost identical recursion trees. The computations were run with Magma V2.29-5 on an Intel Xeon Gold 6230R at 2.10 GHz, with 26 physical cores and 256 GB of memory.
26
R. LA SCALA, M. MARCHESIN, AND S.K. TIWARI
One iteration of GBDecode at r = k − 10. For r = k − 10 = 2710, with n−r = 778 remaining variables and residual weight t′ = 64 (Prange case, t̄ = 0), the three Hamming ideals yield the systems reported in Table 1. They are constructed using a recursive binary decomposition of the remaining variables into halves, with L = ⌈log2 (max(t′ , n − r − t′ ) + 1)⌉ − 1 = 9 as prescribed in Section 2. In every instance and for each of the three ideals, the call to GroebnerSafe at the root returned wild, its Gröbner basis not being completed within the timeout τ . This is precisely the situation MultiSolve is designed for: assigning few variables replaces the original system with a family of simpler ones. The number of tame calls determines the cost of one iteration, as in Section 8. Table 1 reports the average number of tame calls over the 100 instances, together with the mean tree depth and the actual solving degree observed in the corresponding Gröbner basis computations performed by Magma. The FC-Hamming ideal required the fewest tame calls on average, while the C-Hamming ideal did not complete any iteration within 16 hours. A tame GroebnerSafe run with the FC-Hamming ideal takes about 10 minutes on average.
Hamming ideal C-Hamming FC-Hamming QFC-Hamming
system at the root vars gens maxdeg d 7544 6776 2 20 2844 2076 10 20 4133 3365 2 20
tame — 5.6 7.6
recursion tree depth sol. deg. — — 2.6 10 3.5 3
Table 1. The three Hamming ideals for r = 2710 and t̄ = 0. The table reports the systems at the root of the recursion tree (excluding the n − k linear equations of the code and the field equations) and the corresponding recursion-tree statistics of MultiSolve for a single iteration of GBDecode.
FC-Hamming QFC-Hamming
0 0 0
1 0 0
2 3.03 2.50
depth 3 4 1.27 1.33 2.00 1.20
5 — 1.33
6 — 0.53
Table 2. Average number of tame calls at each depth of the recursion tree, at r = 2710 and t̄ = 0, over all runs. A dash means that no tree reaches that depth. Recovering the Prange algorithm at r = k. At r = k and t̄ = 0 the algorithm GBDecode reduces to the Prange algorithm [21], as observed in Section 7. The Evaluation Set is then a whole Information Set, all the remaining X-variables are determined by the code equations, and only the weight condition is left to check. Using FC-Hamming ideal, our runs show exactly this: on every instance, the recursion tree consists of a single tame node. For a random instance, the call to GroebnerSafe terminates with an average computing time of 1 second. This shows that the computational cost of our approach can be meaningfully compared
HAMMING IDEALS AND GRÖBNER BASES FOR SYNDROME DECODING
27
with that of classical ISD methods. Note that, for the considered parameters, the combinatorial cost of Prange is C(0) = 2142.78 . Choosing r and t̄. Table 3 gives, for r = k = 2720 and r = k − 10 = 2710, the average number of tame calls with the FC-Hamming ideal and the expected combinatorial cost C(t̄) of Section 7. Lowering r from k to k − 10 reduces C(0) by 1.24 bits, but the average number of tame calls grows from 1 to 5.6, so that the total cost increases. Raising t̄ to 2 and 30 gives 6.1 and 6.9 tame calls on average, while C(t̄) grows by 7 and 117 bits. We conclude that, for the considered parameters n, k, t, the choice r = k and t̄ = 0 is the most efficient one. r t̄ tame log2 C(t̄)
2720 0 1 142.78
2710 0 5.6 141.54
2710 2 6.1 148.53
2710 30 6.9 258.66
Table 3. Average number of tame calls with the FC-Hamming ideal, over the 100 instances, and expected cost C(t̄). These experiments show the two components of the cost of GBDecode. An Evaluation Set strictly contained in an Information Set gives a combinatorial gain, of 1.24 bits at r = k−10, together with an algebraic cost in the inner loop, measured by the tame calls of MultiSolve. The balance between the two depends on the Hamming ideal and on the solver, as the differences between the three ideals show. A Hamming ideal requiring fewer tame calls, or a faster solver, would reduce the algebraic cost and could make smaller values of r competitive. 10. Conclusions and further directions We have presented an algebraic approach to the Syndrome Decoding Problem, introducing various ideals defining the Hamming variety based on the theory of elementary symmetric functions and factorizations derived from Lucas’ theorem. These constructions are integrated with the Information Set Decoding paradigm. The resulting GBDecode algorithm introduces a tunable trade-off between combinatorial search and algebraic solving, while MultiSolve replaces a hard polynomial system with a family of simpler systems obtained by progressively assigning variables. Experiments on random binary linear codes with Classic McEliece Category 1 parameters show that the choice of the Hamming ideal significantly affects the computational cost. For the considered parameters, the FC-Hamming ideal required fewer Gröbner basis computations, while the Prange-like configuration r = k and t̄ = 0 yielded the lowest cost. These results demonstrate the feasibility of the proposed framework and motivate further investigation of the Hamming models, solving strategies, and parameter optimization. Acknowledgements The authors would like to thank Lorenzo D’Ambrosio and Gabriele Mancini for carefully reading parts of the manuscript and for their helpful comments and suggestions. The first author gratefully acknowledges Raffaele Vitolo for his hospitality
28
R. LA SCALA, M. MARCHESIN, AND S.K. TIWARI
and support during a research stay at the University of Salento. The stimulating discussions, valuable insights, and constructive suggestions offered during this stay played an important role in shaping and refining this work.
References [1] Aguilar Melchor, C.; Aragon, N.; Bettaieb, S.; Bidoux, L.; Blazy, O.; Bos, J.; Deneuville, J.-C.; Dion, A.; Gaborit, P.; Lacan, J.; Persichetti, E.; Robert, J.-M.; V’eron, P.; Z’emor, G., Hamming Quasi-Cyclic (HQC), NIST Post-Quantum Cryptography Standardization, Round 4 submission, 2023. Available at https://pqc-hqc.org. [2] Aragon, N.; Barreto, P.S.L.M.; Bettaieb, S.; Bidoux, L.; Blazy, O.; Deneuville, J.-C.; Gaborit, P.; Ghosh, S.; Gueron, S.; G”uneysu, T.; Aguilar Melchor, C.; Misoczki, R.; Persichetti, E.; Richter-Brockmann, J.; Sendrier, N.; Tillich, J.-P.; Vasseur, V.; Z’emor, G., BIKE: Bit Flipping Key Encapsulation, NIST Post-Quantum Cryptography Standardization, Round 4 submission, 2022. Available at https://bikesuite.org. [3] Becker, A.; Joux, A.; May, A.; Meurer, A., Decoding random binary linear codes in 2n/20 : How 1 + 1 = 0 improves information set decoding, in EUROCRYPT 2012, Lect. Notes Comput. Sci., vol. 7237, Springer, 2012, 520–536. [4] Berlekamp, E.R.; McEliece, R.J.; van Tilborg, H.C.A., On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory, 24 (1978), no. 3, 384–386. [5] Bernstein, D.J.; Chou, T.; Lange, T.; von Maurich, I.; Misoczki, R.; Niederhagen, R.; Persichetti, E.; Peters, C.; Schwabe, P.; Sendrier, N.; Szefer, J.; Wang, W., Classic McEliece: conservative code-based cryptography, NIST Post-Quantum Cryptography Standardization, Round 4 submission, 2022. Available at https://classic.mceliece.org. [6] Bosma, W.; Cannon, J.J.; Playoust, C., The Magma algebra system. I. The user language. J. Symbolic Comput., 24 (1997), 235–265. [7] Caminata, A.; Cartor, R.; Meneghetti, A.; Mora, R.; Pellegrini, A., Quadratic Modelings of Syndrome Decoding, in Post-Quantum Cryptography – PQCrypto 2025, Lect. Notes Comput. Sci., vol. 15577, Springer, 2025, 35–70. [8] Dumer, I., On minimum distance decoding of linear codes, in Proc. 5th Joint Soviet-Swedish International Workshop on Information Theory, 1991, 50–52. [9] Elbro, F.; Weger, V., Can we speed up information set decoding by using extension field structure?, Cryptogr. Commun., 2026, 1–31. [10] Gassner, N.; Lieb, J.; Mazumder, A.; Schaller, M., Information-set decoding for convolutional codes, Des. Codes Cryptogr., 93 (2025), 3481–3505. [11] Ghorpade, S.R., A note on Nullstellensatz over finite fields, in Contributions in Algebra and Algebraic Geometry, Contemp. Math., vol. 738, Amer. Math. Soc., Providence, RI, 2019, 23–32. [12] La Scala, R.; Pintore, F.; Tiwari, S.K.; Visconti, A., A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium, Finite Fields Appl., 98 (2024), Paper No. 102452, 33 pp. [13] La Scala, R.; Tiwari, S.K., Oracle-Based multistep strategy for solving polynomial systems over finite fields and algebraic cryptanalysis of the Aradi cipher, Adv. Math. Commun., 23 (2026), 255–273. [14] Macdonald, I.G., Symmetric Functions and Hall Polynomials, 2nd ed., Oxford Classic Texts in the Physical Sciences, Clarendon Press, Oxford University Press, Oxford, 2015. e 0.054n ), in ASI[15] May, A.; Meurer, A.; Thomae, E., Decoding random linear codes in O(2 ACRYPT 2011, Lect. Notes Comput. Sci., vol. 7073, Springer, 2011, 107–124. [16] May, A.; Ozerov, I., On computing nearest neighbors with applications to decoding of binary linear codes, in EUROCRYPT 2015, Lect. Notes Comput. Sci., vol. 9056, Springer, 2015, 203–228. [17] McEliece, R.J., A public-key cryptosystem based on algebraic coding theory, Technical Report DSN Progress Report 42-44, Jet Propulsion Laboratory, 1978, 114–116. [18] Meneghetti, A.; Pellegrini, A.; Sala, M., On the equivalence of two post-quantum cryptographic families, Ann. Mat. Pura Appl., 202 (2023), no. 2, 967–991. [19] National Institute of Standards and Technology, Post-Quantum Cryptography Standardization, https://csrc.nist.gov/projects/post-quantum-cryptography.
HAMMING IDEALS AND GRÖBNER BASES FOR SYNDROME DECODING
29
[20] Niederreiter, H., Knapsack-type cryptosystems and algebraic coding theory, Probl. Control Inform. Theory, 15 (1986), no. 2, 159–166. [21] Prange, E., The use of information sets in decoding cyclic codes, IRE Trans. Inform. Theory, 8 (1962), no. 5, 5–9. [22] Shor, P.W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, in Proc. 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1994, 124–134. [23] Stern, J., A method for finding codewords of small weight, in Coding Theory and Applications, Lect. Notes Comput. Sci., vol. 388, Springer, 1988, 106–113. [24] Zajac, P., Connecting the complexity of MQ- and code-based cryptosystems, Tatra Mt. Math. Publ., 70 (2017), no. 1, 163–177. ∗ Dipartimento di Fisica, Università degli Studi di Bari “Aldo Moro”, Via Orabona 4, 70125 Bari, Italy Email address: [email protected] ∗∗ Dipartimento di Matematica, Università degli Studi di Bari “Aldo Moro”, Via Orabona 4, 70125 Bari, Italy Email address: [email protected] † Cryptography Research Centre, Technology Innovation Institute, Abu Dhabi, United Arab Emirates Email address: [email protected]