Domain-Informed Representation for Evolutionary Sieving in Integral and Module Lattices

Ahmad Tashfeen ( ), Qi Cheng · 2026

Read Domain-Informed Representation for Evolutionary Sieving in Integral and Module Lattices by Ahmad Tashfeen ( ), Qi Cheng (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-29169.txt.

Introduction

Ahmad Tashfeen and Qi Cheng strengthen sieving for the shortest vector problem, the backbone of modern quantum-safe cryptography. Older cryptography rests on integer factorization and discrete logs, both open to attack by a fully working quantum computer, threatening even data stored today. The authors enhance Laarhoven's genetic view of Ajtai and coauthors' sieving with field-aware vector codes and crossover. Their approach extends from integral lattices to module lattices, giving quantum-safe schemes a sharper tool against future decryption.

Catalog record

CREATORAhmad Tashfeen ( ), Qi Cheng
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37776
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2605.29169

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Domain-Informed Representation for Evolutionary Sieving in Integral and Module Lattices Ahmad Tashfeen ( ), Qi Cheng 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. 1 Introduction Lattices model various real-world systems, e.g., relay circuits, plumbing lines, public roads and digital networks [ 18 , 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, NIST 1 1 1 U. S. Department of Commerce’s National Institute of Standards and Technology launched an initiative [ 21 ] 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–K yber 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 [ 10 , 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 [ 20 ] are done via some sieving technique [ 24 ] . Laarhoven’s [ 16 ] treatment of sieving as a genetic algorithm (GA) enabled the application of the 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 theory 2 2 2 Optimisations through the latest machine learning techniques remain an excellent opportunity for future research. . This choice allows our results to be directly comparable to Laarhoven’s [ 16 ] 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 [ 20 ] and randomly generated problems till 100 dimensions improving application & scalability of Laarhoven’s approach [ 16 ] . 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 \mathbb{N},\mathbb{Z},\mathbb{R}, and \mathbb{C} be the natural, integer, real and complex numbers respectively. Consider a basis matrix \mathcal{B}\in\mathbb{R}^{d\times d} with d linearly independent column vectors \{b_{i}\in\mathbb{R}^{d}:1\leq i\leq d\} such that b_{i} is the i^{\text{th}} column of \mathcal{B} . We recall a possibly transformed d dimensional Euclidean space as \{\mathcal{B}x:x\in\mathbb{R}^{d}\} , if we restrict \mathcal{B}x to only the integral linear combinations x\in\mathbb{Z}^{d} , we obtain a lattice \mathcal{L}(\mathcal{B})=\{\mathcal{B}x:x\in\mathbb{Z}^{d}\} . The dimension of a lattice is \dim(\mathcal{L})=d , i.e., the number of column-vectors in the basis matrix \mathcal{B} and the determinant similarly {\det\mathcal{L}(\mathcal{B})=\left|\det\mathcal{B}\right|} . If \mathcal{B} also has d number of rows, we call \mathcal{L} a full rank lattice . \mathbb{R}^{d} is now the ambient space for the reduced set of vectors that are in the lattice \mathcal{L} . The group operation of a lattice is the vector sum, v+u\in\mathcal{L} such that u,v\in\mathcal{L} . Integral Lattices If we further restrict \mathcal{B}\in\mathbb{Z}^{d\times d} , the resulting lattice is known as an integral lattice . You might imagine a trivial lattice \mathbb{Z}^{2} 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 . \displaystyle\mathcal{B}_{\text{bad}} \displaystyle=\begin{bmatrix}95&47\\ 460&215\end{bmatrix} (1) \displaystyle\mathcal{B}_{\text{good}} \displaystyle=\begin{bmatrix}1&40\\ 30&5\end{bmatrix} Figure 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 [ 10 ] formed over the Gaussian integers \mathbb{Z}[i]=\{\alpha+\beta i:(\alpha,\beta)\in\mathbb{Z}^{2}\} where i^{2}=-1 . Despite the name, Gaussian integers are complex numbers \alpha+\beta i where both, the real \Re(\alpha+\beta i)=\alpha and the imaginary \Im(\alpha+\beta i)=\beta parts are limited to the integers. We can similarly form a lattice, this time in the ambient space of complex numbers \mathbb{C} , by letting \mathcal{B}\in\mathbb{Z}[i]^{d\times d} for the lattice {\mathcal{L}=\{\mathcal{B}x:x\in\mathbb{Z}[i]^{d}\}} . The norm of a v\in\mathbb{Z}[i]^{d} is given as \lVert v\rVert_{2}^{2}=v^{H}v=|v_{1}|^{2}+|v_{2}|^{2}+\cdots+|v_{d}|^{2} where |v_{j}|^{2}=\alpha^{2}+\beta^{2} for v_{j}=\alpha+\beta i . The vector v^{H} is known as the conjugate transpose of v . Hadamard Ratio The \mathcal{H}(\mathcal{B})=\sqrt[d]{\det\mathcal{L}(\mathcal{B})/\lVert b_{1}\rVert\lVert b_{2}\rVert\cdots\lVert b_{d}\rVert} is used as a measure of orthogonality in-between the basis vectors b_{i}\in\mathcal{B} . Put simply, the closer this ratio is to 1 for a basis \mathcal{B} , the more orthogonal it is. 2.1 Lattice Problems Both the SVP and the Closest Vector Problem ( CVP ) are \mathcal{NP} -hard 3 3 3 However, SVP is \mathcal{NP} -hard under a randomised reduction. . Let \lVert v\rVert be the \ell^{2} norm of a vector v . Definition 1 (Shortest Vector Problem ( SVP )) Find the shortest non-zero vector v\in\mathcal{L} such that for all u\in\mathcal{L} where v\neq u , we have \lVert v\rVert\leq\lVert u\rVert . Definition 2 (Approximate Shortest Vector Problem ( apprSVP )) Let \alpha\geq 1 be an approximation factor and find a v\in\mathcal{L} such that \lVert v\rVert is no bigger than \alpha times the length of the shortest non-zero vector , i.e., \lVert v\rVert\leq\alpha\lVert v_{\text{shortest}}\rVert . Definition 3 (Closest Vector Problem ( CVP )) For w\in\mathbb{R}^{d} where w\not\in\mathcal{L} find a vector v\in\mathcal{L} that is closest to w and \lVert w-v\rVert>0 , i.e., \min_{v\in\mathcal{L}}\lVert w-v\rVert . Definition 4 (Shortest Basis Problem ( SBP ))

Read the complete text