Domain-Informed Representation for Evolutionary Sieving in Integral and Module Lattices
arXiv:2605.29169v1 [cs.CR] 27 May 2026
Ahmad Tashfeen(
)
and Qi Cheng
University of Oklahoma, Norman OK 73019, USA {tashfeen,qcheng}@ou.edu
Abstract. Traditional cryptography, rooted in problems, e.g., integer factorisation or discrete log, is inevitably vulnerable to a fully operational quantum computer. Although it remains an engineering frontier, the looming threat extends to encrypted data stored today, which could be decrypted in the future with quantum capabilities. To safeguard against this eventuality, the backbone of the modern quantum-safe cryptography is the Shortest Vector Problem (SVP). We enhance Laarhoven’s treatment of Ajtai et al.’s sieving as a genetic algorithm (GA) for the SVP by incorporating domain-informed SVP representation and crossover while naturally extending application to the module lattices. Keywords: Shortest Vector Problem · Integral Lattice · Module Lattice · Sieving · Genetic Algorithm · Post Quantum Cryptography
1
Introduction
Lattices model various real-world systems, e.g., relay circuits, plumbing lines, public roads and digital networks [19,1]. Recently, they have gained significance in post-quantum cryptography, as traditional encryption methods like RSA are susceptible to quantum attacks. Although fully operational quantum computers may be distant, existing data could be compromised in the future. In 2016, NIST1 launched an initiative [11] to select and standardise quantum-resistant algorithms. Three out of four chosen final algorithms are based on problems from the lattice theory [4,3,5,6]: CRYSTALS–Kyber and Saber use module lattices as a source of their hardness and NTRU is based on the Shortest Vector Problem (SVP). Along with the Knapsack Problem’s reduction to the SVP, the SVP has attracted the attention of many prominent mathematicians over time including Gauss. Today, the most practical [9,25] approaches to the SVP are sieving and lattice reduction algorithms (Section 3.1). These include the Lenstra, Lenstra, and Lovász (LLL), or the block Korkin–Zolotarev (BKZ) algorithms. More than half of the solutions for the Darmstadt’s SVP challenges, posted at their website [21] are done via some sieving technique [24]. Laarhoven’s [17] treatment of sieving as a genetic algorithm (GA) enabled the application of the 1
U. S. Department of Commerce’s National Institute of Standards and Technology
2
A. Tashfeen and Q. Cheng
evolutionary framework to lattices. In this work, we enhance and further test this framework by incorporating field-specific knowledge, while also extending it to the increasingly significant module lattices. The primary aim of this paper is to focus on demonstrating the improvements achieved in a simple genetic algorithm only by integrating insights from lattice theory2 . This choice allows our results to be directly comparable to Laarhoven’s [17] simple genetic algorithm and lets us attribute any improvements solely to the domain-informed problem representation and crossover. Our contributions are summarised as follows, 1. We define an improved SVP representation for GAs enabling a versatile crossover operator using the insights from traditional algorithms like LLL. Our crossover is compatible with module lattices therefore extending a sieving algorithm for module lattices for the first time. 2. We solve all the challenge [21] and randomly generated problems till 100 dimensions improving application & scalability of Laarhoven’s approach [17]. Outline. Sec. 1 and 2 present the current SVP relevance, key lattice intuitions, heuristics, and notations utilized in this paper. Sec. 3 reviews related work. Sec. 4 presents our primary GA. Sec. 5 details and discusses the experiments and their outcomes. Finally, Sec. 6 provides ideas for future-work and concluding remarks.
2
Preliminaries
A lattice is a discrete additive subgroup of a d-dimensional Euclidean space, i.e., a subset closed under addition where each element has no other element within a certain radius. In two dimensions, a lattice maybe colloquially referred to as a grid of points. See Figure 1 for example. Let N, Z, R, and C be the natural, integer, real and complex numbers respectively. Consider a basis matrix B ∈ Rd×d with d linearly independent column vectors {bi ∈ Rd : 1 ≤ i ≤ d} such that bi is the ith column of B. We recall a possibly transformed d dimensional Euclidean space as {Bx : x ∈ Rd }, if we restrict Bx to only the integral linear combinations x ∈ Zd , we obtain a lattice L(B) = {Bx : x ∈ Zd }. The dimension of a lattice is dim(L) = d, i.e., the number of column-vectors in the basis matrix B and the determinant similarly det L(B) = |det B|. If B also has d number of rows, we call L a full rank lattice. Rd is now the ambient space for the reduced set of vectors that are in the lattice L. The group operation of a lattice is the vector sum, v + u ∈ L such that u, v ∈ L. Integral Lattices. If we further restrict B ∈ Zd×d , the resulting lattice is known as an integral lattice. You might imagine a trivial lattice Z2 spanned by the identity matrix. We show the plot of a two dimensional lattice (d = 2) in Figure 1 spanned by both of the basis stated in Equation 1. 2
Optimisations through the latest machine learning techniques remain an excellent opportunity for future research.
Evolutionary Lattice Sieving
3
95 47 460 215 1 40 Bgood = 30 5
(1)
500
400
300
Bbad =
200
100 Good Basis Bad Basis
0 0
20
40
60
80
100
Fig. 1. Example of a 2D lattice.
Good vs. Bad Basis. Figure 1 shows a “good” and a “bad” basis given in Eq. 1 that span the same lattice. A basis gets better as its vectors get shorter and more orthogonal and vice versa. The process of turning a bad basis into a good basis is also referred to as performing lattice reduction. Module Lattices. Here we define the module lattices [9] formed over the Gaussian integers Z[i] = {α+βi : (α, β) ∈ Z2 } where i2 = −1. Despite the name, Gaussian integers are complex numbers α + βi where both, the real ℜ(α + βi) = α and the imaginary ℑ(α + βi) = β parts are limited to the integers. We can similarly form a lattice, this time in the ambient space of complex numbers C, by letting B ∈ Z[i]d×d for the lattice L = {Bx : x ∈ Z[i]d }. The norm of a v ∈ Z[i]d is given as ∥v∥22 = v H v = |v1 |2 + |v2 |2 + · · · + |vd |2 where |vj |2 = α2 + β 2 for vj = α + βi. The vector v H is known as the conjugate transpose of v. p Hadamard Ratio. The H(B) = d det L(B)/∥b1 ∥∥b2 ∥ · · · ∥bd ∥ is used as a measure of orthogonality in-between the basis vectors bi ∈ B. Put simply, the closer this ratio is to 1 for a basis B, the more orthogonal it is. 2.1
Lattice Problems
Both the SVP and the Closest Vector Problem (CVP) are N P-hard3 . Let ∥v∥ be the ℓ2 norm of a vector v. Definition 1 (Shortest Vector Problem (SVP)). Find the shortest non-zero vector v ∈ L such that for all u ∈ L where v ̸= u, we have ∥v∥ ≤ ∥u∥. Definition 2 (Approximate Shortest Vector Problem (apprSVP)). Let α ≥ 1 be an approximation factor and find a v ∈ L such that ∥v∥ is no bigger than α times the length of the shortest non-zero vector, i.e., ∥v∥ ≤ α∥vshortest ∥. Definition 3 (Closest Vector Problem (CVP)). For w ∈ Rd where w ̸∈ L find a vector v ∈ L that is closest to w and ∥w − v∥ > 0, i.e., minv∈L ∥w − v∥. 3
However, SVP is N P-hard under a randomised reduction.
4
A. Tashfeen and Q. Cheng
Definition 4 (Shortest Basis Problem (SBP)). Find a bi ∈ Bgood from Bbad Pd where bi are short in some sense, e.g., minimise max1≤i≤d ∥bi ∥ or i=1 ∥bi ∥2 . SBP may be solved via various lattice reduction algorithms (Section 3.1). Any solution to the SBP often also uncovers a comparable solution to the apprSVP. Essentially all lattice-based cryptography (as talked about in the introduction) relies on the inability of lattice √ reduction algorithms to solve the apprSVP with an approximation of α = O( d) [14]. 2.2
Gaussian Heuristic for the Shortest Vector
It is difficult to verify a solution for the apprSVP and SVP since ∥vshortest ∥ is unknown in the general case. As the dimension d of a random lattice gets sufficiently large, we may rely on the Gaussian expected shortest length, i.e., the p 1 Gaussian heuristic where ∥vshortest ∥ ≈ σ(L) = d/2πe(det L) d [14]. 2.3
Genetic Algorithms
A genotype encodes a solution. Genotype instances are called individuals. A set of individuals is a population u, v ∈ P . Populations of individuals evolve through generations via reproduction. Using a selection Select(P, Fitness) process based on a fitness-function Fitness : P → [0, 1], two parent individuals u, v are selected for crossover to produce a child individual t ← Cross(u, v) in the next generation R. The child t may Mutate(t). See Alg. 1 from Russell [23]. Input: Initial population: P , fitness-function: Fitness : P → [0, 1]. Output: The best individual in population, according to the fitness. 1: do 2: R←∅ 3: for (u, v) ← Select(P, Fitness) 4: t ← Cross(u, v) 5: if (small random probability) then t ← Mutate(t) 6: R ← R ∪ {t} 7: P ←R 8: while (∀v ∈ P, Fitness(v) < 1 − ε)
Algorithm 1: This simple base GA is the same as Laarhoven’s base GA [17] therefore, attributing all improvements in comparison solely to our domain-informed problem representation and crossover operator.
Evolutionary Lattice Sieving
3
5
Related Work
If any of the N P-complete problems are shown to be in P then all of N Pproblems are in P. In the same seminal paper [16] where Karp determines a subset of the N P problems as N P-complete with the aforementioned property, he also gives twenty-one examples of such N P-complete problems. Number 18 on the list is the knapsack problem: given a set M = {m1 , m2 , . . . , mn } ∈ Nn , S ∈ N n find x ∈ {0, 1} such that M x = S. In other words, find a subset of M whose sum is equal to S. The first cryptosystem to be based on an N P-complete problem uses a disguised knapsack problem and was attempted by Merkle and Hellman [20]. We say a disguised knapsack problem since whether a cryptographic system can be as hard to break as to solve an N P-complete problem is an open problem in itself [22]. One might disguise an easy knapsack problem, defined with a superincreasing Measy = {mk > 2mk−1 : mk ∈ M } by modding integral multiples of its elements. Note a solution x for Measy can be recovered easily by setting xk = 1 if S ≥ mk and then subtracting mk from S. The same approach however does not work on Mdisguised = {Amk mod B : gcd(A, B) = 1, mk ∈ Measy }. Lagarias and Odlyzko [18] showed that any knapsack problem can be encoded as an SVP. Take any knapsack problem (M, S) and the relevant solution x such that M x = S. Now consider the lattice basis Bbad of dimension d = n + 1 in Equation 2. The lattice spanned by Bbad must have a vector t ∈ L(Bbad ) that is the result of an integral linear combination due to x. x1 2x1 − 1 2x1 − 1 2 0 ··· 0 1 0 2 · · · 0 1 x2 2x2 − 1 2x2 − 1 .. .. (2) = t = ... ... . . . ... ... ... = . . 0 0 · · · 2 1 xn 2xn − 1 2xn − 1 0 M ·x−S −1 m1 m2 · · · mn S {z } | Bbad
Since x√is a binary vector, any (2xi − 1) ∈ t must be either 1 or −1. Therefore, ∥t∥ = n and t is very likely to be the shortest vector in the lattice √ L(Bbad ) because for all other lattice vectors v ∈ L(Bbad ) the length ∥v∥ ≫ n due to the non-unit squares. The shortest vector t in the lattice spanned by Bbad will reveal the solution x to the knapsack problem, i.e., xk = 1 if tk > 0 else xk = 0. 3.1
Lattice Reduction Algorithms
If a lattice is expressed in terms of it’s good basis then solving the SVP becomes fairly easy. This means that if we first solve the SBP then the SVP is easy. For example, assume for a certain Bgood that all column vectors bi are pairwise orthogonal, i.e., for i ̸= j we know that bi · bj = 0. Then for any x ∈ Zd , ∥x1 b1 + x2 b2 + · · · xd bd ∥2 = x21 ∥b1 ∥2 + x22 ∥b2 ∥2 + · · · x2d ∥bd ∥2 and the shortest non-zero vector(s) can be found in {±b1 , · · · ± bd }. For an approximate solution of an instance of the CVP using a good basis, see Babai’s nearest hyperplane algorithm [7] or Theorem 7.34 (pg. 405) of Hoffstein [14].
6
A. Tashfeen and Q. Cheng
Lenstra, Lenstra, and Lovász (LLL) Algorithm The first lattice reduction algorithm is by Gauss. It works like Euclid’s GCD algorithm but with two, twodimensional vectors, i.e., B = {b1 , b2 }. Assume without the loss of generality that ∥b1 ∥ ≤ ∥b2 ∥ then b2 = b2 − (b1 · b2 )/∥b1 ∥2 b1 . If ∥b2 ∥ is still greater than ∥b1 ∥ we can stop. Otherwise, swap b2 with b1 and try again. The LLL algorithm generalises Gaussian lattice reduction from two to d dimensions. Just like Gaussian lattice reduction, it subtracts an integral multiple of a shorter basis vector from a larger basis vector until some size condition is fulfilled. For each 1 ≤ j < k ≤ d, we reduce bk as bk = bk − ⌊µk,j ⌉ bj where µk,j = b∗j ·bk /b∗j ·b∗j . The vector b∗j is the j th basis vector in the Gram-Schmidt orthogonalization of B. The reduction of bk is carried out using the Gram-Schmidt orthogonalizations of all the already reduced bj for every index 1 ≤ j < k − 1 where the size condition |µk,j | > 0.5 is met. If LLL terminates after only this recursive size reduction then the goodness of the reduced basis depends on the order of the original basis vectors in the basis matrix. Therefore, after the size reduction of bk , another condition, namely the popular Lovász condition is checked; for δ = 3/4 we check the condition, ∥b∗k ∥2 ≥ (δ − µ2k,k−1 )∥b∗k−1 ∥2 . If the Lovász condition is met then bk is considered reduced and k will be incremented. Otherwise, for the optimal ordering, we swap bk and bk−1 and decrement k 4 . LLL is a polynomial time lattice reduction algorithm for all 0 < δ < 1. The outer loop of Algorithm 2 runs at most in O(d2 log(d) + d2 log(max∥bi ∥)) and solves the apprSVP with an approximation factor of α = 2(d−1)/2 . It is also an open problem whether LLL terminates in polynomial time for δ = 1. For a more in-depth analysis, see Kalbach et al. [15]. Input: Lovász condition constant: 0 < δ < 1 and the Bad basis: B = {b1 , b2 , . . . , bd }. Output: Good/Reduced basis: B = {b1 , b2 , . . . , bd }. 1: k ← 2 2: (B∗ , µ) ← GramSchmidt(B) 3: while k ≤ d 4: for j ∈ {k − 1, k − 2, k − 3, . . . , 1} 5: if µk,j > 0.5 6: bk ← bk − ⌊µk,j ⌉ bj 7: (B∗ , µ) ← GramSchmidt(B) 8: if ∥b∗k ∥2 ≥ δ − µ2k,k−1 ∥b∗k−1 ∥2 9: k ←k+1 10: else 11: Swap(bk−1 , bk ) 12: (B∗ , µ) ← GramSchmidt(B) 13: k ← max(k − 1, 2)
Algorithm 2: The LLL algorithm (Section 3.1). GramSchmidt(B) returns the Gram–Schmidt orthogonalisation of B as well as the projection scalars µk,j evaluated during the process of orthogonalising bk via bj . Swap(bj , bk ) swaps bj , bk . 4
More precisely k = max(k − 1, 2)
Evolutionary Lattice Sieving
7
LLL Variations While LLL is a polynomial time algorithm, many of it’s generalisations and extensions tend to perform just as fast during empirical analysis and yield a further reduced basis [8]. Gama et al. argue by their extensive empirical analysis [12] that there is a gap between what theory is able to prove and what is the true power of the reduction algorithms. The two possible exponential time variations of LLL are DEEP (deep insertion method) and BKZ (block Korkin–Zolotarev) [12]. DEEP differs from the standard LLL when the Lovász condition fails. Standard LLL simply swaps the bk with bk−1 whereas in DEEP we insert bk at an optimal place before the k th basis vector. While in BKZ, instead of reducing bk with only one bj , the same is done with a block of basis vectors, bj , bj+1 , bj+2 , . . . bj+β−1 where β is the block size. Note that if we let β = d then the shortest vector in the output of BKZ solves the SVP problem and for any β < d we solve some version of the apprSVP. 3.2
Sieving
Sieving for the shortest vector first surfaced due to the works of Ajtai et al. [2]. At the time of this writing, more than half (437/847) of the solutions posted at the SVP challenges website [21] are done via sieving [24]. The idea is: if we have u, v ∈ L and we want a shorter one, we might try v − u. For a fixed P ⊂ L, repeatedly check if there exists a pair u, v ∈ P such that ∥v − u∥ < ∥v∥ then v is replaced with v − u. Laarhoven [17] set sieving up as a simple genetic algorithm. The foremost concern here arises about a possible method of mutation if lattice vectors v ∈ L(B) are treated as individuals in a genetic algorithm. This is due to the fact that mutating a gene vi ∈ v may cause v to step outside of the lattice. For this reason, they encode the individual for v = Bx as x ∈ Zd . This is possible because of the definition of a lattice given in Section 2. Now x maybe perturbed by adding binary noise to a random xi ∈ x. While encoding a lattice vector v = Bx as x gives a way to mutate v through x, it requires a matrix multiplication Bx in order for the fitness (norm) of v to be calculated.
4
Methodology
We give a naïve sieving Algorithm 3. It checks the difference of all the possible pairings in the current population of vectors P for a shorter non-zero vector not already present in P . These newer and shorter vectors are collected in R. At the start of each iteration, we combine P and R, selecting out of the combination at most |P | successive shortest vectors to be reassigned as P . The sieving terminates when P 2 no longer contains a pair (u, v) whose difference’s length is shorter than any of the ones already in P . We show an example by reducing the bad basis Bbad given in eq. 1 of Sec. 2. The initial P is given as, 46 94 97 475 P = (3) 185 430 520 2300 and Figure 2 shows the new P at select iterations of a total of seven iterations that were ran.
8
A. Tashfeen and Q. Cheng
Input: P ⊂ L. Output: Reduced version of subset: P. 1: do 2: R←∅ 3: for each (u, v) ∈ P 2 4: t←v−u 5: if (⃗0 ̸= t ̸∈ P ) ∧ (∥t∥ < ∥u∥ ∨ ∥t∥ < ∥v∥) then R ← R ∪ {t} 6: P ← Select(P ∪ R) 7: while R ̸= ∅
Algorithm 3: Naïve sieving algorithm with global selection. Select(P ∪R) selects |P | shortest (fittest) vectors (individuals) among P ∪ R.
300
2000
200 1000
100
0
0 −100
−1000
(475, 2300) (97, 520) (94, 430) (46, 185)
−2000 −400
−200
0
200
(-51, -335) (-48, -245) (46, 185) (-3, -90)
−200 −300
400
−40
(a) Iteration 1.
0
20
40
(b) Iteration 2.
100
60
75
40
50
20
25 0
0
−25
−20
−50
(-43, -95) (-3, -90) (2, 60) (-1, -30)
−75 −100
−20
−40
−20
0
(c) Iteration 6.
20
40
(42, 65) (2, 60) (40, 5) (-1, -30)
−40 −60 −40
−20
0
20
40
(d) Iteration 7.
Fig. 2. Algorithm 3 reducing Bbad in Eq. 1 starting with population P in Eq. 3. Note that in this case, we find the shortest vector by solving the SBP exactly. The seventh iteration in Figure 2 contains Bgood of Equation 1.
Evolutionary Lattice Sieving
500
9
500 400
400
300 300
200 𝑢 𝑣 span(𝑢) projspan(𝑢) (𝑣) = 𝜇𝑢
200
100
0
100 0
b𝜇e𝑢 Our Offspring Laarhoven Offspring −100
0
100
200
300
400
Offspring Mutated Offsprings
−100 500
(a) Illustration of our crossover technique vs. Laarhoven’s. See Section 4.1.
−200 −500
−400
−300
−200
−100
0
100
200
(b) Fig. 3a offspring mutations. See Section 4.1.
Fig. 3. Illustration of crossover and mutation techniques from Section 4.1.
4.1
Our Genetic Algorithm for Sieving
Following is a specification for each of the components of the genetic algorithm 5 used in this paper to solve the apprSVP. Genotype. We represent vectors v = ⟨v1 , v2 , . . . , vd ⟩ ∈ L as is. Note that here L ⊆ Zd or L ⊆ Z[i]d (see Section 2). Fitness Function. We evaluate the fitness of a vector v by the inverse of its ℓ2 norm: Fitness(v) = ∥v∥−1 2 . Observe that one may also invert the squared norm. Crossover. For parents, u, v ∈ P , we may generate the offspring t, t = Cross(u, v) = v − ⌊µ⌉ u where
µ=
ℜ(u · v) ℑ(u · v) + i. u·u u·u
If u, v ∈ Zd then the imaginary part ℑ(u·v) = 0. We round off a complex number z = α + βi where (α, β) ∈ R2 by ⌊z⌉ = ⌊α⌉ + ⌊β⌉ i. See Figure 3a for a geometric interpretation of the crossover in 2 dimensions. The idea is that if (u, v) are near to each other then the offspring t is of high fitness but in the average case, (u, v) are not near. Letting u be the shorter vector we realise that multiple copies ⌊µ⌉ of u could be subtracted from v. This constant µ is used to evaluate the projection of v onto the span of u, i.e., projspan(u) (v) = µu. However, as seen in Figure 3a, projspan(u) (v) is not necessarily in the lattice. Therefore, instead of projspan(u) (v) we subtract ⌊µ⌉ u from v getting a much shorter (fitter) offspring than the Laarhoven’s offspring v − u. Mutation. The j th column of the initial population and the subsequent generations is given as Pj = Bcj . Laarhoven [17] represent each individual in the population as cj instead of Bcj . This enabled them to mutate Pj = Bcj by adding
10
A. Tashfeen and Q. Cheng
a small integral perturbation to ci,j . However, this representation requires a matrix multiplication before the fitness (inverse ℓ2 norm) of each individual can be calculated. In our representation, if an offspring was to be mutated, we may multiply µ (Section 4.1) by a normal random variable ξ ∼ N (1, 1) of mean and standard deviation 1, i.e., tmutated = v − ⌊ξµ⌉ u. The crossover step can now be given as Cross(u, v) = v − ⌊ξµ⌉ u where either ξ = 1 or ξ ∼ N (1, 1) under a small probability. As an example, for each ξ ∈ {0.1, 0.4, 0.7, 1, 1.3, 1.6, 1.9}, Figure 3b shows the corresponding six possible mutations of our offspring shown in Figure 3a. Initial Population. Before we proceed with the generation of the initial population using B, we may optionally compute the Hermite normal form of B as well as reduce it using the LLL algorithm for some δ. The Hermite normal form is to integral matrices what the reduced echelon form is for the matrices over the reals. Let n = |P |, we generate the initial population via a constant d by n binary matrix C like this: P = BC. If L(B) ⊆ Zd or B ∈ Zd×d , then let C ∈ {0, 1}d×n where Pr(Ci,j = 1) = ρ. However, if L(B) ⊆ Z[i]d or B ∈ Z[i]d×d then for α, β ∈ {0, 1} we have Ci,j = α + βi where Pr(α = 1) = Pr(β = 1) = ρ. Selection Strategy. Let P be the previous and R be the current generation. The next generation is then produced by picking the |P | successive shortest vectors from the pool P ∪ R and then assigning them back to P ← Elite(P ∪ R). P will now be sorted by vector length in ascending order. We will use this P to select the individuals for crossover. Let ui , vj be the ith and j th vectors in P then Algorithm 4 states how we can select pairings of vectors in P . Input: Population: P . Output: Generated pairs for reproduction. 1: for i ∈ {1, 2, 3, . . . |P | − 1} 2: for j ∈ {i + 1, . . . |P |} 3: yield (ui , vj )
Algorithm 4: yield (ui , vj ) yields each pair to Select(P ) in Algorithm 5.
4.2
Analysis of the GAs for Sieving
Let m count the max. generations, n = |P | be the size of the initial population and d be the dimension of the lattice. On average, our algorithm runs in O(dmn1.5 ). This due to the O(d) cost of each fitness evaluation times the total number of generations m times the total number of expected n1.5 crossovers. In the case of Laarhoven’s [17] algorithm, we keep the same m generations, n individuals and note that they consider all possible children for a potential insertion in the next generation. Furthermore, they represent the j th individual
Evolutionary Lattice Sieving
11
Input: (1) Basis: B, (2) Population size: n (3) Sampling density: ρ Output: Approximation of the shortest vector. 1: Cd,n ← (ci,j ∼ Bernoulli(ρ)) 2: P ← BC 3: R ← ∅ 4: do 5: P ← Elite(P ∪ R) 6: R←∅ 7: do 8: u, v ← Select(P ) 9: t ← Cross(u, v) 10: if (⃗0 ̸= t ̸∈ P ) ∧ (∥t∥ < ∥u∥ ∨ ∥t∥ < ∥v∥) 11: R ← R ∪ {t} 12: while |R| < n1.5 13: while ∀v ∈ P, Fitness(v) < w−1
Algorithm 5: Our genetic sieving algorithm. See Section 4.1.
Pj = Bcj as cj in contrast to Bcj to stay compatible with their mutation operation. Their representation of Pj as cj introduces a matrix multiplication (namely B multiplied on the left with cj ) each time fitness is to be calculated since fitness is a function of ∥Bcj ∥. Therefore, Laarhoven’s algorithm can be shown to run in O(d3 mn2 ) on average. The exponent 1.5 of n1.5 in our algorithm was determined by a combination of empirical analysis and heuristics from the original choices of δ in the LLL (Section 3.1).
5
Results
Recall that lattice-based cryptography relies on the inability of lattice reduction algorithms to solve the√apprSVP in high dimensions (d > 300) with an approximation factor α = O( d). For dimensions d ≤ 100 in integral and d ≤ 50 in module lattices, we optimally solve the apprSVP with an α < 2.05 (Table 1). Detailed results for reduction on SVP challenges [21] in dimensions 40 ≤ d ≤ 100 are given in Section 5.1. Parallelly, we generated random integral lattices of equal dimensions to further test the performance of Algorithm 5. Results on these lattices are given in Section 5.2. Finally, we reduce module lattices of the dimensions 20, 30, 40 and 50, giving the results in Section 5.3. The experiments reducing the SVP challenge and the random integral lattices in dimensions 40, 50, 60, 70 and 80 were carried out twice. Once with no mutations and once with 1% chance of mutation. The resulting shortest vectors were the same in either case. Although, the experiments with mutations took about twice as long. Afterwards, experiments on lattices of dimensions d ∈ {90, 100} and module lattices were therefore carried out without mutations. The stopping condition for each row in the results of Table 1 can be shown by letting w of Algorithm 5 be ℓ (the shortest/most fit vector found). In practice, we
12
A. Tashfeen and Q. Cheng
×107
LLL BKZ Our Sieve
6000
ℓ 2 norm of the shortest vector found
ℓ 2 norm of the shortest vector found
7000
5000 4000 3000 2000 40
50
60
70
80
90
2.0 1.5 1.0 0.5 0.0
100
40
Dimension
(a) Shortest vector length comparison in the SVP challenge lattices.
LLL BKZ Our Sieve
50
60
70
80
90
100
Dimension
(b) Shortest vector length comparison in the randomly generated lattices.
Fig. 4. Comparison of the shortest vector length found by different algorithms.
stopped once the difference of the mean population length between the current and the last generation was consecutively less than 1 for three generations. 5.1
Reducing SVP Challenge Lattices
We started by reducing each of the lattices using the LLL algorithm as described in Section 3.1 for δ = 1 − 10−7 . Note that the initial population included this reduced B as is. This implies that the algorithm must find something better than the final results of the LLL for a δ = 0.9999999 fairly close to 1. For the Algorithm 5 parameter ρ = 0.01, Table 1 summarises the results at the final step for each 40 ≤ d ≤ 100. Up until 80 dimensions, our results (length of the shortest vector) match the best ones found so far. Furthermore, these were all solved on an M2 Macbook Air with 24 GB of memory. 5.2
Reducing Random Integral Lattices
We generate these lattices L(B) by uniformly randomly generating each element bi,j of B between −d3 and d3 . Afterwards, we compute the Hermite normal form (this is to integral matrices what the reduced echelon form is for the matrices over the reals) of B and reduce it with the LLL algorithm for δ = 1 − 10−7 . For the Algorithm 5 parameter ρ = 0.01, Table 1 summarises the results at the final step for each 40 ≤ d ≤ 100. We optimally solve the apprSVP for α < 1.5 for all 40 ≤ d ≤ 100. 5.3
Reducing Module Lattices
We generate these lattices L(B) by generating each α + βi ∈ B containing α and β picked uniformly randomly between −d3 and d3 . Furthermore, to each basis vector bi ∈ B we add d/4 many other randomly chosen basis vectors bj ∈ B.
Evolutionary Lattice Sieving
13
For the same as before Alg. 5 parameter ρ = 0.01, Table 1 summarises the results at the final step. We solve the apprSVP for α < 2.05 for all 20 ≤ d ≤ 50. 5.4
Results Summary & Discussion
Among the SVP Challenge Lattices, for d ≤ 80 dimensions, our resultant short vectors match the known best ones found so far. For all of the integral and module lattices, we optimally solve the apprSVP with α < 1.5, and α < 2.05. We preprocessed the basis with the state of the art LLL algorithm for a δ = 0.9999999 fairly close to 1. This puts our algorithm in direct comparison with the LLL reduction algorithm. Figure 4 further compares the reduction power of LLL as well as BKZ with δ = 0.9999999 and the standard block-size of 10 against our algorithm. We outperform both the LLL and the BKZ. Laarhoven solved the same (and only attempted) 40 dimensional lattice as we did in our results. They reported 29 iterations starting with a set of 1500 lattice vectors to find the shortest vector of norm 1702 and an average vector of norm 2008 [17]. Our approach took 7 iterations starting with a set of 1000 lattice vectors to find the shortest vector of norm 1702 and an average vector of norm 1981. Laarhoven found the same shortest vector as we did in 1.9 seconds compared to the 0.06 seconds it took our approach. While we can not faithfully explain the difference in time due to the possible machine/implementation differences, we suspect the difference is due the absence of the matrix multiplication overhead in our algorithm as explained in Sections 4.1 and 4.2. The reduction in the number of generations can be explained by the optimisations inspired by the classical algorithms in our crossover operator (Section 4.1). Evolutionary sieving for the shortest vector remains a relatively new and under-explored area. While we presently do not anticipate it posing a direct threat to existing cryptographic algorithms, this paper demonstrates that interdisciplinary approaches, combining machine learning and number theory, can effectively reduce a lattice of 100 dimensions with a modest approximation factor. This promising intersection of fields opens up exciting future avenues.
6
Conclusion and Future Work
Sieving algorithms have become one of the most practical methods for the SVP. We improved Laarhoven’s [17] representation of the SVP for GAs by reducing the number of generations and population size required to obtain the same (or better average) results. Our improvements are due to the refined genotype and crossover born out of the insights from the classic number theoretic algorithms. We further showed the proposed algorithm’s reduction potential on the increasingly significant module lattices. It is important to recognize that scaling any method for dimensions beyond 100 presents considerable challenges due to the inherent complexities of lattice problems. This difficulty underscores the reliance of the state-of-the-art cryptographic schemes on such problems [4,3,5,6].
14
A. Tashfeen and Q. Cheng
We can advance our understanding of the reduction capabilities of evolutionary approaches in dimensions greater than 100 in various ways. For instance, managing the population as described by [13,10] or selection through techniques such as tournament selection could yield better results. Additionally, implementing more sophisticated crossover strategies, such as performing multiple steps of Gauss reduction on parent vectors, or employing a nearest neighbour search for parent selection could enhance the effectiveness of these approaches. Furthermore, evolutionary sieving techniques could be investigated within module lattices in rings beyond Gaussian integers, such as more general Cyclotomic fields. This multifaceted exploration holds the potential to significantly improve our ability to address the SVP in higher dimensions, thereby reinforcing the robustness of evolutionary sieving in integral and module lattices. Table 1. A comparison of the shortest vector length in each dimension (d) found via the Algorithm 5 (ℓ) against the expected shortest length due to the Gaussian Heuristic. Recall from Section 2.2 that the exact length of the shortest non-zero vector is unknown in the general case and therefore, for a sufficiently large d [14], we may rely on the Gaussian expected shortest length (σ). By Definition 2, ℓ/σ ≥ α. The column g is the total number of generations evolved and n gives the size of the initial population. SVP challenge lattices d
σ Alg. 5 (ℓ)
40 1560 50 1746 60 1916 70 2065 80 2205 90 2544 100 2468
α
g
SVP random integral lattices n
Alg. 5 (ℓ)
σ
α
g
n
1702.46 1.09 7 1000 212828 201343.89 0.95 10 800 1893.17 1.08 8 1250 522364 460101.23 0.88 13 1000 1943.40 1.01 16 9900 1113319 803170.35 0.72 25 3000 2142.60 1.04 11 49980 2071820 1411636.20 0.68 18 28000 2272.19 1.03 16 240000 3351770 2302176.05 0.69 16 160000 2500.40 0.98 25 1638000 5564035 6815686.92 1.22 18 540000 3578.23 1.45 16 1500000 8339504 12002723.15 1.44 16 1000000 module lattices d
σ
Alg. 5 (ℓ)
α
g
n
20 30 40 50
22947 136309 369551 863938
26188.63 177814.21 754691.69 1482020.58
1.14 1.30 2.04 1.72
5 4 4 5
2000 3000 4000 5000
Acknowledgments. We thank Dimitrios Diochnos and Dean Hougen for their constructive criticism and other valuable feedback on the manuscript and acknowledge the U. S. National Science Foundation for their support through the grant CCF-2530361. Disclosure of Interests. The authors have no competing interests to declare that are relevant to the content of this article.
Evolutionary Lattice Sieving
15
References 1. Abramkina, O., Yakubova, M., Serikov, T., Begimbayeva, Y., Yakubov, B.: Implementation of lattice theory into the tls to ensure secure traffic transmission in ip networks based on ip pbx asterisk. International Journal of Advanced Computer Science and Applications 15(10) (2024). https://doi.org/10.14569/IJACSA.2024. 0151076, http://dx.doi.org/10.14569/IJACSA.2024.0151076 2. Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of the thirty-third annual ACM symposium on Theory of computing. pp. 601–610 (2001) 3. Alagic, G., Alperin-Sheriff, J., Apon, D., Cooper, D., Dang, Q., Kelsey, J., Liu, Y.K., Miller, C., Moody, D., Peralta, R., Perlner, R., Robinson, A., SmithTone, D.: Status report on the second round of the nist post-quantum cryptography standardization process. US Department of Commerce, NIST (July 2020), url=https://csrc.nist.gov/pubs/ir/8309/final 4. Alagic, G., Alperin-Sheriff, J., Apon, D., Cooper, D., Dang, Q., Miller, C., Moody, D., Peralta, R., Perlner, R., Robinson, A., Smith-Tone, D., Liu, Y.K.: Status report on the first round of the nist post-quantum cryptography standardization process. US Department of Commerce, NIST (January 2019), url=https://csrc.nist.gov/ pubs/ir/8240/final 5. Alagic, G., Apon, D., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Miller, C., Moody, D., Peralta, R., Perlner, R., Robinson, A., Smith-Tone, D., Liu, Y.K.: Status report on the third round of the nist post-quantum cryptography standardization process. US Department of Commerce, NIST (July 2022), url=https://csrc.nist.gov/pubs/ir/8413/upd1/final 6. 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.: Status report on the fourth round of the nist post-quantum cryptography standardization process. US Department of Commerce, NIST (March 2025), https://csrc.nist.gov/pubs/ir/8545/final 7. Babai, L.: On lovász’lattice reduction and the nearest lattice point problem. Combinatorica 6, 1–13 (1986) 8. Balny, S., Delaplace, C., Dequen, G.: Another l makes it better? lagrange meets lll and may improve bkz pre-processing. In: 2025 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX). pp. 181–193. SIAM (2025) 9. de Boer, K., van Woerden, W.: Lattice-based cryptography: A survey on the security of the lattice-based NIST finalists. Cryptology ePrint Archive, Paper 2025/304 (2025), https://eprint.iacr.org/2025/304 10. Bosman, P.A., Luong, N.H., Thierens, D.: Expanding from discrete cartesian to permutation gene-pool optimal mixing evolutionary algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference 2016. pp. 637–644 (2016) 11. of Commerce, U.S.D.: Federal register/notices. Notice and request for nominations for candidate postquantum algorithms. 244, National Institute of Standards and Technology (December 2016), url=https://www.federalregister.gov/d/2016-30615 12. Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Advances in Cryptology– EUROCRYPT 2008: 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings 27. pp. 31–51. Springer (2008) 13. Goldman, B.W., Punch, W.F.: Parameter-less population pyramid. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation. pp. 785–792 (2014)
16
A. Tashfeen and Q. Cheng
14. Hoffstein, J., Pipher, J., Silverman, J.H., Silverman, J.H.: An introduction to mathematical cryptography, vol. 1, pp. 436, 377, 402, 405. Springer (2008) 15. Kalbach, A., Chinburg, T.: Lll algorithm for lattice basis reduction. arXiv preprint arXiv:2410.22196 (2024) 16. Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations. pp. 85–104. Plenum, New York (1972) 17. Laarhoven, T.: Evolutionary techniques in lattice sieving algorithms. In: Proceedings of the 11th International Joint Conference on Computational Intelligence. pp. 31–39. IJCCI 2019, SCITEPRESS - Science and Technology Publications, Lda, Setubal, PRT (2019). https://doi.org/10.5220/0007968800310039, https://doi.org/10.5220/0007968800310039 18. Lagarias, J.C., Odlyzko, A.M.: Solving low-density subset sum problems. Journal of the ACM (JACM) 32(1), 229–246 (1985) 19. Lidl, R., Pilz, G.: Applications of Lattices, pp. 56–119. Springer US, New York, NY (1984). https://doi.org/10.1007/978-1-4615-6465-2_2, https://doi.org/ 10.1007/978-1-4615-6465-2_2 20. Merkle, R.C., Hellman, M.E.: Hiding information and signatures in trapdoor knapsacks. In: Secure communications and asymmetric cryptosystems, pp. 197–215. Routledge (2019) 21. Nguyen, G.N.: Shortest vector problem challenge (darmstadt lattice challenge) (2025), https://www.latticechallenge.org/svp-challenge/, accessed: 2025-02-06 22. Pass, R.: Parallel repetition of zero-knowledge proofs and the possibility of basing cryptography on np-hardness. In: 21st Annual IEEE Conference on Computational Complexity (CCC’06). pp. 13–pp. IEEE (2006) 23. Russell, S.J., Norvig, P.: Artificial intelligence: a modern approach, p. 129. Pearson (2016) 24. Sun, Z., Gu, C., Zheng, Y.: A review of sieve algorithms in solving the shortest lattice vector problem. IEEE Access 8, 190475–190486 (2020) 25. Zhao, Z., Ding, J., Yang, B.Y.: Sieving with streaming memory access. IACR Transactions on Cryptographic Hardware and Embedded Systems 2025(2), 362–384 (2025)