pith. sign in

arxiv: 2605.29169 · v1 · pith:CVRKGQRWnew · submitted 2026-05-27 · 💻 cs.CR · cs.AI

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

Ahmad Tashfeen , Qi Cheng This is my paper

Pith reviewed 2026-06-29 11:06 UTC · model grok-4.3

classification 💻 cs.CR cs.AI
keywords shortest vector problemgenetic algorithmslattice sievingmodule latticespost-quantum cryptographyevolutionary computation
0
0 comments X

The pith

Incorporating domain-informed representation and crossover into genetic algorithm sieving improves performance on the shortest vector problem for both integral and module lattices.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper builds on Laarhoven's framing of Ajtai et al.'s lattice sieving as a genetic algorithm for finding short vectors. It introduces a representation of candidate vectors that encodes domain structure from the lattice and a crossover operator that respects that structure. The same operators apply directly to module lattices without separate redesign. A reader would care because module lattices underpin several post-quantum cryptosystems, so any practical improvement in sieving affects concrete security estimates against quantum attacks.

Core claim

By defining a domain-informed representation for vectors in the shortest vector problem together with a matching crossover operator, the genetic algorithm formulation of sieving can be strengthened for ordinary integer lattices and extended without modification to module lattices.

What carries the argument

Domain-informed SVP representation and crossover operator, which embed lattice geometry into the chromosome encoding and recombination step of the genetic algorithm.

If this is right

  • Genetic algorithm sieving becomes directly applicable to module-SVP instances that appear in module-LWE and module-SIS based cryptosystems.
  • The method preserves the known asymptotic complexity of the underlying sieving while potentially lowering practical iteration counts through guided recombination.
  • A single evolutionary framework now covers both integral and module settings without requiring distinct algorithm branches.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The representation could be reused to adapt other evolutionary heuristics to module lattices.
  • Security analyses of module-lattice cryptography may need to account for this style of attack if the performance gain materializes.
  • Analogous domain-informed operators might be developed for related problems such as the closest vector problem.
  • pith_inferences

Load-bearing premise

The new representation and crossover operator produce a net improvement in search efficiency on SVP instances rather than merely rewriting the same search space without measurable gain.

What would settle it

Empirical runs of the proposed genetic algorithm versus the baseline Laarhoven genetic algorithm on identical random integral-lattice and module-lattice instances that show no reduction in average runtime or no increase in success probability for recovering vectors of target length would falsify the claimed enhancement.

Figures

Figures reproduced from arXiv: 2605.29169 by Ahmad Tashfeen, Qi Cheng.

