A Greedy Global Framework for Lattice Reduction Using Deep Insertions
Authors
Sanjay Bhattacherjee, Julio Hernandez-Castro, Jack Moyler
Sanjay Bhattacherjee
School of Computing, University of Kent, Canterbury, United Kingdom
s dot bhattacherjee at kent dot ac dot uk
s dot bhattacherjee at kent dot ac dot uk
Julio Hernandez-Castro
ETSISI, Universidad Politécnica de Madrid, Madrid, Spain
jc dot hernandez dot castro at upm dot es
jc dot hernandez dot castro at upm dot es
Jack Moyler
School of Computing, University of Kent, Canterbury, United Kingdom
jdm58 at kent dot ac dot uk
jdm58 at kent dot ac dot uk
Abstract
LLL-style lattice reduction algorithms iteratively employ size reduction and reordering on ordered basis vectors to find progressively shorter, more orthogonal vectors. DeepLLL reorders the basis through deep insertions, yielding much shorter vectors than LLL. DeepLLL was introduced alongside BKZ, however, the latter has received greater attention and has emerged as the state-of-the-art. We first show that LLL-style algorithms work with a designated measure of basis quality and iteratively improves it; specifically, DeepLLL improves a sublattice measure based on the generalised Lovász condition. We then introduce a new generic framework X-GG for lattice reduction algorithms that work with a measure X of basis quality. X-GG globally searches for deep insertions that minimise X in each iteration. We instantiate the framework with two quality measures – basis potential (Pot) and squared sum (SS) – both of which have corresponding DeepLLL algorithms. We prove polynomial runtimes for our X-GG algorithms and also prove their output to be X-DeepLLL reduced. Our experiments on non-preprocessed bases show that X-GG produces better quality outputs whilst being much faster than the corresponding DeepLLL algorithms. We also compare SS-GG and the FPLLL implementation of BKZ with LLL-preprocessed bases. In small dimensions (40 to 210), SS-GG is significantly faster than BKZ with block sizes 8 to 12, while simultaneously also providing better output quality in most cases. In higher dimensions (250 and beyond), by varying the threshold $\delta$ for deep insertion, SS-GG offers new trade-offs between the output quality and runtime. On the one hand, it provides significantly better runtime than BKZ-5 with worse output quality; on the other hand, it is significantly faster than BKZ-21 while providing increasingly better output quality after around dimension 350.
References
[ABF+20]
Martin R. Albrecht, Shi Bai, Pierre-Alain Fouque, Paul Kirchner, Damien Stehlé, and Weiqiang Wen. Faster Enumeration-Based Lattice Reduction: Root Hermite Factor $k^{1/(2k)}$ Time $k^{k/8+o(k)}$. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, pages 186–212, Cham. 2020. Springer International Publishing. DOI: https://doi.org/10.1007/978-3-030-56880-1_7
[ACD+18]
Martin R. Albrecht, Benjamin R. Curtis, Amit Deo, Alex Davidson, Rachel Player, Eamonn W. Postlethwaite, Fernando Virdia, and Thomas Wunderer. Estimate All the {LWE, NTRU} Schemes!. In Dario Catalano and Roberto De Prisco, editors, Security and Cryptography for Networks, pages 351–367, Cham. 2018. Springer International Publishing. DOI: 10.1007/978-3-319-98113-0_19
[ADH+19]
Martin R. Albrecht, Léo Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W. Postlethwaite, and Marc Stevens. The General Sieve Kernel and New Records in Lattice Reduction. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, pages 717–746, Cham. 2019. Springer International Publishing. DOI: https://doi.org/10.1007/978-3-030-17656-3_25
[Akh03]
Ali Akhavi. The optimal LLL algorithm is still polynomial in fixed dimension. Theoretical Computer Science, 297(1):3–23, 2003. DOI: 10.1016/S0304-3975(02)00616-3
[Bab85]
László Babai. On Lovász' lattice reduction and the nearest lattice point problem (shortened version). In Proceedings of the 2nd Symposium of Theoretical Aspects of Computer Science, pages 13–20, Berlin, Heidelberg. 1985. Springer-Verlag. DOI: https://doi.org/10.1007/BFb0023990
[Bab86]
László Babai. On Lovász' lattice reduction and the nearest lattice point problem. Combinatorica, 6:1–13, March 1986. DOI: https://doi.org/10.1007/bf02579403
[BGW20]
Tristram Bogart, John Goodrick, and Kevin Woods. A parametric version of LLL and some consequences: Parametric shortest and closest vector problems. SIAM J. Discret. Math., 34(4):2363–2387, January 2020. DOI: 10.1137/20M1327422
[BM24]
Sanjay Bhattacherjee and Jack Moyler. Our implementations of some LLL-style algorithms. https://github.com/GG-LLL/Greedy-Global-LLL. 2024.
[CN11]
Yuanmi Chen and Phong Q. Nguyen. BKZ2.0: Better lattice security estimates. In Dong Hoon Lee and Xiaoyun Wang, editors, ASIACRYPT 2011, volume 7073 of LNCS, pages 1–20, Seoul, South Korea. December 2011. Springer. DOI: 10.1007/978-3-642-25385-0_1
[Coh93]
Henri Cohen. A course in computational algebraic number theory. Springer 1993. DOI: https://doi.org/10.1007/978-3-662-02945-9
[Cop96a]
Don Coppersmith. Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known. In Ueli Maurer, editor, Advances in Cryptology — EUROCRYPT '96, pages 178–189, Berlin, Heidelberg. 1996. Springer Berlin Heidelberg. DOI: 10.1007/3-540-68339-9_16
[Cop96b]
Don Coppersmith. Finding a Small Root of a Univariate Modular Equation. In Ueli Maurer, editor, Advances in Cryptology — EUROCRYPT '96, pages 155–165, Berlin, Heidelberg. 1996. Springer Berlin Heidelberg. DOI: 10.1007/3-540-68339-9_14
[CSV12]
Xiao-Wen Chang, Damien Stehlé, and Gilles Villard. Perturbation analysis of the QR factor R in the context of LLL lattice basis reduction. Mathematics of Computation, 81(279):1487–1511, 2012. DOI: https://doi.org/10.1090/s0025-5718-2012-02545-2
[CSV18]
Jingwei Chen, Damien Stehlé, and Gilles Villard. Computing an LLL-reduced basis of the orthogonal lattice. In Carlos Arreche, editor, Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, pages 127–133, New York, NY, USA. 2018. Association for Computing Machinery. DOI: 10.1145/3208976.3209013
[{Dar}10]
Darmstadt T.U.. SVP challenge. https://www.latticechallenge.org/svp-challenge/. 2010.
[FK15]
Masaharu Fukase and Kenji Kashiwabara. An accelerated algorithm for solving SVP based on statistical analysis. J. Inf. Process., 23:67–80, 2015. DOI: 10.2197/ipsjjip.23.67
[FSW14]
Felix Fontein, Michael Schneider, and Urs Wagner. PotLLL: a polynomial time version of LLL with deep insertions. Designs, Codes and Cryptography, 73(2):355–368, 2014. DOI: 10.1007/s10623-014-9918-8
[Gal12]
Steven D. Galbraith. Mathematics of public key cryptography. Cambridge University Press, USA, 1st edition. 2012. DOI: https://doi.org/10.1017/CBO9781139012843
[GM03]
Daniel Goldstein and Andrew Mayer. On the equidistribution of Hecke points. Forum Mathematicum, 15(2):165–189, 2003. DOI: 10.1515/form.2003.009
[GN08]
Nicolas Gama and Phong Q. Nguyen. Predicting lattice reduction. In Nigel P. Smart, editor, EUROCRYPT 2008, volume 4965 of LNCS, pages 31–51, Istanbul, Turkey. April 2008. Springer. DOI: 10.1007/978-3-540-78967-3_3
[Han09]
Guillaume Hanrot. LLL: A tool for effective Diophantine approximation, volume 1, pages 215–263. Springer Berlin Heidelberg, Berlin, Heidelberg, 1st edition. 2009. DOI: 10.1007/978-3-642-02295-1_6
[HG97]
Nicholas Howgrave-Graham. Finding small roots of univariate modular equations revisited. In Michael Darnell, editor, Crytography and Coding, pages 131–142, Berlin, Heidelberg. 1997. Springer Berlin Heidelberg. DOI: 10.1007/BFb0024458
[HG07]
Nicholas A. Howgrave-Graham. Isodual reduction of lattices. https://eprint.iacr.org/2007/105. Cryptology ePrint Archive, Paper 2007/105. 2007.
[HLP+23]
Guillaume Hanrot, Vincent Lefèvre, Patrick Pélissier, Philippe Théveny, and Paul Zimmermann. The GNU MPFR Library. Available at https://www.mpfr.org/index.html. 2023.
[KEF21]
Paul Kirchner, Thomas Espitau, and Pierre-Alain Fouque. Towards faster polynomial-time lattice reduction. In Tal Malkin and Chris Peikert, editors, 2021, Part II, volume 12826 of LNCS, pages 760–790, Virtual Event. August 2021. Springer. DOI: 10.1007/978-3-030-84245-1_26
[Kl{\"u}09]
Jürgen Klüners. The van Hoeij algorithm for factoring polynomials, volume 1, pages 283–291. Springer Berlin Heidelberg, Berlin, Heidelberg, 1st edition. 2009. DOI: 10.1007/978-3-642-02295-1_8
[KS01]
Henrik Koy and Claus Peter Schnorr. Segment LLL-reduction of lattice bases. In Joseph H. Silverman, editor, Cryptography and Lattices, pages 67–80. 2001. Springer Berlin Heidelberg. DOI: 10.1007/3-540-44670-2_7
[Len01]
Hendrik W. Lenstra. Flags and lattice basis reduction. In Carles Casacuberta, Rosa Maria Miró-Roig, Joan Verdera, and Sebastià Xambó-Descamps, editors, European Congress of Mathematics, pages 37–51, Basel. 2001. Birkhäuser Basel. DOI: https://doi.org/10.1007/978-3-0348-8268-2_3
[LLL82]
Arjen K. Lenstra, Hendrik Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261:515–534, 1982. DOI: 10.1007/BF01457454
[LPSW19]
Changmin Lee, Alice Pellet-Mary, Damien Stehlé, and Alexandre Wallet. An LLL algorithm for module lattices. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part II, volume 11922 of LNCS, pages 59–90, Kobe, Japan. December 2019. Springer. DOI: 10.1007/978-3-030-34621-8_3
[MSV09]
Ivan Morel, Damien Stehlé, and Gilles Villard. H-LLL: using householder inside LLL. In John P. May, editor, Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, pages 271–278, New York, NY, USA. 2009. Association for Computing Machinery. DOI: 10.1145/1576702.1576740
[NS01]
Phong Q. Nguyen and Jacques Stern. The two faces of lattices in cryptology. In Joseph H. Silverman, editor, Cryptography and Lattices, pages 146–180, Berlin, Heidelberg. 2001. Springer Berlin Heidelberg. DOI: 10.1007/3-540-44670-2_12
[NS06]
Phong Q. Nguyen and Damien Stehlé. LLL on the average. In Florian Hess, Sebastian Pauli, and Michael Pohst, editors, Proceedings of the 7th International Conference on Algorithmic Number Theory, pages 238–256, Berlin, Heidelberg. 2006. Springer-Verlag. DOI: 10.1007/11792086_18
[NS09a]
Phong Q. Nguyen and Damien Stehlé. An LLL algorithm with quadratic complexity. SIAM Journal on Computing, 39(3):874–903, 2009. DOI: 10.1137/070705702
[NS09b]
Phong Q. Nguyen and Damien Stehlé. Low-Dimensional Lattice Basis Reduction Revisited. ACM Trans. Algorithms, 5(4), November 2009. DOI: 10.1145/1597036.1597050
[NS16]
Arnold Neumaier and Damien Stehlé. Faster LLL-type reduction of lattice bases. In Markus Rosenkranz, editor, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, pages 373–380, New York, NY, USA. 2016. Association for Computing Machinery. DOI: 10.1145/2930889.2930917
[NV09]
Phong Q. Nguyen and Brigitte Valle. The LLL algorithm: survey and applications. Springer, 1st edition. 2009. DOI: https://doi.org/10.1007/978-3-642-02295-1
[Odl84]
A. Odlyzko. Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir's fast signature scheme. IEEE Transactions on Information Theory, 30(4):594–601, 1984. DOI: 10.1109/TIT.1984.1056942
[PSZ15]
Thomas Plantard, Willy Susilo, and Zhenfei Zhang. LLL for ideal lattices: re-evaluation of the security of Gentry–Halevi's FHE scheme. Des. Codes Cryptography, 76(2):325–344, August 2015. DOI: 10.1007/s10623-014-9957-1
[RH23]
Keegan Ryan and Nadia Heninger. Fast Practical Lattice Reduction Through Iterated Compression. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, pages 3–36, Cham. 2023. Springer Nature Switzerland. DOI: https://doi.org/10.1007/978-3-031-38548-3_1
[SB10]
Michael Schneider and Johannes Buchmann. Extended lattice reduction experiments using the BKZ algorithm. In Sicherheit 2010. Sicherheit, Schutz und Zuverlässigkeit, pages 241–251. Gesellschaft für Informatik e.V., Bonn 2010.
[SBL09]
Michael Schneider, Johannes Buchmann, and Richard Lindner. Probabilistic analysis of LLL reduced bases. In Johannes A. Buchmann, John Cremona, and Michael E. Pohst, editors, Algorithms and Number Theory, volume 9221 of Dagstuhl Seminar Proceedings (DagSemProc), pages 1–6, Dagstuhl, Germany. 2009. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. DOI: 10.4230/DagSemProc.09221.4
[SE94]
Claus-Peter Schnorr and Martin Euchner. Lattice basis reduction: improved practical algorithms and solving subset sum problems. Mathematical programming, 66(1):181–199, 1994. DOI: 10.1007/BF01581144
[Sho21]
Victor Shoup. NTL: A library for doing number theory. Available at https://github.com/libntl/ntl. 2021.
[{The}23]
The FPLLL development team. FPLLL, a lattice reduction library, Version: 5.4.4. Available at https://github.com/fplll/fplll. 2023.
[TKH18]
Tadanori Teruya, Kenji Kashiwabara, and Goichiro Hanaoka. Fast Lattice Basis Reduction Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem. In Michel Abdalla and Ricardo Dahab, editors, Public-Key Cryptography – PKC 2018, pages 437–460, Cham. 2018. Springer International Publishing. DOI: https://doi.org/10.1007/978-3-319-76578-5_15
[YY18]
Junpei Yamaguchi and Masaya Yasuda. Explicit formula for Gram–Schmidt vectors in LLL with deep insertions and its applications. In Jerzy Kaczorowski, Josef Pieprzyk, and Jacek Pomykała, editors, Number-Theoretic Methods in Cryptology, pages 142–160, Cham. 2018. Springer International Publishing. DOI: https://doi.org/10.1007/978-3-319-76620-1_9
[YY19]
Masaya Yasuda and Junpei Yamaguchi. A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram–Schmidt lengths. Designs, Codes and Cryptography, 87(11):2489–2505, 2019. DOI: 10.1007/s10623-019-00634-9
[YYS+17]
Masaya Yasuda, Kazuhiro Yokoyama, Takeshi Shimoyama, Jun Kogure, and Takeshi Koshiba. Analysis of decreasing squared-sum of Gram–Schmidt lengths for short lattice vectors. Journal of Mathematical Cryptology, 11(1):1–24, 2017. DOI: 10.1515/jmc-2016-0008
PDF
History
Submitted: 2024-10-09
Accepted: 2025-03-11
Published: 2025-04-08
Accepted: 2025-03-11
Published: 2025-04-08
How to cite
Sanjay Bhattacherjee, Julio Hernandez-Castro, and Jack Moyler, A Greedy Global Framework for Lattice Reduction Using Deep Insertions. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/aevuommol.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.