Cross-Paradigm Models of Restricted Syndrome Decoding with Application to CROSS⋆ Étienne Burle and Aleksei Udovenko
arXiv:2604.09292v1 [cs.CR] 10 Apr 2026
SnT, University of Luxembourg [email protected]
Abstract. Restricted Syndrome Decoding (ResSD) is a variant of linear code decoding problem where each of the error’s entries must belong to a fixed small set of values. This problem underlies the security of CROSS, a post-quantum signature scheme that is one of the Round 2 candidates of NIST’s ongoing additional signatures call. We show that solutions to this problem can be deduced from vectors of a particular structure and a small norm in newly constructed codes, in both Hamming and Euclidean metrics. This allows us to reduce Restricted Syndrome Decoding to both code-based (Regular Syndrome Decoding) and lattice-based problems (Closest Vector Problem, List of Short/Close Vectors), increasing the attack surface and providing new insights into the security of ResSD. We evaluate our attacks on CROSS instances both theoretically and experimentally on reduced parameters. Keywords: Post-quantum cryptography · Cryptanalysis · Restricted Syndrome Decoding · Code-based cryptography · Lattice-based cryptography · CROSS
1
Introduction
Since the discovery of Shor’s algorithm [49], the public key cryptosystems that were and are widely used can be broken by a quantum computer. That is why the US state agency NIST launched in 2017 a competitive call for designing new quantum-resistant cryptosystems, which resulted in three post-quantum standards in August 2024. While one signature is based on hash functions [33], the two others (one encryption and one signature) assume the hardness of latticebased problems [48, 39]. There is also another lattice-based signature standard [43] which should be coming soon. This led the NIST to diversify post-quantum standards in order to avoid relying on the same kind of problem. This was the aim of the new NIST call for additional signatures in 2023, whose process is currently in the second round.1 For encryption schemes, the NIST announced in March 2025 a new post-quantum standard [1] based on linear codes. This work was funded by the Luxembourg National Research Fund (FNR) via project PQseal C24/IS/18978392. 1 https://csrc.nist.gov/Projects/pqc-dig-sig/round-2-additional-signatures
⋆
Indeed, code-based problems are strong candidates for building alternative schemes. One of the remaining candidates for the ongoing signature call is CROSS [5] which is based on a variant of the syndrome decoding problem, the cornerstone of code-based cryptography. It consists in solving an underdetermined linear system of equations over a finite field, but with the additional constraint that the number of nonzero variables is bounded. The idea of using this NP-hard problem ([12]) in cryptography is not new, since the first code-based encryption scheme, the McEliece scheme [41], was published in 1978. The syndrome decoding problem has been studied a lot for a long time [42, 50, 24, 9, 34, 27, 13, 11, 40, 16, 22, 17, 19, 36, 38], and this is a testimony to its hardness. One of its variants is the regular syndrome decoding problem, where the solution is partitioned into consecutive blocks of equal length, with each block containing exactly one nonzero element. Originally introduced in [3], it has since been the subject of several particular studies [44, 31, 21, 18, 25, 36, 52]. CROSS is based on another variation of the problem called the restricted syndrome decoding problem. In this case, each of the solution’s entries must belong to a fixed small set of values. First introduced in [7, 6] and proved NPcomplete in [7, 15], it has since been studied in [15, 8, 14] and by CROSS designers themselves [4]. One can see that this problem is relatively new, and that is why NIST is looking forward to further analysis of the underlying problems of CROSS [2], as well as the ZKPoK identification protocol [8] used by the scheme. Our contribution Our primary goal is to better understand the Restricted Syndrome Decoding (ResSD) problem and expand the surface of analysis techniques applicable to (n−k)×n and a syndrome s ∈ Fn−k , the it. Given a parity-check matrix H ∈ Fq q problem consists in finding an error e ∈ Fnq such that eH⊺ = s with each entry of e belonging to a fixed subset E of Fq . Although CROSS has also a version using ResSD with a subgroup of E n , in this work we focus on the basic version (called CROSS-R-SDP). The main family of algorithms for solving the original syndrome decoding problem is called ISD (Information Set Decoding), and almost all existing algorithms for solving ResSD are adaptations of ISD. There is an exception in recent work [14] that studies algebraic techniques based on Gröbner basis, as well as hybrid attacks. We depart from these methods with several new ideas. (Reduction of ResSD to regular syndrome decoding) The first idea consists, instead of using H directly, in considering the new parity check matrix H′ = r1 H1 . . . rz H1 ∥ . . . . . . ∥ r1 Hn . . . rz Hn where Hi is the ith column of H and ri are the elements of E. One can immediately see that if e was a solution to our original ResSD problem, then if we denote e′ the vector of length zn which in the ith z-size block has exactly one 1 at the position that corresponds to the value of the ith coordinate of e, we will have 2
e′ H′ = s. So e′ is a special solution of a regular syndrome decoding instance, because its nonzero values contain only ones. We call this kind of vectors lightregular vectors. That is why we add n parity-check equations imposing a sum equal to 1 on each block (similarly to the so-called “encoding regularity” from e ∈ F(2n−k)×zn [25]). We obtain a new parity-check matrix H . We adapt some ISD q algorithms to this new particular problem, obtaining rather high complexities e as a parity-check matrix. because of the high rate of the code admitting H (Reduction of light-regular decoding (and ResSD) to CVP) Noticing that light-regular vectors also minimize the Euclidean norm among solutions, we create the lattice containing this code and convert the regular syndrome decoding problem into a closest vector problem. The idea is similar to lattice-based attacks against code-based problems using the Lee metric [32]. But the large dimension of our lattice which in addition has many short vectors makes this instance hard to solve. We nevertheless improve the attack by using a “hybrid” method consisting in “guessing” a certain number of blocks. This reduces the dimension of the lattice, and if we enumerate all vectors close to our new target, the solution will be among them. We combine this already hybrid attack with a “truncation method” consisting in guessing of a certain number of coordinates per block, giving better complexities. (Direct reductions from ResSD to ListCVP/ListSVP) Another idea is based on the fact that given a, b ∈ Fq with a ̸= 0 and b = (b, . . . , b), we can rewrite eH⊺ = s into (ae + b)H⊺ = as + bH⊺ . If we denote H′ = aH and s′ = as + bH⊺ , they both constitute an instance of ResSD with solution’s entries lying in aE + b. Thus, we can perform an affine substitution of the set of error’s values to minimize a parameter that we called the affine diameter of E. This, combined with the truncation method, leads to solutions of small Euclidean norms that allow us to use lattice-based attacks again, while preserving the dimension n of the problem. This results in a reduction of ResSD to a listclosest-vector-problem (which consists in listing the vector close up to a certain distance to the target) and to the list-shortest-vector-problem (the same, but the target is the zero vector) over lattices. Remarkably, certain parameters of ResSD instances heuristically lead to a degeneration of these list-decoding problems into basic CVP and SVP instances. This generalizes the observation of the CROSS designers [4] that ResSD with a two-element set E corresponds to a subset-sum problem. These attacks are based on statistics on the error distributions. In CROSS, the set E of values for the error is a multiplicative subgroup of Fq , which allows us to randomize the solution of the ResSD instance. This allows us to convert weak-key attacks into standard probabilistic attacks. Although CROSS insofar is the only scheme based on ResSD, our analysis would help with other potential future designs. We summarize our reductions in Table 1 and give all the complexities obtained for the CROSS parameters in Table 2. We see that the direct adaptation of ISD algorithms given in [5] remains the best attack, and thus our reductions together with basic RegSD/Lattice3
Field Restr. E Fq
Any
Fp
Any
Fp
Any
Fp
Mult. subgroup
Fp
Mult. subgroup
Problem
Parameters
Ref.
Section 3 n blocks of z entries each, enforced binary solution, deterministic CVP full-rank lattice of dimension zn, Section 4 √ volume p2n−k , norm = n, enforced binary solution, deterministic ListCVP/CVP full-rank lattice of dimension n, Subsection 5.3 √ volume pn−k , norm ≤ n·DE /2, deterministic ListCVP/CVP full-rank lattice of dimension n, Subsection 5.4 √ volume pn−k , norm ≤ n · σ(E), probabilistic ListSVP/SVP full-rank lattice of dimension n, Subsection 5.5 √ volume pn−k−1 , norm ≤ n · σ(E), probabilistic Regular SD
Table 1. Summary of reductions from a ResSD problem with parity check matrix (n−k)×n H ∈ Fq and syndrome s ∈ Fn−k with solution entries in a set E of size z. q List-CVP/List-SVP instances may degrade to CVP/SVP for some parameters, under Gaussian Heuristic. σ(E) denotes standard deviation of a random variable sampled uniformly from E. DE denotes the difference between the maximum and the minimum elements of E, as integers, up to affine substitution. The two last reductions are weak-key attacks for arbitrary restriction sets E and can be converted into general probabilistic attacks when E is a multiplicative subgroup of the field.
(n, k)
Attack
Time
Memory
Ref.
2 2220 2197 2229 2196
117
(127,76)
Shifted representations Naive ISD enumeration ISD for Regular SD Hybrid-BatchCVP Hybrid-ListCVP
143
2 poly(n) 2162 2136 226
[5, Tab.5] Proposition 4 Subsection 3.2 Subsection 4.2 Subsection 5.6
(187,111)
Shifted representations Naive ISD enumeration ISD for Regular SD Hybrid-BatchCVP Hybrid-ListCVP
2207 2319 2285 2336 2287
2169 poly(n) 2238 2201 239
[5, Tab.5] Proposition 4 Subsection 3.2 Subsection 4.2 Subsection 5.6
(251,150)
Shifted representations Naive ISD enumeration ISD for Regular SD Hybrid-BatchCVP Hybrid-ListCVP
2274 2429 2380 2450 2384
2234 poly(n) 2320 2271 252
[5, Tab.5] Proposition 4 Subsection 3.2 Subsection 4.2 Subsection 5.6
Table 2. Summary of existing and our attacks against CROSS-R-SDP instances.
4
based solving techniques do not threaten CROSS so far. We nevertheless obtain an interesting Time/Memory compromise using our reduction to List-CVP. The relevant source code and supporting materials are available at [20].2
2
Preliminaries
The finite field of size q = pk , p prime, is denoted by Fq . The symbol ≜ is used to define the object on the left side. We denote by Card (S) the cardinality of the set S. Vectors are denoted by bold lowercase letters and indexed from 1, matrices are denoted by bold capitals. For every matrix M, we denote by Mi its ith column and by Mi,j its entry in the ith row and j th column. In and 0 are, respectively, the identity matrix of size n for every integer n and the zero matrix (0 can also be the zero vector, depending on the context). The ith entry of a vector x is denoted xi . The Hamming weight of a vector u ∈ Fnq is |u|H ≜ {i ∈ {1 . . . n} | ui ̸= 0} . The Euclidean norm of a vector v ∈ Zn is v u n uX vi2 . |v|E ≜ t i=1
2.1
Linear codes
Definition 1 (Linear code). A linear code C ⊂ Fnq of dimension k is a vector subspace of Fnq of dimension k. It can be represented by two equivalent ways: whose rows are a basis of C: – With a generator matrix G ∈ Fk×n q C = xG | x ∈ Fkq (n−k)×n
that is a generator matrix of C ⊥ : – With a parity-check matrix H ∈ Fq C = y ∈ Fnq | yHT = 0 In particular, we have GHT = 0 and C does not change if its generator or parity-check matrix is multiplied on the left by an invertible matrix. Notation 1 C(G) is the linear code that admits G as a generator matrix, and C ⊥ (H) is the code that admits H as a parity-check matrix. We say that a generator matrix G is in systematic form if it is in the form (Ik , R). 2
See also https://github.com/cryptolu/Cross-Paradigm-RestrictedSD.
5
Restricted syndrome decoding There are several variations of Restricted Syndrome Decoding problems (ResSD) in the literature. Since we focus on the analysis of CROSS, we use the definition given in the specification, which we slightly generalize to include derived instances that we will analyze. (n−k)×n
Problem 1 (ResSD). Given H ∈ Fq and s ∈ Fn−k , find e ∈ E n such that q ⊺ eH = s, where E ⊂ Fq is a predetermined subset of size z. In the CROSS specification [5] and in [14], the set E is chosen to be a multiplicative subgroup of Fq , and q = p is a prime. We provide the general definition as in [8], since we will also consider “truncated” instances where E is a subset of the original multiplicative subgroup. We also focus on the full-weight instance, although [15, 8] further considered a case where the number of coordinates ei = 0 is fixed. The following two statements show basic manipulation methods for ResSD instances and are a formalization of the “Shifting E” paragraph from [5]. (n−k)×n
be an × Fn−k Proposition 1 (Affine Shifting of E). Let (H, s) ∈ Fq q instance of ResSD with solution’s entries in a set E = {r1 , . . . , rz }. We denote by u = (1, . . . , 1) the vector of length n − k. For any a, b ∈ Fq , a ̸= 0, define a (n−k)×n × Fn−k of ResSD with solution’s entries in the new instance (H′ , s′ ) ∈ Fq q ′ ′ −1 ′ set E , where H = a H, s = s + ba−1 uH⊺ , E ′ = aE + b ⊆ Fq . If there exists an algorithm solving (H′ , s′ ) over E ′ in time T with success probability ρ, then there exists an algorithm solving (H, s) over E in time T + O(n2 ) with success probability ρ. Proof. Computing (H′ , s′ ) can be done in time O(n2 ). Let us then suppose that we know e′ ∈ E ′n such that ⊺
e′ H′ = s′ ⇔ ⇔
e′ (a−1 H⊺ ) = s + ba−1 uH⊺ a−1 (e′ − bu)H⊺ = s
We also remark e ≜ a−1 (e′ − bu) has entries in a−1 E ′ − a−1 b = a−1 (aE + b) − a−1 b = E So e that can be computed in linear time is a solution to our problem.
⊓ ⊔
(n−k)×n
Proposition 2 (Multiplicative Randomization). Let (H, s) ∈ Fq × Fn−k be an instance of ResSD with restriction set E = ω i | 0 ≤ i < z for a q primitive z th root of unity ω ∈ Fq . Then, one can sample in polynomial time a (n−k)×n new instance (H′ , s) ∈ Fq × Fn−k of ResSD over the same restriction set q E, such that the sets of solutions to the two instances are in bijection computable in O(n) and the image of any solution to (H, s) is uniformly distributed over E n . Proof. Sample a vector c uniformly at random from E n and let C be the diagonal matrix constructed from c. Observe that a solution e to the initial problem satisfies s = eHT = eCC−1 HT = e′ H′T , 6
where H′ = HC−1 , and e′ = xC has every coordinate multiplied by a random element from E. Observing that because ω is a primitive root, for any e0 ∈ E the mapping e 7→ e0 e is a bijection from E to itself, this concludes the proof. ⊔ ⊓ The following method is inspired by hybrid methods in regular syndrome decoding (see below and in Section 3). It further exploits the multiplicative subgroup structure to provide stronger attack guaranties. (n−k)×n
Proposition 3 (Multiplicative Truncation). Let (H, s) ∈ Fq × Fn−k q be ian instance of ResSD with anthexisting solution x whose entries lie in E =′ ω | 0 ≤ i < z for a primitive z root of unity ω ∈ Fq . Then, for any integer z (n−k)×n with 1 ≤ z ′ ≤ z, one can efficiently sample a ResSD instance (H′ , s) ∈ Fq × n−k Fq such that, with probability at least ρ (over sampling), the entries of the n solution will lie in E ′ = ω i | 0 ≤ i < z ′ , where ρ = (z ′ /z) , and a solution to ′ ′n (H , s) in E can be efficiently converted into a solution to (H, s) in E. Proof. Let (H′ , s) be sampled using multiplicative randomization (Proposition 2) and let x′ be the image of x under the bijection from the statement. Clearly, every coordinate of x′ lands in E ′ with probability z ′ /z, independently of other coordinates. Therefore, x′ belongs to E ′n with probability ρ. Recovering x from any solution x′ amounts to n multiplications (by the diagonal of C−1 ); the result clearly belongs to E n and satisfies the parity check equation. ⊔ ⊓ Remark 1. This proposition is heavily based on the fact that E is a multiplicative subgroup. For general E, it is possible to apply a variant of the truncation similar to hybrid attacks on the regular syndrome decoding problem described in [18, 52]. Concretely, we do not modify the parity check matrix and simply guess z ′ out of z possible values error coordinate separately. This has the same z of each ′ probability 1 − z−1 / = z /z per coordinate. However, the key difference ′ ′ z z from the multiplicative truncation is that one cannot force a particular subset of E, and every coordinate will have its own randomly chosen subset. Finally, we also describe a basic memoryless attack that will be used for comparison with other low-memory methods. Note that the CROSS security analysis document [4] only describes attacks with the best time complexity, which have impractical memory complexities. (n−k)×n
Proposition 4. Let (H, s) ∈ Fq × Fn−k be an instance of ResSD with an q existing solution whose entries lie in a set E with |E| = z. Then, it can be solved in time O(n2 z k ) and negligible memory. Proof. Write H = (In−k , H′ ) so that for e = (x, y) ∈ Fn−k × Fkq , HeT = q T ′ T T k T x +H y = s . Enumerate z candidates for y and verify that x = sT −H′ yT belongs to E n−k (which can be done in O(n2 ) field operations per guess). ⊔ ⊓ 7
Regular syndrome decoding We recall the Regular Syndrome Decoding problem (RegSD). Definition 2. For n = zt, a vector e ∈ Fnq of Hamming weight t is regular if it can be written e = (e1 , . . . , et ) where each ei ∈ Fzq has Hamming weight 1. (n−k)×n
Problem 2 (RegSD). Given H ∈ Fq and s ∈ Fn−k , n = zt, find a regular q n vector e ∈ Fq of Hamming weight t such that eH⊺ = s. Definition 3. In this work, we will often consider regular vectors over Fnq having only one value on their nonzero entries. We are going to call such vectors lightregular vectors and denote by Lnt the set of those of Hamming weight t. 2.2
Lattices
An n-dimensional ball of radius R, denoted Bn,R ⊆ Rn , consists of all vectors of Rn having the Euclidean norm at most R. Its volume is Vol Bn,R ≜
Rn π n/2 = Rn · Vol Bn,1 . Γ (1 + n/2)
Definition 4 (Lattice). Let A ∈ Rk×n . The k-dimensional lattice generated by A is L(A) ≜ xA | x ∈ Zk . The length of its shortest nonzero vector (in terms of the Euclidean norm) is denoted λ1 (L(A)). The volume of A is defined p as Vol L(A) ≜ | det AAT |. We now describe fundamental lattice-related problems. The following standard heuristic is used to approximate the number of lattice vectors of norm below a given radius r. Heuristic 1 (Gaussian Heuristic (GH)) For a lattice L ⊂ Rn , the number of lattice points inside a ball Bn,R is approximately |L ∩ Bn,R | ≈
Vol Bn,R . Vol L
In particular, under GH, the shortest vector is approximated as r n 1/n −1/n 1/n λ1 (L) ≈ (Vol Bn,1 ) (Vol L) . (Vol L) ≈ 2πe Below, we describe standard lattice problems and their list-decoding variants and summarize the best solving complexities based on standard heuristics. All mentioned algorithms are probabilistic. Problem 3 (Shortest Vector Problem, SVP). Given a lattice L ⊂ Rn , find a nonzero vector u of L of minimum Euclidean norm λ1 (L). Problem 4 (List-SVP). Given a lattice L ⊂ Rn and a norm upper bound r, list all vectors of L of norm at most R. Equivalently, compute L ∩ Bn,R . 8
Problem 5 (Closest Vector Problem, CVP). Given a lattice L ⊂ Rn and a vector y ∈ Rn , find a vector u ∈ L that minimizes |y − u|E . Problem 6 (List-CVP). Given a lattice L ⊂ Rn , a vector y ∈ Rn , and a norm upper bound R, list all vectors of L having distance at most R to y. Equivalently, compute L ∩ (y + Bn,R ). Heuristic 2 (Sieving [10]) The SVP problem over an n-dimensional lattice can be solved in time 20.292n+o(n) and memory 20.208n+o(n) . Single CVP complexity is the same as sieving; however, there is a speedup when multiple targets need to be solved. Heuristic 3 (Batch-CVP Complexity [23]) A batch of M CVP instances over an n-dimensional lattice, M ≥ 20.058n+o(n) , can be solved in time M · 20.234n+o(n) and memory 20.208n+o(n) . The following heuristic claim is based on classic enumeration methods [26], [46, 30], which we summarize in Section A. Heuristic 4 (List-SVP/List-CVP complexity) The List-SVP/List-CVP problems over an n-dimensional lattice L, up to a negligible amount of missed vectors, can be solved in time ! n X Vol B i,R i 20.292n+o(n) + O n i(n−i) (Vol L)i/n δ i=1 and 20.208n+o(n) memory, where δ =
1 n − 2n−2 2πe
and Ri = R ·
q
i n.
We will also use the standard notions of LLL-reduced, BKZ-β reduced (2 ≤ β ≤ n) and HKZ-reduced lattice bases. Their formal definition is given in Section A.
3
Regular Syndrome Decoding Modeling
In this section, E is a fixed subset of Fq of cardinality z, whose elements are {r1 , . . . , rz }. Notation 2 For every matrix M over Fq with n columns, we denote the zncolumn matrix ME ≜ r1 M1 . . . rz M1 ∥ . . . . . . ∥ r1 Mn . . . rz Mn 9
3.1
Reduction
We consider the following matrix and vector 1...1 ∥ 0 ... ... 0 .. .. .. 0 . . . .. . . .. ∈ Fn×nz and u = 1 . . . . . . . . . 1 ∈ Fn .. .. Un = . n . . . q q . . . . .. .. 0 .. 0 ... ... 0 ∥ 1...1 for the following definition. (n−k)×n
Definition 5. For any H ∈ Fq and s ∈ Fn−k , we define q e ≜ UE ∈ F(2n−k)×zn and e s ≜ u | s ∈ F2n−k H p p H For any e ∈ E n , we also define e e = (e e1 , . . . , e en ) ∈ Fzn q such that for 1 ≤ i ≤ n, th if the i entry of e is equal to rj , then e ei ∈ Fzq has value one at its j th entry and zeros elsewhere. This construction allows the following lemma: (2n−k)×zn e e × F2n−k H, s ∈ Fq q ⊺ e defined as in Definition 5. Every solution x of xH = e s such that |x|H ≤ n belongs to Lzn n and the mapping (n−k)×n
Lemma 1. Let (H, s) ∈ Fq
and × Fn−k q
φ : E n −→ Lzn n e −→ e e n forms a bijection between the solutions in E of the ResSD instance (H, s) and e e s with solutions of Hamming weight n. the RegSD instance H,
e and the n first entries of e Proof. By construction of the n first rows of H s, e⊺ = e xH s implies that x has at least one nonzero entry per block, so |x|H ≥ n. Adding the constraint |x|H ≤ n means that |x|H = n and so x is regular. Still, e and the n first entries of e by construction of the n first rows of H s, we deduce that the unique nonzero value in each block can only be 1. So x ∈ Lzn n . e e For e a solution of (H, s), it is easy to see that e e is a solution of H, s and, e e conversely, for u a solution of H, s we can easily see that φ−1 (u) is a solution of (H, s). Because φ and φ−1 are injective functions, this concludes the proof. ⊔ ⊓ This bijection naturally gives the following reduction. 10
(n−k)×n
× Fn−k be an instance of ResSD with soq (2n−k)×zn e e lution entries in E = {r1 , . . . rz }, and consider H, s ∈ Fq × F2n−k q defined as in Definition 5 as an instance of RegSD with solutions of Hamming e e weight n. If there exists an algorithm solving H, s in time T with success probTheorem 1. Let (H, s) ∈ Fq
ability ρ, then there exists an algorithm solving (H, s) in time T + O(n2 ) with success probability ρ. Proof. It follows immediately from Lemma 1 and the facts that computing e H, e s can be done in quadratic time and recovering e ∈ E n from e e ∈ Lzn n in linear time. ⊔ ⊓ e e Remark 2. The light-regular solutions of the instance H, s of RegSD are exe⊺ = e actly the vectors of minimum Hamming weight among those satisfying xH s (as seen in Lemma 1), so they are also solutions of the usual Syndrome Decoding problem (but with a structured code). They are also solutions of minimum Lee metric as well as the ones of minimum Euclidean norm, which leads to considering them as solutions of a lattice problem as we do in the next section. 3.2
Security analysis
Most algorithms for solving the usual decoding problem rely on ISD (Information Set Decoding) [42, 50, 24, 9, 27, 13, 11, 40, 16, 17, 38]. These have been adapted for the case of regular vectors in [31, 21, 25] for the binary case, and in [38, 36] for the general q-ary case. We are going to adapt the Permutation-Based and Enumeration-Based Regular-ISD from [25], which are themselves adaptations of [42] and [27] to the error-regular case. Bi-Regular Permutations We should first consider the conditions for our e to be set in systematic form. Let P ∈ Fzn×zn be a permutation matrix matrix H q e 1, H e 2 ≜ HP, e e 1 is a square matrix of size 2n − k. and we denote H where H e 1 invertible. So, because of the n first P must be selected in order to have H e e 1 , or there will rows of H, there must be at least one column of each block in H be empty rows. Moreover, there should not be three columns or more from the e 1 , or there will be a linear dependency between columns. Indeed, same block in H e there is let us consider z ′ ≤ z columns of the same block. By construction of H a linear dependency between them if and only if there exists a nonzero vector ′ x ∈ Fzq such that z′ z′ X X xi = 0 and ri xi = 0 i=1
i=1
where ri are some elements of E (which are all distinct). This system admits a nonzero vectorial solution if and only if z ′ ≥ 3.
11
That is why we introduce the notion of bi-regular permutations which is inspired by regular permutations introduced in [25]. It allows us to have exactly e 1. one or two columns of each block in H Definition 6. Let e = (e1 , . . . , en ) ∈ (Fzq )n . For a permutation matrix P let ′′′ eP = (e′1 , . . . , e′n , e′′1 , . . . , e′′n , e′′′ 1 , . . . , en ) z−2 with e′i and e′′i are vectors with one entry, and e′′′ . P is bi-regular if i ∈ Fq ′′′ ′′ ′ each ei , ei and ei are formed only by coordinates from ei .
Since columns from different blocks cannot have linear dependencies (because of the distinct rows of ones in the n first rows), we obtain the following proposition. (2n−k)×zn
e ∈ Fq Proposition 5. Let H defined as in Definition 5 from some H ∈ (n−k)×n zn×zn e can a permutation matrix, if P is bi-regular then HP Fq . For P ∈ Fq be put in systematic form by doing linear operations on its rows. Permutation-Based ISD This algorithm from [25] was a direct adaptation of the original Prange algorithm [42] to the regular context. Although we are in a non-binary we can almost directly take the version of [25]. Given an context, e e s (defined as in Definition 5), the algorithm randomly chooses a instance H, e 1, H e 2 ≜ HP, e e1 ∈ bi-regular permutation matrix P for computing H where H (2n−k)×(2n−k)
(2n−k)×((z−2)n+k)
e 2 ∈ Fq e −1e . Then it computes e1 ≜ H and H Fq 1 s ∈ F2n−k and checks whether |e | = n. If this is the case, it returns the solution 1 H q e e = P−1 (e1 , 0). If not, the algorithm starts the process again. Remark 3. If the vector e e has Hamming weight n, it will also be light-regular e impose the sum on each of the n blocks to be since the linear constraints of H equal to 1. Remark 4. In the notation of Definition 6, we impose (e′′n−k+1 , . . . , e′′n ) and ′′′ (e′′′ 1 , . . . , en ) to be equal to 0. Assuming that the original solution is unique (as expected with CROSS parameters), we can see that the probability for choosing a right bi-regular permutation is exactly the probability of guessing: – for n − k blocks, a set of two entries to which the nonzero value belongs. – for k blocks, the exact position of the nonzero value. We obtain a probability of success that is !n−k n z−1 2 −k −k z = 2 z z 2
(1)
The total average number of iteration of our adapted Permutation-Based ISD being the inverse of success, the complexity of the algorithm ofthe nprobability k z is at least in O 2 . 2 12
Enumeration-Based ISD We are now going to improve the algorithm using the ideas originally coming from [27]. We again adapt to our case the adaptae must be put in the quasi-systematic form, which tion from [25]. This time H ! e I2n−k−ℓ H1 (2n−k−ℓ)×((z−2)n+k+ℓ) e and is e 2 for an integer ℓ ≥ 1, with H1 ∈ Fq 0 H e 2 ∈ Fℓ×((z−2)n+k+ℓ) e by permuting H . For that purpose, we need to transform H q its columns so that its 2n − k − ℓ first columns form a full-rank matrix. The bi-regular permutations as we have defined them are suitable for this. e into QHP e where P is a random So, the algorithm starts by transforming H bi-regular permutation and Q is an invertible matrix giving the quasi-systematic e⊺ = e form. Denoting e = (e1 , e2 ) and Qe s = (e s1 , e s2 ), we just need to solve e2 H s2 , 2 ⊺ e and we recover e1 = e s1 − e2 H1 . We are going to enumerate the vectors e2 e⊺ = e s with some additional conditions on e2 . verifying e2 H 2 2 Because we have used a bi-regular permutation, we can retake the notation of Definition 6 and write e
=
(e1 , e2 )
=
′′′ (e′1 , . . . , e′n , e′′1 , . . . , e′′n , e′′′ 1 , . . . , en ) ′′′ ((e′1 , . . . , e′n , e′′1 , . . . , e′′n−k−ℓ ), (e′′n−k−ℓ+1 , . . . , e′′n , e′′′ 1 , . . . , en ))
The vectors e2 that we enumerate are those with elements (e′′n−k−ℓ+1 , . . . , e′′n ) ′′′ set to zero and whose elements (e′′′ 1 , . . . , en ) have a Hamming weight equal to a ′′′ parameter p. Let us denote y ≜ (e1 , . . . , e′′′ n ).
Enumerating y This vector is divided into n blocks of z − 2 entries, each with at most one nonzero entry per block (of value 1). We are going to apply a meetin-the-middle strategy taking into account this structure. We define the set n n Rnp ≜ v = (v1 , . . . , vn ) ∈ Fz−2 q
0 ≤ |vi |H ≤ 1, |v|H = p, vi,j ∈ {0, 1}
o
and write y = (y1 , y2 ) where each yi is composed of n/2 blocks. ⊺ ⊺ e 2 = (H2 , H′ , H′′ ) e⊺ = e Having e2 H s2 now means y1 H′2 = e s2 − y2 H′′2 , where H 2 2 2 n ℓ×(z−2) 2 ℓ×(k+ℓ) ′ ′′ . with H2 ∈ Fq and H , H ∈ Fq n o n/2 We construct three lists L1 , L2 and L where Li = yi | yi ∈ Rp/2 and ⊺ ⊺ L = (y1 , y2 ) ∈ L1 × L2 | y1 H′2 + y2 H′′2 = e s2 . Then for all y ∈ L, we choose e ⊺ . The algorithm then checks whether e2 = (0, y) and compute e1 = e s1 − e2 H 1 |e1 |H = n − p. If this is the case, it returns e e = P−1 (e1 , e2 ) as a solution. If not, the algorithm starts again. The entire algorithm is described in Algorithm 1. 13
Algorithm 1 Enumeration-Based algorithm Parameters: ℓ ≤ 2n − k and p ≤ n, e ∈ F(2n−k)×zn Inputs: Parity-check matrix H , syndrome e s ∈ F2n−k q q zn e⊺ Output: Light-regular vector e e ∈ Fq of weight n such that e eH 1: loop 2: Sample a random bi-regular permutation P. e1 I2n−k−ℓ H e 3: e 2 ← QHP, (es1 , es2 ) ← Qes 0 H 4:
Li ←
5:
L←
n
n/2
o
yi | yi ∈ Rp/2 , i = 1, 2
n
e ⊺2 = es2 (y1 , y2 ) ∈ L1 × L2 | (0, y1 , y2 )H
o
6: for y ∈ L do e ⊺1 7: e1 = e s1 − (0, y)H 8: if |e1 |H = n − p then 9: return P−1 (e1 , e2 ) 10: end if 11: end for 12: end loop
Complexity We still assume that the solution is unique. Following [25], we can estimate that the time of enumeration will be approximately in T0 = n max(Card (L1 ) , Card (L2 ) , Card (L)) Card (L1 × L2 ) . As in the previous algorithm, we must comqℓ pute the probability of choosing a good permutation P. This corresponds to the probability of having the following:
with E(Card (L)) =
– y1 and y2 each of Hamming weight p/2 which is according to binomial law z − 2 for each block the probability of having weight 1 being : z p n−p 2 2 n/2 z−2 P0 = z z p/2 – having (e′′n−k−ℓ+1 , . . . , e′′n ) equal to 0. We denote this probability by P. For computing P, we first supposeothat k + ℓ ≥ n/2. 1 P2 where n n We have P = Po P1 ≜ P (e′′n−k−ℓ+1 , . . . , e′′n/2 ) = 0
and P2 ≜ P (e′′n/2 , . . . , e′′n ) = 0 . For P2 ,
we know that there are p/2 blocks where the nonzero entries are already set, and for the entries from other blocks the probability to be nonzero is 1/2 because n/2−p/2 1 there remain only two positions. So P2 = . For P1 , we first compute 2 the probability of having i entries from blocks where the nonzero entry has not 14
already been set in y (there are n/2 − p/2 of such blocks): n−k−ℓ k+ℓ−n/2 k+ℓ−n/2 X i n/2−p/2−i Pi = and so P = Pi 2−i 1 n/2 i=0
p/2
For the case where k + ℓ ≤ n/2, we have P=
k+ℓ X
Pi′ 2−i
where
i=0
Pi′ =
k+ℓ i
n/2−k−ℓ n/2−p/2−i n/2 p/2
We can now estimate the hole complexity by (when k + ℓ ≥ n/2): 2 n/2 n/2−p/2 p/2 n/2 p ℓ n2 max (z − 2) , (z − 2) /q p/2 p/2 T0 = n−k−ℓ p n−p k+ℓ−n/2 P0 P1 P2 z−2 Pk+ℓ−n/2 2 i n/2−p/2−i n/2 2 2−i i=0 p/2 n/2 z z p/2 n/2−p/2 p/2 n/2 n2 max (z − 2) , p/2 (z − 2)p /q ℓ = p n−p Pk+ℓ−n/2 k+ℓ−n/2 n−k−ℓ −i 2 z−2 i=0 n/2−p/2−i 2 i z z Memory complexity is proportional to Card (L1 ) = n/2 (z − 2)p/2 . p/2 Complexities for CROSS We give in Table 3 the complexities of our adapted ISD algorithms, giving also the best parameters p and ℓ to run the EnumerationBased ISD. We recall that with the CROSS parameters, our regular code has length 7n and dimension 5n + k. We can notice that the rate of attack’s complexity to the security parameter remains roughly the same: 0.65 for 128, 0.67 for 192, and 0.67 for 256. The Enumeration-Based algorithm has a high memory complexity due to the use of lists. Security
(n, k)
128 192 256
(127,76) (187,111) (251,150)
Permutation-Based costs Enumeration-Based costs 325 470 625
197 285 380
(162) (238) (320)
(p, ℓ) (99, 23) (144, 34) (196, 46)
Table 3. Complexities of our adapted ISD for CROSS (q = 127 and z = 7). Costs are given in bits, and memory complexities are in parenthesis.
Conclusion We have seen that adapting the ISD algorithms for our case does not give competitive attacks. The main reason is because the rate of the regular 15
(z − 2)n + k code is , which tends to be high when z is not too small, as in zn CROSS where z = 7. This means that one must guess a large number of variables while applying the adapted Prange algorithm or its refinements. The complexity could probably be reduced by using other ISD variants but not enough to make it competitive. The fact that it is more effective to apply the adapted ISD directly to the original ResSD problem as was done in the CROSS specification could possibly have been anticipated. n Indeed, we saw in (1) that our Prange’s average k z , which is strictly greater than z k because n > k. number of iterations is 2 2 And we can notice that if we “adapt” Prange’s algorithm to the original ResSD problem directly, we will have to “guess” k values that can take z values each (this is the attack of Proposition 4), making the average number of iterations equal to z k . There are also algebraic (or hybrid) algorithms for solving RegSD as studied in [18, 52], in both binary and non-binary cases. However, although they are likely to provide better parameters (the algorithm described in [52] has the lowest complexities in many parameters regimes), it would also probably not be enough to have interesting complexities. Indeed, if we observe the gaps between their complexities and the ones of adapted ISD given in [52, Tab.2] for codes of approximately the same lengths as ours, the gain is up to 15 bits.
4
Lattice-based Modelings: Reduction of ResSD to CVP
From now on, we will work in Fp with p a prime number, and E = {r1 , . . . , rz } is a fixed subset of Fp . For every matrix M or vector v over Fp , we denote by Z(M) (or Z(v)) the matrix (or vector) over Z whose entries have the same values as those in M (or v), with identification Fp ≃ {0, . . . , p − 1}. Conversely, for a matrix N over Z, we denote by Fp (N) the matrix over Fp whose entries are the projection of those of N (same for vectors). For any linear code C, define Z(C) ≜ {Z(v) | v ∈ C}. We also consider the lattice Z(C) + pZn that contains C precisely. Definition 7. Given C ≜ C(G) ⊂ Fnp a linear code of dimension k with G = (Ik , R) in systematic form, we define C
L(C) ≜ L A
with
C
A ≜
Ik Z (R) 0 pIn−k
∈ Zn×n
Remark 5. If G cannot be put in a systematic form as is and requires multiplication by a permutation matrix P ∈ Fn×n , we instead consider C ≜ C (GP) and p C −1 define L(C) ≜ L A P . Then we can easily check the following proposition.
16
Proposition 6. Let C ⊂ Fnp be a linear code. The mapping Zn −→ Fnp u −→ Fp (u) n
forms a surjection from L(C) onto C, and a bijection between L(C)∩{0, . . . , p − 1} and C.
From the structure of the generator matrix AC one can immediately deduce the volume of the lattice, equal to the determinant of the matrix. Proposition 7. For any linear code C ⊂ Fnp of dimension k, Vol L(C) = pn−k . 4.1
Reduction
(2n−k)×zn e e which is defined ×F2n−k H, s ∈ Fq , and ×Fn−k q p e . Let y e be some as in Definition 5. We denote L∗ ≜ L Ce where Ce ≜ C ⊥ H n ⊺ ∗ ∗ e = e eH vector of Fp such that y s and y ≜ Z(e y). Let S be the set of the ∗ ∗ e solutions of CVP for the instance (L , y ), and Sbe the set of solutions of e e RegSD of Hamming weight n for the instance H, s . (n−k)×n
Let (H, s) ∈ Fp
For the reduction, we will firstly need the two following lemmas giving relations between our code and our lattice. Lemma 2. Let u∗ ∈ L∗ be such that |y∗ − u∗ |E ≤ e belongs to S.
√
n. Then e e ≜ Fp (y∗ − u∗ )
e⊺ = y e⊺ − u e⊺ = e e = Fp (u∗ ). We have e eH eH Proof. Let eH s because us denote u ⊥ e e ∈ C H thanks to Proposition 6. If we suppose that |e u e|H > n, then we √ ∗ ∗ e|H ≤ n and by will obviously have |y − u |E > n which is not possible. So |e e e , so e ∈ S. ⊓ ⊔ Lemma 1 we can deduce that e e ∈ Lzn n √ Lemma 3. Let e e ∈ Se and we denote e∗ ≜ Z(e e). Then |e∗ |E = n and u∗ ≜ y∗ − e∗ belongs to L∗ . √ ∗ Proof. By Lemma 1 we know that e e ∈ Lzn n. Let us denote n , so |e |E = ∗ ⊺ ⊺ ⊺ e e e e = Fp (u eH = y eH − e u eH = e s−e s = 0. So we have ). We can check that u ⊥ e ∗ e ∈ C H and by Proposition 6 we can deduce that u ∈ L∗ . u ⊔ ⊓ We now compute the distance of a solution of our CVP instance to the target. Lemma 4. If we assume that Se ̸= ∅, then we have √ S ∗ = u∗ ∈ L∗ | |y∗ − u∗ |E = n 17
e We also define u∗ = y∗ − e∗ Proof. We assumed Se ̸= ∅, so we can choose e e1 ∈ S. 1 1 √ ∗ ∗ e 1 ≜ Fp (u1 ). Thanks to Lemma 3 we know that |e√ and u n and u1∗ ∈ L∗ . 1 |E = So we have obtained that u1∗ ∈ {u∗ ∈ L∗ | |y∗ − u∗ |E = n}. This means by the definition of CVP that √ S ∗ = {u∗ ∈ L∗ | |y∗ − u∗ |E = R} for some 0 ≤ R ≤ n. (2) √ We now assume that R < n. Let u2∗ ∈ S ∗ . We denote e∗2 ≜ y∗ − u2∗ , with e e2 ≜ Fp (e∗2 ). We know that |e∗2 |E = R because of (2) so by Lemma 2 we have √ ∗ e So |e e e2 ∈ S. ≥ n which is a contradiction to the fact √ e2 |H = n implying |e2 |E √ that R < n. This means that R = n. ⊓ ⊔ We can now prove the following proposition, which gives in fact a reduction from RegSD to CVP (with our particular instances). Proposition 8. If we assume that Se ̸= ∅, then the mapping ψ : Zzn −→
Fzn p
u∗ −→ Fp (y∗ − u∗ ) e forms a bijection between S ∗ and S. Proof. We first show that ψ with the domain restrained to S ∗ is injective. Let us suppose that there exists u1∗ , u2∗ ∈ S ∗ distinct such that ψ(u1∗ ) = ψ(u2∗ ), so Fp (y∗ −u1∗ ) = Fp (y∗ −u2∗ ). This means that there exists a nonzero vector k ∈ Zn such that y∗ − u1∗ = y∗ − u2∗ + pk. So by triangular inequality and Lemma 4 we have |y∗ − u1∗ |E √ n
≥ ≥
|y∗ − u2∗ |E + p |k|E √ n + p |k|E
This means that k = 0. So we obtain a contradiction proving the injectivity. Conversely, we obviously have ψ −1 : e e −→ y∗ − Z (e e) which is injective. ∗ e Because S and S are finite sets, we now just need to show that ψ(S ∗ ) ⊂ Se and that ψ −1 Se ⊂ S ∗ . The first point is immediate given Lemma 2 and Lemma 4. For the second one, let e e ∈ Se and e∗ ≜ Z(e e). By√Lemma 3 we know ∗ ∗ ∗ −1 that u ≜ y − e = ψ (e e) belongs to L∗ and that |e∗ |E = n. So by Lemma 4 we have u∗ ∈ S ∗ . ⊔ ⊓ We now have everything necessary to build the reduction from ResSD to CVP. (n−k)×n
× Fn−k be an instance of ResSD with solup e tion entries in E = {r1 , . . . rz }, and consider L Ce , y∗ where Ce ≜ C ⊥ H e⊺ = e and Fp (y∗)H s, as an instance of CVP. If there exists an algorithm which can solve L Ce , y∗ in time T with success probability ρ, then there exists an Theorem 2. Let (H, s) ∈ Fp
algorithm solving (H, s) in time T + O(n3 ) with success probability ρ. 18
Proof. Computing
e e H, s can be done in quadratic time, and computing y∗
needs to solve a linear system, which can be done in time O(n3 ). Let us then consider φ and ψ the mappings as defined in Lemma 1 and Proposition 8 respectively. We then have φ ◦ ψ −1 which is a bijection between the solutions of both of our problems, and computing a preimages of this mapping can be done in linear time. ⊔ ⊓ Remark 6. This reduction comes from the same ideas as those of [32], where reductions are given from Lee-based problems to lattice-based problems. But in our case, the distributions of lattices are particular (not uniform). 4.2
Security analysis - Hybrid-BatchCVP attack
Combining the reduction with modern heuristic algorithms for Batch-CVP yields the following generic result. (n−k)×n
be an instance of ResSD with solu× Fn−k Corollary 1. Let (H, s) ∈ Fp p tion entries in E with |E| = z. Then, under Heuristic 3, it can be solved in time 20.234z(n−g)+o(zn) z g and memory 20.208z(n−g)+o(zn) , where g = ⌈0.058zn logz 2⌉. Proof. Let us guess g first blocks of z variables each in the final lattice (z g candidates) and modify the target vector each time accordingly. We obtain a batch of M = z g CVP target vectors for a single lattice of reduced dimension z(n − g) (the guessing can be equivalently done on the initial ResSD problem, so that the reduction proof remains valid for the smaller problem). Note that M ≥ 20.058zn ≥ 20.058z(n−g) and therefore Heuristic 3 is applicable. ⊔ ⊓ Remark 7. Since the number of guesses is chosen such that 20.234zn z g ≈ 20.292zn , the reduction from the use of the Batch-CVP technique (compared to basic sieving cost for CVP) comes from the reduction of the lattice dimension, and is equal 2 to 20.234zg ≈ 20.0014z n logz 2 . We consider the application of the hybrid attack - multiplicative truncation (see Proposition 3), CVP reduction, partial guessing, and Batch-CVP solution - to CROSS-R-SDP parameters and their reduced variants. The results are summarized in Table 4. Interestingly, the best time complexity is achieved at truncation z ′ = 6 (out of the original z = 7); it is roughly equal to 21.8n . Choosing z ′ = 5 leads to a small slowdown, but significant savings in memory complexity. However, we note that, at least for the CROSS-R-SDP parameters, the proposed attack complexities do not improve over basic memoryless ISD-like guessing of k coordinates in the initial problem ResSD. This attack has time complexities 2213.4 , 2311.6 , 2421.1 for n = 127, 187, and 251 respectively. The main contribution to this fact is that we used generic CVP solvers whose complexity estimate depends only on the dimension of the lattice, which is quite large in our case (zn). Possible analysis based on the length of the solution vector is made difficult due to the existence of a large number of short vectors in the 19
(n, k)
(127, 76)
(187, 111)
(251, 150)
z′
Trunc. prob.
g blocks guessed
Batch-CVP cost
Total time
Memory
7 6 5 4 3 2
2−0.0 2−28.2 2−61.6 2−102.5 2−155.2 2−229.5
19 (253.3 ) 18 (246.5 ) 16 (237.2 ) 15 (230.0 ) 14 (222.2 ) 15 (215.0 )
2230.2 2199.6 2167.0 2134.8 2101.5 267.4
2231.5 2229.1 2229.9 2238.6 2258.0 2298.2
2157.2 2136.0 2115.4 293.2 270.5 246.6
7 6 5 4 3 2
2−0.0 2−41.6 2−90.8 2−151.0 2−228.6 2−338.0
28 (278.6 ) 26 (267.2 ) 24 (255.7 ) 22 (244.0 ) 21 (233.3 ) 22 (222.0 )
2339.0 2293.3 2246.4 2198.4 2149.8 299.2
2340.3 2336.1 2338.5 2350.7 2379.7 2438.5
2231.5 2200.9 2169.5 2137.3 2103.6 268.6
7 6 5 4 3 2
2−0.0 2−55.8 2−121.8 2−202.6 2−306.8 2−453.6
37 (2103.9 ) 34 (287.9 ) 32 (274.3 ) 30 (260.0 ) 28 (244.4 ) 30 (230.0 )
2454.4 2392.6 2330.5 2266.9 2200.9 2133.4
2455.7 2449.6 2453.6 2470.8 2509.0 2588.3
2311.6 2270.8 2227.8 2183.9 2139.2 291.9
Table 4. Hybrid-Batch-CVP cost estimation for CROSS-R-SDP. The attack consists in probabilistic truncation from the initial z = 7 to z ′ , guessing g coordinate blocks, and running heuristic Batch-CVP. The complexities are adapted to achieve success rate of 90%. Up to the correction factor, the total time complexity is the product of the inverse of the truncation probability and the batch-CVP cost.
lattice. For example, for the restriction used in CROSS, any vector of the form (. . . , 0, 2, −3, 1, 0, . . .) belongs to the lattice, where the part (2, −3, 1) is inside any block. Developing and analyzing tailored lattice algorithms is an interesting avenue for future work.
5
Lattice-based Modelings: Reduction of ResSD to List-CVP and List-SVP without expansion
We also propose another heuristic, but more direct and more compact latticebased modeling of ResSD. The key idea is that the set E of allowed values can be modeled by a set of “small” values around a well-chosen center. Furthermore, the values can be scaled by a nonzero constant which increases the number of such embeddings. The effect is stronger when the set is small or has a certain structure. For this purpose, we will use the multiplicative truncation (Proposition 3) to reduce the size of the set E. We start with the notion of an affine diameter in Subsection 5.1, which quantifies how close the values of the set E can be packed together under an affine substitution. In Subsection 5.2, we describe the general shape of the reduction 20
with an arbitrary center µ and a radius R. Then, in Subsection 5.3, we analyze the specialization of the reduction based on the affine diameter, which leads to a concrete deterministic reduction to List-CVP. In Subsection 5.4, we continue with a stronger but probabilistic reduction to List-CVP based on the standard deviation of the set E and the mean of E as the center. We show in Subsection 5.5 that for an integral center the problem can be converted to List-SVP by manipulating the ResSD instance before the reduction. Remarkably, for some ResSD instances (low code rate and compact restriction set), one can heuristically deduce reductions to pure CVP and SVP. Finally, in Subsection 5.6 we conclude with applying the reductions to CROSS-R-SDP instances and verifying them experimentally. 5.1
Affine diameter
Definition 8. Let E ⊆ Fp , |E| = z > 0. We define the affine diameter DE of the set as min max Z(ax + b). (3) a,b∈Fp ,a̸=0 x∈E
Remark 8. For computational purposes, a small optimization is to use the equivalent expression DE =
max Z(ax − ax0 ),
min
a∈Fp \{0},x0 ∈E x∈E
which reduces the number of b to be tested from p to |E|. To see that it is true, observe that, for a fixed a, the minimum in (3) is achieved when one of the elements of E is mapped to 0. Otherwise, one can subtract the smallest integer from Z(ax + b) without wrapping modulo p, decreasing the maximum value by that amount. Therefore, it is sufficient to enumerate all nonzero a and an element x0 ∈ E to be mapped to 0, and choose the minimum value of the sets’ maximums. It is easy to see that DE is the smallest length of a continuous segment that contains all elements of aE + b. We will show how to use a small affine diameter to convert ResSD into a lattice-based problem. Before that, we will study the notion itself further. The case of z = 1 is trivial with DE = 0. Generally, any two elements of E may always be mapped to 0 and 1 by a valid choice of a, b in the definition. In the case of z = 2, this implies DE = 1, which essentially leads to a subset-sum formulation of ResSD, as already noted by the designers of CROSS [5]. The larger cases of z > 2 become nontrivial. We study some examples computationally for p = 127 used in CROSS. Note that the set E used in CROSS ′ has subsets of size z ′ with 1 ≤ z ′ ≤ 7, of affine diameter 2z −1 − 1, namely z ′ −1 {1, 2, 4, . . . , 2 } ⊆ E. We will use this together with the truncation technique. The results are summarized in Table 5. For example, in the case of z = 3 with p = 127 as in CROSS, without loss of generality, assume the shape E = {0, 1, a}. The average affine diameter (over 21
a ∈ {2, . . . , p − 1} ⊆ Fp ) is 8.032. The highest value of DE is 13 achieved with {0, 1, 20}, which is affine-equivalent to {0, 6, 13}. The other possible values of DE are all integers from 2 to 11 and are achieved (for example) by the sets {0, 1, DE )}.
z = |E|
CROSS
Min.
Avg.
2 3 4 5 6 7 8 9 10
1 3 7 15 31 63 -
1 2 3 4 5 6 7 8 9
1 8.03 17.81 27.47 36.09 43.56 50.01† 55.60† 60.42†
Affine diameter DE Max. Example (Max.) 1 13 27 42 57 65 72† 79† 83†
{0, 1} {0, 6, 13} {0, 11, 12, 27} {0, 12, 14, 17, 42} {0, 12, 13, 16, 23, 57} {0, 22, 35, 40, 54, 63, 65} {0, 16, 27, 31, 32, 35, 38, 72} {0, 1, 2, 4, 7, 13, 22, 46, 79} {0, 18, 28, 29, 36, 56, 59, 71, 82, 83}
Table 5. Comparison of the affine diameter of subsets of E used in CROSS-R-SDP (p = 127) to average/maximum values over subsets of Fp of size z. †: approximate values obtained by sampling at least 107 random subsets of size z.
We conclude that the affine diameter is a nontrivial parameter with a broad range of values. We observed that the values for the subsets of the set E used in CROSS are on the smaller side, showing suboptimal resistance. Together with the truncation technique, we will use it to derive new direct lattice-based models of the ResSD and CROSS in particular. 5.2
Reduction to List-CVP
The following theorem shows the close relation between solution vectors to a (restricted) syndrome decoding problem and the lattice associated to the corresponding linear code (as defined in Section 4). One has to keep Proposition 1 (Affine Shifting) in mind, since it allows us to change the set E which can lead to different behavior of the Euclidean distances. (n−k)×n
Theorem 3. Let (H, s) ∈ Fp × Fn−k be an instance of ResSD with solup tion entries in a set E. Let positive µ ∈ R. Then, there exists an n-dimensional lattice L ⊆ Zn of volume pn−k and a vector v ∈ Rn , constructible in time polynomial in n, such that there exists an embedding φ of the solutions e ∈ Fnp , eHT = s, into the lattice, such that v u n uX 2 |φ(e) − v|E = t (Z(ei ) − µ) . (4) i=1
This embedding and its left inverse are computable in time O(n). 22
Proof. We first construct L, y and φ. Let C be the linear code that admits H as a parity check matrix. Let a ∈ Fnp be an arbitrary solution to aHT = s. Define L = L(C) ⊆ Zn ,
(5)
v = µ − Z(a) ∈ Rn ,
(6)
φ : e 7→ Z(e) − Z(a) ∈ Zn ,
(7)
where µ = (µ, . . . , µ) ∈ Rn . We now prove the claims. Clearly, L and v are constructible efficiently. We now prove that φ produces a vector in L. Let e ∈ Fnp be a solution to the SD problem: eHT = s. Then, Fp (φ(e))HT = (e − a)HT = 0, and so Fp (φ(e)) belongs to C, which by Proposition 6 implies that φ(e) belongs to L. Furthermore, we have φ(e) − v = Z(e) − Z(a) − µ + Z(a) = Z(e) − µ which implies (4). Finally, the map ψ : y 7→ Fp (y + a) is a left inverse of φ and it is clear that both ϕ and ψ can be computed in linear time. ⊔ ⊓ As a corollary, we derive the generic reduction of ResSD to List-CVP, which is parametrized by the “restriction center” µ which should be close to all elements of E, and the radius R bounding the distance from this center. (n−k)×n
× Fn−k be an instance of ResSD with soluCorollary 2. Let (H, s) ∈ Fp p tion entries in a set E. Let positive µ, R ∈ R, µ ≥ 0, R > 0, and define ( n ) X 2 2 ρ= P (ei − µ) ≤ R . (8) ei ∈Z(E) 1≤i≤n
i=1
Let a lattice L ⊆ Zn and a vector v ∈ Rn be defined as in Theorem 3. Then, with probability ρ over solutions to the ResSD problem, a solution to the ListCVP instance (L, v) with distance upper bound R and N output vectors can be converted into a solution to the ResSD instance in time O(nN ). Proof. From Theorem 3 it is clear that solutions e satisfying the bound in (8) belong to the constructed List-CVP instance within radius R. Recovering the ResSD solution can be done in linear time per candidate vector, since it only requires addition of a constant vector and testing the restriction to E. ⊔ ⊓ Remark 9. p Under the Gaussian and using Proposition 7, we note that p n Heuristic n when R ≤ 2πe Vol1/n = 2πe p1−k/n , the number of vectors in the lattice satisfying the distance bound R is a small constant. In this case, one can heuristically reclassify the List-CVP formulation as a simple CVP. In contrast, Theorem 2 is a non-heuristic precise reduction to CVP. 23
Remark 10. Note that the success probability is taken over the instances of the initial problem, and so is essentially a weak-key attack when ρ < 1. For a fixed µ, by varying the distance upper bound R we can explore different trade-off points between the List-CVP complexity and the success probability. However, reaching a very high success probability would be extremely costly. Luckily, we have an alternative in the case where E is a multiplicative subgroup, as in CROSS. The natural randomization method (Proposition 2) allows the reduction to be performed multiple times, each time having a fresh success probability ρ. Here, one needs to note that the reduction probability in the theorem is over the possible error-vector solutions, and the randomization technique perfectly randomizes these vectors. 5.3
Analysis based on affine diameter
A possible choice for µ and R is naturally based on the affine diameter. The following proposition describes a precise compact reduction based on this quantity. (n−k)×n
× Fn−k be an instance of ResSD with Proposition 9. Let (H, s) ∈ Fp p solution entries in a set E. Then, in time polynomial in n and linear in the output size, this problem can be reduced to √ a List-CVP problem over an n-dimensional lattice of volume pn−k and distance nDE /2. Proof. We first apply Proposition 1 to obtain an equivalent ResSD instance √ with E ′ = {0, . . . , DE } and then apply Corollary 2 with µ = DE /2 and R = nDE /2, so that 2 n n 2 X X DE nDE (ei − µ)2 ≤ ≤ , 2 4 i=1 i=1 implies the success probability ρ = 1 exactly. The lattice from Corollary 2 (and Theorem 3) has volume pn−k by Proposition 7. ⊓ ⊔ An interesting question one may ask is for which ResSD parameters n, k, p, DE the problem reduces to pure CVP (which would be solvable in heuristic time 20.292n+o(n) by Heuristic 3)? The following analysis is under the GH. The expected length of the shortest nonzero vector (or distance from a ranp n n−k p n 1/n n . When this quantity is larger than dom √ point) is = 2πe Vol 2πe p R = nDE /2, we can expect a unique solution coinciding with the image of the solution to the ResSD problem under the reduction. Therefore, we need r 2 1−k/n p ≈ 0.48p1−k/n . DE < πe This bound benefits from smaller DE , larger p, and lower code rate. Regarding the overall sparsity, a natural requirement is to expect roughly 1 random solution to the problem, which means z n ≈ pn−k , z = |E| (see [5]), and thus the bound becomes DE < 0.48z. Clearly, this is not possible for z ≥ 3. Therefore, this reduction with (µ, R) based on the affine diameter never reduces 24
to pure CVP in interesting cases. However, the reduction may still be useful for two reasons. First, we can apply multiplicative truncation (Proposition 3), which makes the problem sparser by eliminating some elements of E. The combination of truncation and reduction may thus be more powerful. Second, the List-CVP formulation can still lead to efficient attacks, since the enumeration complexity gradually increases from sieving 20.292n+o(n) , with increasing List-CVP radius. In the next subsection, we will evaluate these options, but together with better choices of µ and R. 5.4
Analysis based on the standard deviation of E
Although setting µ, R in the reduction based on the affine diameter DE is a natural option and leads to good theoretical bounds and deterministic success (ρ = 1), stronger attacks may be achieved when ρ < 1 is allowed. Another natural choice of µ is the one that minimizes the expected value of the distance (where the expectation is over e ∈ E n ) v u n uX 2 (Z(ei ) − µ) . |φ(e) − v|E = t i=1
Since it is not straightforward to compute, we will first minimize the expected square of the distance instead. Pn 2 Proposition 10. The expected value of the sum i=1 (Z(ei ) − µ) , where each ei isPsampled independently and uniformly from a set E, is minimized at µ = 1 r∈E Z(r). |E| Proof. By linearity of expectation, ( n ) n o X n X 2 2 2 (Z(r) − µ) , E (Z(ei ) − µ) = nE (Z(e0 ) − µ) = |E| i=1 r∈E
where the second equation is due to e0 being P sampled uniformly from E. The 1 latter expression is minimized at µ = |E| ⊔ ⊓ r∈E Z(r). Setting µ to the average value of Z(E) means that the expected value of the Pn 2 sum i=1 (Z(ei ) − µ) being minimized is equal to nσ 2 (E) where σ 2 (Z(E)) is the variance of a random variable sampled uniformly from E. For computing the success probability of the reduction, it is more convenient to work with the median of the distance instead of the mean. This would give a good estimate on the List-CVP distance in the reduction with the success rate ρ = 50%. For this purpose, we will heuristically assume that the mean approximates well the median. Note that taking the median commutes with squaring, so that the median of the distance is equal to the square root of the median of the squared distance, which by the heuristic coincides with the mean of the squared distance, which is in turn minimized and calculated in Proposition 10. We will also evaluate the quality of this heuristic experimentally. 25
Heuristic P 5 The median value ME,n of the distance d = |φ(e) − v|E (using 1 2 µ = |E| r∈E Z(r)) is well approximated by the square root of the mean of d : v u z u n X ME,n = t · (Z(r) − µ)2 . |E| r∈E
5.5
Reduction to List-SVP
In this subsection, we describe a trick that allows one to convert the problem into List-SVP / SVP using the fact that the problem originates from linear codes, where the corresponding decoding and low-weigh codeword problems are more closely related. (n−k)×n
× Fn−k be an instance of ResSD with Proposition 11. Let (H, s) ∈ Fp p solution entries in a set E. Let µ be a positive integer. Then, there exists an ndimensional lattice L ⊆ Zn of volume pn−k−1 , constructible in time polynomial in n, such that there exists an embedding φ of the solutions e ∈ Fnp , eHT = s, into the lattice, such that v u n uX 2 (Z(ei ) − µ) . (9) |φ(e)|E = t i=1
This embedding and its left inverse are computable in time O(n). Proof. First, we apply Proposition 1 with a = 1 and b = −µ to obtain a new ResSD problem (H′ , s′ ) with restriction E ′ = {r − µ | r ∈ E}. Second, choose an (n−k)×(n−k) such that arbitrary invertible matrix Q ∈ Fp Qs′T = (1, 0, . . . , 0)T = s′′T . Let H′′ = QH′ . Clearly, the sets of solutions of eH′T = s′ and of eH′′T = s′′ are (n−k−1)×n to H′′ with the first row removed, which identical. Now set H′′′ ∈ Fp only increases the set of solutions in the new ResSD instance eH′′′ = 0 (by an expected factor of p). Let C be the linear code that admits H′′′ as a parity check matrix. Define L = L(C) ⊆ Zn , φ : e 7→ Z(e) − µ ∈ Zn ,
(10) (11)
where µ = (µ, . . . , µ) ∈ Rn . Clearly, L is constructible efficiently. Let e ∈ Fnp be a solution to the original SD problem: eHT = s. Then, H′′ Fp (φ(e))T = QH′ Fp (φ(e))T = QH′ (e − µ) = Qs′T = (1, 0, . . . , 0)T , and so Fp (φ(e)) belongs to C, which by Proposition 6 implies that φ(e) belongs to L. The norm equation (9) follows directly from the definition of φ. It is evident that ϕ has left inverse and both are computable in linear time. ⊔ ⊓ 26
This directly implies the List-SVP reduction, with proof as in Corollary 2. (n−k)×n
Corollary 3. Let (H, s) ∈ Fp × Fn−k be an instance of ResSD with the p solution’s entries in a set E. Let a nonnegative integer µ and a positive real R and define ( n ) X 2 2 ρ= P (ei − µ) ≤ R . ei ∈Z(E) 1≤i≤n
i=1
Let a lattice L ⊆ Zn be defined as in Proposition 11. Then, with probability ρ over solutions to the ResSD problem, a solution to List-SVP over L with distance upper bound R and N output vectors can be converted into a solution to the RegSD instance in time O(N ). This reduction is of theoretical and practical interest. For parameters implying R < λ1 (L), under GH, the constructed List-SVP problem degenerates to a pure SVP problem, which is an interesting result for a code-based problem. The reduction provides an alternative to the Kannan embedding [35], which is the most used technique for converting a CVP instance into an SVP instance. SVP algorithms are often more performant than CVP in practice. However, in our analysis below, we only consider strongest generic methods (Heuristic 2 and Heuristic 3) which have the same complexity for SVP and CVP (perhaps having a small difference hidden in the omitted polynomial factors). 5.6
Security analysis - Hybrid-ListCVP attack
We discuss the hybrid attack - multiplicative truncation and List-CVP reduction - applied to CROSS-R-SDP parameters. We are using the mean-based µ and the median R from Subsection 5.4. The results are summarized in Table 6. The first step in the attack is to truncate the instance from z = 7 to z ′ ≤ z. According to Proposition 3, this has a probability of success (z ′ /z)n , which means that (z/z ′ )n attempts are needed on average. We increase this number of attempts by a factor of four to reach the success probability 1 − e−4 ≈ 98%. Here, we use the Poisson distribution as the limit of the binomial distribution. This defines the first factor in the final time complexity. The second step consists in applying the List-CVP reduction from Corollary 2 with the distance upper bound R being the median of the distribution, approximated using Heuristic 5. Since the median only ensures the success rate of 50%, we repeat the entire process four times, each time using multiplicative randomization (Proposition 2), increasing the success rate to 15/16 ≈ 94%. The third step is to solve the resulting List-CVP instance by enumeration, using the complexity estimate from Heuristic 4. The latter always includes the sieving cost, which actually dominates in instances where the target solution is expected to be unique. Due to the pruning used in Heuristic 4, we repeat the process four times to reach 98% success rate of the step. The total success rate is 90%. This step also dominates memory complexity which by Heuristic 3 is 20.208n+o(n) . 27
(n, k)
z′
Trunc. prob.
|L ∩ Bn,R |
Sieve cost
Enum. cost
Total time
Memory
(35, 21)
7 6 5 4 3 2 1
2−0.0 2−7.8 2−17.0 2−28.3 2−42.8 2−63.3 2−98.3
2124.7 290.7 256.1 220.2 2−18.4 2−64.6 2−∞
210.2 210.2 210.2 210.2 210.2 210.2 210.2
2130.0 296.2 262.0 228.0 26.8 23.6 20.0
2136.0 2110.0 285.0 262.2 257.0 277.5 2112.5
27.3 27.3 27.3 27.3 27.3 27.3 27.3
(127, 76)
7 6 5 4 3 2 1
2−0.0 2−28.2 2−61.6 2−102.5 2−155.2 2−229.5 2−356.5
2459.1 2335.7 2210.1 279.9 2−60.3 2−227.8 2−∞
237.1 237.1 237.1 237.1 237.1 237.1 237.1
2466.5 2343.5 2219.4 2105.2 230.3 27.1 20.0
2472.5 2377.7 2287.1 2213.8 2196.3 2270.6 2397.6
226.4 226.4 226.4 226.4 226.4 226.4 226.4
(187, 111)
7 6 5 4 3 2 1
2−0.0 2−41.6 2−90.8 2−151.0 2−228.6 2−338.0 2−525.0
2671.4 2489.7 2304.8 2113.1 2−93.3 2−339.9 2−∞
254.6 254.6 254.6 254.6 254.6 254.6 254.6
2679.4 2498.4 2316.5 2158.4 251.0 28.6 20.0
2685.4 2545.9 2413.3 2315.3 2287.2 2396.6 2583.6
238.9 238.9 238.9 238.9 238.9 238.9 238.9
(251, 150)
7 6 5 4 3 2 1
2−0.0 2−55.8 2−121.8 2−202.6 2−306.8 2−453.6 2−704.6
2909.7 2665.8 2417.5 2160.3 2−116.9 2−447.8 2−∞
273.3 273.3 273.3 273.3 273.3 273.3 273.3
2918.2 2675.0 2432.3 2226.7 281.0 210.9 20.0
2924.2 2736.9 2560.2 2435.3 2384.1 2530.9 2781.9
252.2 252.2 252.2 252.2 252.2 252.2 252.2
Table 6. Hybrid-List-CVP cost estimation for CROSS instances and a reduced instance used for experiments. The attack consists in probabilistic truncation from the initial z = 7 to z ′ and running sieve and enumeration algorithms. The complexities are adapted to achieve success rate of 90%. Up to the correction, total time is equal to the product of the inverse of the truncation probability and the sum of sieve and enumeration costs.
We remark that the analysis potentially omits polynomial complexity factors in sieving (which is relevant for instances degraded to CVP) and in enumeration (which is relevant for List-CVP cases). This is in part due to the lack of a precise analysis of the sieving complexity. We believe that this leads to an acceptable accuracy for security analysis purposes, and this simplification is in line with the common literature. From the results, we can draw several conclusions. First, the best attacks are always obtained from the truncation to z ′ = 3, which coincidentally is the 28
largest z ′ for which List-CVP reduces to CVP. Second, the attacks do not threaten the CROSS parameters even with potentially improved sieving and enumeration algorithms (note that, in current analysis, enumeration always incurs additional overhead in comparison to the expected number of vectors in the output). Indeed, for z ′ ≤ 3, the probability of successful truncation is always less than 2−n . For z ′ ≥ 4, the ratio of the expected number of vectors in the considered ball Bn,R to the probability of successful truncation is always larger than 2n . Experimental verification We performed experiments to verify the correctness of the reduction. The setup consists of a standard laptop with an Intel i7 CPU @ 3 GHz and 32 GB RAM. The software used is the SageMath computer algebra [45] and the fpylll library [51]. For n = 35, k = 21, z = 4 (n, k are downscaled CROSS parameters and z = 4 should be understood as z ′ = 4 after multiplicative truncation), our complexity analysis predicts 220.21 vectors within the mean-based center µ = 3.75 and the heuristic median radius R = 15.86 (for the set E = {1, 2, 4, 8}). In 105 tries, we observed the image of the correct solution satisfy the bound in about 51% of the instances, confirming Heuristic 5. Computing BKZ-n-reduced basis took negligible time. Enumeration using fpylll without pruning took about 12 seconds (theoretical time complexity estimate 232.34 ). Using exact values of the Gram-Schmidt matrix of the reduced basis (instead of the GSA), the computed complexity reduced to 228.46 on average (this matches common observations on strong reduction quality for small dimensions). Over several experiments, we always observed around 1.2 million vectors within the target vector, closely matching the prediction 220.21 . Whenever the reduction image of the initial solution satisfied the bound, it was correctly recovered among the enumerated vectors.
6
Conclusion
In this work, we have shown and studied reductions of the recent Restricted Syndrome Decoding problem to the more traditional Regular Syndrome Decoding problem with the particularity of light-regular errors, as well as to the latticebased search (SVP, CVP) and enumeration problems (List-SVP, List-CVP). The reductions range from exact, deterministic and relatively large output instances (dimension zn), to heuristic, probabilistic and compact instances (dimension n). We believe that our results shed new light on the ResSD problem and open new research directions, such as finding more connections between the paradigms, finding new reductions, advancing analysis of the resulting instances. For the CROSS signature, we obtained some new time-memory trade-off points, although our current reductions and attacks do not threaten its security. Acknowledgments This work was funded by the Luxembourg National Research Fund (FNR), project PQseal C24/IS/18978392. 29
References 1. Aguilar-Melchor, C., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.C., Gaborit, P., Persichetti, E., Zémor, G., Bos, J., Dion, A., Lacan, J., Robert, J.M., Veron, P.: HQC. Tech. rep., National Institute of Standards and Technology (2022), available at https://csrc.nist.gov/Projects/ post-quantum-cryptography/round-4-submissions 2. Alagic, G., Bros, M., Ciadoux, P., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Liu, Y.K., Miller, C., Moody, D., Peralta, R., Perlner, R., Robinson, A., Silberg, H., Smith-Tone, D., Waller, N.a.: Status report on the first round of the additional digital signature schemes for the nist post-quantum cryptography standardization process. Tech. rep., National Institute of Standards and Technology (2024), https://csrc.nist.gov/pubs/ir/8528/final, nIST Internal Report 8528. 3. Augot, D., Finiasz, M., Sendrier, N.: A family of fast syndrome based cryptographic hash functions. In: Ed Dawson, Serge Vaudenay (editors). Progress cryptology-Mycrypt First international conference on cryptology Malaysia, ISBN 978-3-540-28938-8. LNCS, vol. 3715, pp. 64–83. Springer, Kuala Lumpur, Malaysia (Sep 2005). https://doi.org/10.1007/11554868_6, https://doi.org/10.1007/ 11554868_6 4. Baldi, M., Barenghi, A., Battagliola, M., Bitzer, S., Gianvecchio, M., Karl, P., Manganiello, F., Pavoni, A., Pelosi, G., Pintore, F., Santini, P., Schupp, J., Signorini, E., Slaughter, F., Wachter-Zeh, A., Weger, V.: CROSS — Codes and Restricted Objects Signature Scheme. Security Details. Version 2.2 - July 31, 2025. Tech. rep. (2024) 5. Baldi, M., Barenghi, A., Battagliola, M., Bitzer, S., Gianvecchio, M., Karl, P., Manganiello, F., Pavoni, A., Pelosi, G., Santini, P., Schupp, J., Signorini, E., Slaughter, F., Wachter-Zeh, A., Weger, V.: CROSS — Codes and Restricted Objects Signature Scheme. Tech. rep., National Institute of Standards and Technology (2024), available at https://csrc.nist.gov/Projects/pqc-dig-sig/ round-2-additional-signatures 6. Baldi, M., Battaglioni, M., Chiaraluce, F., Horlemann, A.L., Persichetti, E., Santini, P., Weger, V.: A new path to code-based signatures via identification schemes with restricted errors. Advances in Mathematics of Communications 19(5), 1360– 1381 (2025). https://doi.org/10.3934/amc.2024058 7. Baldi, M., Battaglioni, M., Chiaraluce, F., Horlemann-Trautmann, A.L., Persichetti, E., Santini, P., Weger, V.: A new path to code-based signatures via identification schemes with restricted errors (2021). https://doi.org/10.48550/arXiv. 2008.06403 8. Baldi, M., Bitzer, S., Pavoni, A., Santini, P., Wachter-Zeh, A., Weger, V.: Zero knowledge protocols and signatures from the restricted syndrome decoding problem. In: Tang, Q., Teague, V. (eds.) PKC 2024, Part II. LNCS, vol. 14602, pp. 243–274. Springer, Cham (Apr 2024). https://doi.org/10.1007/ 978-3-031-57722-2_8 9. Barg, A.: Minimum distance decoding algorithms for linear codes. In: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 12th International Symposium, AAECC-12, Toulouse, France, June 23-27, 1997, Proceedings. LNCS, vol. 1255, pp. 1–14. Springer (1997) 10. Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: Krauthgamer, R. (ed.)
30
27th SODA. pp. 10–24. ACM-SIAM (Jan 2016). https://doi.org/10.1137/1. 9781611974331.ch2 11. 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: Advances in Cryptology - EUROCRYPT 2012. LNCS, Springer (2012) 12. Berlekamp, E., McEliece, R., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Trans. Inform. Theory 24(3), 384–386 (May 1978) 13. Bernstein, D.J., Lange, T., Peters, C.: Smaller decoding exponents: ball-collision decoding. In: Advances in Cryptology - CRYPTO 2011. LNCS, vol. 6841, pp. 743– 760 (2011) 14. Beullens, W., Briaud, P., Øygarden, M.: A security analysis of restricted syndrome decoding problems. CiC 1(3), 33 (2024). https://doi.org/10.62056/a06cy7qiu 15. Bitzer, S., Pavoni, A., Weger, V., Santini, P., Baldi, M., Wachter-Zeh, A.: Generic decoding of restricted errors. In: IEEE International Symposium on Information Theory, ISIT 2023, Taipei, Taiwan, June 25-30, 2023. pp. 246– 251. IEEE (2023). https://doi.org/10.1109/ISIT54713.2023.10206983, https: //doi.org/10.1109/ISIT54713.2023.10206983 16. Both, L., May, A.: Optimizing BJMM with Nearest Neighbors: Full Decoding in 22/21n and McEliece Security. In: WCC Workshop on Coding and Cryptography (Sep 2017), http://wcc2017.suai.ru/Proceedings{_}WCC2017.zip 17. Both, L., May, A.: Decoding linear codes with high error rate and its impact for LPN security. In: Lange, T., Steinwandt, R. (eds.) Post-Quantum Cryptography 2018. LNCS, vol. 10786, pp. 25–46. Springer, Fort Lauderdale, FL, USA (Apr 2018). https://doi.org/10.1007/978-3-319-79063-3{_}2, https://doi. org/10.1007/978-3-319-79063-3{_}2 18. Briaud, P., Øygarden, M.: A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 391–422. Springer, Cham (Apr 2023). https://doi.org/10.1007/978-3-031-30589-4_14 19. Bricout, R., Chailloux, A., Debris-Alazard, T., Lequesne, M.: Ternary syndrome decoding with large weight. In: Paterson, K.G., Stebila, D. (eds.) SAC 2019. LNCS, vol. 11959, pp. 437–466. Springer, Cham (Aug 2019). https://doi.org/10.1007/ 978-3-030-38471-5_18 20. Burle, E., Udovenko, A.: Cross-paradigm models of restricted syndrome decoding with application to CROSS - supporting code (Jan 2026). https://doi.org/10. 5281/zenodo.18230686, https://doi.org/10.5281/zenodo.18230686 21. Carozza, E., Couteau, G., Joux, A.: Short signatures from regular syndrome decoding in the head. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 532–563. Springer, Cham (Apr 2023). https://doi.org/ 10.1007/978-3-031-30589-4_19 22. Debris-Alazard, T., Tillich, J.P.: Statistical decoding. In: Proc. IEEE Int. Symposium Inf. Theory - ISIT 2017. pp. 1798–1802. Aachen, Germany (Jun 2017) 23. Ducas, L., Laarhoven, T., van Woerden, W.P.J.: The randomized slicer for CVPP: Sharper, faster, smaller, batchier. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020, Part II. LNCS, vol. 12111, pp. 3–36. Springer, Cham (May 2020). https://doi.org/10.1007/978-3-030-45388-6_1 24. Dumer, I.: On minimum distance decoding of linear codes. In: Proc. 5th Joint Soviet-Swedish Int. Workshop Inform. Theory. pp. 50–52. Moscow (1991) 25. Esser, A., Santini, P.: Not just regular decoding: Asymptotics and improvements of regular syndrome decoding attacks. In: Reyzin, L., Stebila, D. (eds.)
31
CRYPTO 2024, Part VI. LNCS, vol. 14925, pp. 183–217. Springer, Cham (Aug 2024). https://doi.org/10.1007/978-3-031-68391-6_6 26. Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Mathematics of Computation 44(170), 463–471 (1985), http://www.jstor.org/stable/2007966 27. Finiasz, M., Sendrier, N.: Security bounds for the design of code-based cryptosystems. In: Matsui, M. (ed.) Advances in Cryptology - ASIACRYPT 2009. LNCS, vol. 5912, pp. 88–105. Springer (2009) 28. Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Berlin, Heidelberg (Apr 2008). https://doi.org/10.1007/978-3-540-78967-3_3 29. Gama, N., Nguyen, P.Q., Regev, O.: Lattice enumeration using extreme pruning. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 257– 278. Springer, Berlin, Heidelberg (May / Jun 2010). https://doi.org/10.1007/ 978-3-642-13190-5_13 30. Hanrot, G., Pujol, X., Stehlé, D.: Algorithms for the shortest and closest lattice vector problems. In: Chee, Y.M., Guo, Z., Ling, S., Shao, F., Tang, Y., Wang, H., Xing, C. (eds.) Coding and Cryptology. pp. 159–190. Springer Berlin Heidelberg, Berlin, Heidelberg (2011) 31. Hazay, C., Orsini, E., Scholl, P., Soria-Vazquez, E.: Concretely efficient large-scale MPC with active security (or, TinyKeys for TinyOT). In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part III. LNCS, vol. 11274, pp. 86–117. Springer, Cham (Dec 2018). https://doi.org/10.1007/978-3-030-03332-3_4 32. Horlemann, A.L., Khathuria, K., Newman, M., Sakzad, A., Cabello, C.V.: Latticebased vulnerabilities in lee metric post-quantum cryptosystems. Cryptology ePrint Archive, Report 2024/1495 (2024), https://eprint.iacr.org/2024/1495 33. Hülsing, A., Bernstein, D.J., Dobraunig, C., Eichlseder, M., Fluhrer, S., Gazdag, S.L., Kampanakis, P., Kölbl, S., Lange, T., Lauridsen, M.M., Mendel, F., Niederhagen, R., Rechberger, C., Rijneveld, J., Schwabe, P., Aumasson, J.P., Westerbaan, B., Beullens, W.: SPHINCS+ . Tech. rep., National Institute of Standards and Technology (2022), available at https://csrc.nist.gov/Projects/ post-quantum-cryptography/selected-algorithms-2022 34. Jabri, A.A.: A statistical decoding algorithm for general linear block codes. In: Honary, B. (ed.) Cryptography and coding. Proceedings of the 8th IMA International Conference. LNCS, vol. 2260, pp. 1–8. Springer, Cirencester, UK (Dec 2001) 35. Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: 15th ACM STOC. pp. 193–206. ACM Press (Apr 1983). https: //doi.org/10.1145/800061.808749 36. Kim, J., Lee, C.: Reduce and prange: Revisiting prange’s information set decoding for LPN and RSD. IACR Cryptol. ePrint Arch. p. 276 (2024), https://eprint. iacr.org/2024/276 37. Lenstra, A., Lenstra, H., Lovász, L.: Factoring polynomials with rational coefficients. Math. ann 261(4), 515–534 (1982) 38. Liu, H., Wang, X., Yang, K., Yu, Y.: The hardness of LPN over any integer ring and field for PCG applications. In: Joye, M., Leander, G. (eds.) EUROCRYPT 2024, Part VI. LNCS, vol. 14656, pp. 149–179. Springer, Cham (May 2024). https: //doi.org/10.1007/978-3-031-58751-1_6 39. Lyubashevsky, V., Ducas, L., Kiltz, E., Lepoint, T., Schwabe, P., Seiler, G., Stehlé, D., Bai, S.: CRYSTALS-DILITHIUM. Tech. rep., National Institute of Standards and Technology (2022), available at https://csrc.nist.gov/Projects/ post-quantum-cryptography/selected-algorithms-2022
32
40. May, A., Ozerov, I.: On computing nearest neighbors with applications to decoding of binary linear codes. In: Oswald, E., Fischlin, M. (eds.) Advances in Cryptology - EUROCRYPT 2015. LNCS, vol. 9056, pp. 203–228. Springer (2015) 41. McEliece, R.J.: A Public-Key System Based on Algebraic Coding Theory, pp. 114– 116. Jet Propulsion Lab (1978), dSN Progress Report 44 42. Prange, E.: The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory 8(5), 5–9 (1962). https://doi.org/10.1109/TIT.1962. 1057777, http://dx.doi.org/10.1109/TIT.1962.1057777 43. Prest, T., Fouque, P.A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Ricosset, T., Seiler, G., Whyte, W., Zhang, Z.: FALCON. Tech. rep., National Institute of Standards and Technology (2022), available at https://csrc.nist. gov/Projects/post-quantum-cryptography/selected-algorithms-2022 44. Saarinen, M.J.O.: Linearization attacks against syndrome based hashes. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) Progress in Cryptology - INDOCRYPT 2007. LNCS, vol. 4859, pp. 1–9. Springer (2007) 45. Sage Developers, T.: SageMath, the Sage Mathematics Software System (Version 10.6) (2025), https://www.sagemath.org 46. Schnorr, C.P., Euchner, M.: Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical Programming 66(1), 181–199 (Aug 1994). https://doi.org/10.1007/BF01581144, https://doi.org/10.1007/ BF01581144 47. Schnorr, C.P.: Lattice reduction by random sampling and birthday methods. In: Alt, H., Habib, M. (eds.) STACS 2003. pp. 145–156. Springer Berlin Heidelberg, Berlin, Heidelberg (2003) 48. Schwabe, P., Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J.M., Seiler, G., Stehlé, D., Ding, J.: CRYSTALS-KYBER. Tech. rep., National Institute of Standards and Technology (2022), available at https://csrc. nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022 49. Shor, P.W.: Algorithms for quantum computation: Discrete logarithms and factoring. In: Goldwasser, S. (ed.) FOCS. pp. 124–134 (1994) 50. Stern, J.: A method for finding codewords of small weight. In: Cohen, G.D., Wolfmann, J. (eds.) Coding Theory and Applications. LNCS, vol. 388, pp. 106–113. Springer (1988) 51. development team, T.F.: fpylll, a Python wrapper for the fplll lattice reduction library, Version: 0.6.4 (2025), https://github.com/fplll/fpylll, available at https://github.com/fplll/fpylll 52. Wang, T., Wang, A., Yang, K., Liu, H., Yu, Y., Zhang, J., Wang, X.: A hybrid algorithm for the regular syndrome decoding problem. IACR Cryptol. ePrint Arch. p. 1284 (2025), https://eprint.iacr.org/2025/1284
A
Lattice enumeration methods
In the following, we summarize a standard heuristic framework for solving ListSVPand List-CVP, based on enumeration of lattice points inside a given ball (L∩(y+Bn,r ) for a given basis of L and y). Note that enumeration was previously developed and used for the purpose of solving SVP/CVP; the more modern and optimized sieving methods supersede enumeration. However, enumeration is still useful for solving the “List” problem variants. 33
Orthogonalization Applying Gram-Schidmt orthogonalization to a full-rank lattice basis B = (b1 , . . . , bn ) ∈ (Rn )n yields the orthogonal vectors (b∗1 , . . . , b∗n ) Pi and projections µi,j ∈ R of bi on b∗j , 1 ≤ i, j ≤ n, satisfying bi = j=1 µi,j b∗j . Define the orthogonal projections πi , 1 ≤ i ≤ n, ⊥
πi : Rn → span {b1 , . . . , bi−1 } : bk 7→
n X
µk,j b∗j .
j=i
For 1 ≤ a ≤ b ≤ n, we write L[a,b] to denote the lattice spanned by the vectors πa (ba ), . . . , πa (bb ). Reduced bases The root Hermite factor δ0 of a vector x in a lattice L is defined as !1/n |x|E δ0 ≜ 1/n (Vol L) (see [28]). We are usually interested in δ0 of the first basis vector. The lattice basis is said to be LLL-reduced with factor ε, 0 < ε < 1 [37] if all µi,j ≤ 1/2 and its Gram-Schmidt orthogonalization satisfies 2
2
b∗i+1 + µi+1,i b∗i E ≥ (1 − ε) |b∗i |E . The lattice basis is said to be BKZ-reduced with block size β ≥ 2 and factor ε, 0 < ε < 1 [46] if it is LLL-reduced with factor ε and for each 1 ≤ j ≤ n, b∗j E = λ1 (L[j,min(j+β−1,n)] ). The lattice basis is said to be HKZ-reduced, if for each 1 ≤ j ≤ n, b∗j E = λ1 (πj (L)). In particular, b1 = b∗1 is the shortest vector in L. Heuristic 6 (Geometric Series Assumption, GSA [47]) Let B be a BKZβ- or HKZ- reduced basis and let (b∗i )i be its Gram-Schmidt orthogonalization −
n
with root Hermite factor δ0 . Then, for all i, and with δ = δ0 n−1 , |b∗i |E ≈ δ 2(i−1) · |b∗1 |E = δ 2(i−1) · δ0n (Vol L)
1/n
≈ δ 2i−n−1 (Vol L)
1/n
.
We now briefly describe the generic enumeration algorithm [26, 46, 30]. The idea is to enumerate elements of projections πi (L) of the lattice orthogonally to basis vectors, in reverse order (i going from n to 1). Let x(i) , L(i) , y(i) be projections of x, L, y orthogonally to the span of b1 , . . . , bi−1 . If x ∈ (L ∩ (y + Bn,R )), then x(i) ∈ L(i) ∩ (y(i) + Bn−i+1,R ) for all i. Furthermore, L(i) ∩(y(i) +Bn−i+1,R ) can be obtained from L(i+1) ∩ (y(i+1) + Bn−i,R ) in an efficient way. The complexity of the enumeration is bounded (up to polynomial factors) by the sum of the sizes of projected intersections L(i) ∩ (y(i) + Bn−i+1,R ), which by GH gives cost n X Vol Bn−i+1,R . T = Vol L(i) i=1 34
Qn i/n We have Vol L(i) = j=i b∗j E which under GSA is equal to δ i(n−i) (Vol L) . (i) The second component ∈ is pruning. Observe that for most points x (i) (i) L ∩ (y + Bn−i+1,R ) their projections will have shorter length than the vecp tor themselves. Linear pruning consists in using the upper bound Rd = R · d/n at the dimension d = n + i − 1. The authors of [29] proved that the probability of a uniformly random vector on a sphere satisfying this constraint at all levels is exactly 1/n. Therefore, randomizing the basis (see the same work) and repeating the search cn times on for some constant c allows us to list all but a negligible fraction of vectors. Finally, we consider an HKZ-reduced basis, which can be reduced to solving a polynomial time of SVP instances. Thus, the final cost includes the cost of sieving 1/(n−1) q p n 1/n − n 2πe and δ = δ0 n−1 = . (Heuristic 2). This means δ0 = 2πe n Remark 11. The sieving algorithm from Heuristic 2 outputs 20.208n short vectors. These short vectors could potentially be used to improve the enumeration complexity beyond using an HKZ-reduced basis. This is an interesting question beyond the scope of this work.
35