Figure 1
Figure 1. Figure 1: Example of a 2D lattice. Bbad =  95 47 460 215 Bgood =  1 40 30 5  (1) Good vs. Bad Basis [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 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 [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 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 ⊆ Z d or L ⊆ Z[i] d (see Section 2). Fitness Function. We evaluate the fitness of a vector v by… view at source ↗
Figure 4
Figure 4. Figure 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 populatio… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper claims to enhance Laarhoven's genetic-algorithm formulation of Ajtai et al.'s sieving for the Shortest Vector Problem by introducing a domain-informed representation of SVP vectors together with a corresponding crossover operator, and states that the same framework extends naturally to module lattices.

Significance. If the new operators were shown to reduce the number of lattice-vector evaluations or to increase the probability of recovering a shortest vector relative to the baseline GA, the work would be relevant to the concrete security analysis of lattice-based post-quantum schemes. No such demonstration is supplied.

major comments (2)
  1. [Abstract] Abstract: the central claim that the proposed domain-informed representation and crossover 'enhance' Laarhoven's GA is unsupported; the manuscript contains neither runtime measurements, success-rate tables, scaling plots, nor an analytic argument showing that the new operators reduce the expected number of norm evaluations or improve the success probability over the baseline.
  2. [Abstract] The extension to module lattices is asserted without any accompanying definition of the representation or crossover operator on module elements, nor any indication of how the GA fitness or selection steps are modified.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive feedback. The comments correctly identify that the abstract's enhancement claim lacks supporting evidence and that the module-lattice extension requires explicit definitions. We address both points below and will revise the manuscript to strengthen these aspects.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the proposed domain-informed representation and crossover 'enhance' Laarhoven's GA is unsupported; the manuscript contains neither runtime measurements, success-rate tables, scaling plots, nor an analytic argument showing that the new operators reduce the expected number of norm evaluations or improve the success probability over the baseline.

    Authors: We agree that the current manuscript does not supply runtime measurements, success-rate tables, scaling plots, or an analytic argument demonstrating improvement over the baseline GA. The work presents the domain-informed representation and crossover as a conceptual contribution derived from lattice structure. In revision we will add comparative experiments (runtime, success probability, and scaling) against Laarhoven's formulation; if space constraints preclude full experiments we will instead supply a short analytic argument bounding the expected reduction in norm evaluations. revision: yes

  2. Referee: [Abstract] The extension to module lattices is asserted without any accompanying definition of the representation or crossover operator on module elements, nor any indication of how the GA fitness or selection steps are modified.

    Authors: We acknowledge that the manuscript asserts a natural extension to module lattices without providing the required definitions or modifications. The revised version will include an explicit definition of the representation and crossover operator over module elements together with the corresponding changes to the fitness function and selection mechanism. revision: yes

Circularity Check

0 steps flagged

No circularity: proposal of domain-informed GA operators stands as independent methodological suggestion

full rationale

The abstract and description frame the contribution as an enhancement to Laarhoven's existing GA treatment of sieving, via new representation and crossover operators, with natural extension to module lattices. No equations, fitted parameters, self-citations, or uniqueness theorems are invoked in the provided text. The central claim does not reduce by construction to its inputs; it is a standard algorithmic proposal whose performance impact would require separate empirical validation outside the derivation itself. No load-bearing self-referential steps appear.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; ledger left empty pending full text.

pith-pipeline@v0.9.1-grok · 5625 in / 1040 out tokens · 31360 ms · 2026-06-29T11:06:33.199096+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 4 canonical work pages

  1. [1]

    International Journal of Advanced Computer Science and Applications15(10) (2024)

    Abramkina, O., Yakubova, M., Serikov, T., Begimbayeva, Y., Yakubov, B.: Imple- mentation 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 Applications15(10) (2024). https://doi.org/10.14569/IJACSA.2024. 0151076, http://dx.doi.org/10.14569/IJ...

    work page doi:10.14569/ijacsa.2024 2024

  2. [2]

    In: Proceedings of the thirty-third annual ACM symposium on Theory of computing

    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)

    2001

  3. [3]

    US Department of Commerce, NIST (July 2020), url=https://csrc.nist.gov/pubs/ir/8309/final

    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., Smith- Tone, D.: Status report on the second round of the nist post-quantum cryptog- raphy standardization process. US Department of Commerce, NIST (July 2020), url=https://csrc.nist.gov/pubs/ir/8309/final

    2020

  4. [4]

    US Department of Commerce, NIST (January 2019), url=https://csrc.nist.gov/ pubs/ir/8240/final

    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

    2019

  5. [5]

    US Department of Commerce, NIST (July 2022), url=https://csrc.nist.gov/pubs/ir/8413/upd1/final

    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 cryptog- raphy standardization process. US Department of Commerce, NIST (July 2022), url=https://csrc.nist.gov/pubs/ir/8413/upd1/final

    2022

  6. [6]

    US Department of Commerce, NIST (March 2025), https://csrc.nist.gov/pubs/ir/8545/final

    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), http...

    2025

  7. [7]

    Com- binatorica6, 1–13 (1986)

    Babai, L.: On lovász’lattice reduction and the nearest lattice point problem. Com- binatorica6, 1–13 (1986)

    1986

  8. [8]

    In: 2025 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX)

    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)

    2025

  9. [9]

    Cryptology ePrint Archive, Paper 2025/304 (2025), https://eprint.iacr.org/2025/304

    de Boer, K., van Woerden, W.: Lattice-based cryptography: A survey on the secu- rity of the lattice-based NIST finalists. Cryptology ePrint Archive, Paper 2025/304 (2025), https://eprint.iacr.org/2025/304

    2025

  10. [10]

    In: Proceedings of the Genetic and Evolutionary Computation Conference 2016

    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)

    2016

  11. [11]

    Notice and request for nominations for candidate postquantum algorithms

    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

    2016

  12. [12]

    In: Advances in Cryptology– EUROCRYPT 2008: 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008

    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)

    2008

  13. [13]

    In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

    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

    2014

  14. [14]

    Hoffstein, J., Pipher, J., Silverman, J.H., Silverman, J.H.: An introduction to math- ematical cryptography, vol. 1, pp. 436, 377, 402, 405. Springer (2008)

    2008

  15. [15]

    arXiv preprint arXiv:2410.22196 (2024)

    Kalbach, A., Chinburg, T.: Lll algorithm for lattice basis reduction. arXiv preprint arXiv:2410.22196 (2024)

    work page arXiv 2024

  16. [16]

    In: Complexity of Com- puter Computations

    Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Com- puter Computations. pp. 85–104. Plenum, New York (1972)

    1972

  17. [17]

    In: Pro- ceedings of the 11th International Joint Conference on Computational Intelli- gence

    Laarhoven, T.: Evolutionary techniques in lattice sieving algorithms. In: Pro- ceedings of the 11th International Joint Conference on Computational Intelli- gence. pp. 31–39. IJCCI 2019, SCITEPRESS - Science and Technology Pub- lications, Lda, Setubal, PRT (2019). https://doi.org/10.5220/0007968800310039, https://doi.org/10.5220/0007968800310039

    work page doi:10.5220/0007968800310039 2019

  18. [18]

    Journal of the ACM (JACM)32(1), 229–246 (1985)

    Lagarias, J.C., Odlyzko, A.M.: Solving low-density subset sum problems. Journal of the ACM (JACM)32(1), 229–246 (1985)

    1985

  19. [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

    work page doi:10.1007/978-1-4615-6465-2_2 1984

  20. [20]

    In: Secure communications and asymmetric cryptosystems, pp

    Merkle, R.C., Hellman, M.E.: Hiding information and signatures in trapdoor knap- sacks. In: Secure communications and asymmetric cryptosystems, pp. 197–215. Routledge (2019)

    2019

  21. [21]

    Nguyen, G.N.: Shortest vector problem challenge (darmstadt lattice challenge) (2025), https://www.latticechallenge.org/svp-challenge/, accessed: 2025-02-06

    2025

  22. [22]

    In: 21st Annual IEEE Conference on Computational Complexity (CCC’06)

    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)

    2006

  23. [23]

    Russell, S.J., Norvig, P.: Artificial intelligence: a modern approach, p. 129. Pearson (2016)

    2016

  24. [24]

    IEEE Access8, 190475–190486 (2020)

    Sun, Z., Gu, C., Zheng, Y.: A review of sieve algorithms in solving the shortest lattice vector problem. IEEE Access8, 190475–190486 (2020)

    2020

  25. [25]

    Zhao,Z.,Ding,J.,Yang,B.Y.:Sievingwithstreamingmemoryaccess.IACRTrans- actions on Cryptographic Hardware and Embedded Systems2025(2), 362–384 (2025)

    2025