×

zbMATH — the first resource for mathematics

A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths. (English) Zbl 1431.68084
Summary: Lattice basis reduction algorithms have been used in cryptanalysis. The most famous algorithm is LLL, proposed by Lenstra, Lenstra, Lovász, and one of its typical improvements is LLL with deep insertions (DeepLLL). A DeepLLL-reduced basis is LLL-reduced, and hence its quality is at least as good as LLL. In practice, DeepLLL often outputs a more reduced basis than LLL, but no theoretical result is known. First, we show provable output quality of DeepLLL, strictly better than that of LLL. Second, as a main work of this paper, we propose a new variant of DeepLLL. The squared-sum of Gram-Schmidt lengths of a basis is related with the computational hardness of lattice problems such as the shortest vector problem (SVP). Given an input basis, our variant monotonically decreases the squared-sum by a given factor at every deep insertion. This guarantees that our variant runs in polynomial-time.

MSC:
68R05 Combinatorics in computer science
68W40 Analysis of algorithms
94A60 Cryptography
Software:
BKZ; DeepLLL; NTL; PotLLL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ajtai M.: Generating random lattices according to the invariant distribution, Draft of March (2006).
[2] Aono, Yoshinori; Nguyen, Phong Q., Random Sampling Revisited: Lattice Enumeration with Discrete Pruning, 65-102, (2017), Cham · Zbl 1415.94404
[3] Aono, Yoshinori; Wang, Yuntao; Hayashi, Takuya; Takagi, Tsuyoshi, Improved Progressive BKZ Algorithms and Their Precise Cost Estimation by Sharp Simulator, 789-819, (2016), Berlin, Heidelberg · Zbl 1385.94007
[4] Babai, L., On Lovász’ lattice reduction and the nearest lattice point problem, Combinatorica, 6, 1-13, (1986) · Zbl 0593.68030
[5] Bremner M.R.: Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications. CRC Press, Boca Raton (2011).
[6] Chen, Yuanmi; Nguyen, Phong Q., BKZ 2.0: Better Lattice Security Estimates, 1-20, (2011), Berlin, Heidelberg · Zbl 1227.94037
[7] Cohen H.: A Course in Computational Algebraic Number Theory, vol. 138. Graduate Texts in MathSpringer, Berlin (1993). · Zbl 0786.11071
[8] Darmstadt T.U.: SVP Challenge. http://www.latticechallenge.org/svp-challenge/.
[9] Ducas, Léo, Shortest Vector from Lattice Sieving: A Few Dimensions for Free, 125-145, (2018), Cham · Zbl 1423.94069
[10] Fukase, M.; Kashiwabara, K., An accelerated algorithm for solving SVP based on statistical analysis, J. Inf. Process., 23, 1-15, (2015)
[11] Fontein, F.; Schneider, M.; Wagner, U., PotLLL: a polynomial time version of LLL with deep insertions, Des. Codes Cryptogr., 73, 355-368, (2014) · Zbl 1297.94067
[12] Galbraith S.D.: Mathematics of Public Key Cryptography. Cambridge University Press, Cambridge (2012). · Zbl 1238.94027
[13] Gama N., Nguyen P.Q.: Predicting lattice reduction. In: Advances in Cryptology—EUROCRYPT 2008, Lecture Notes in Computer Science 4965, pp. 31-51 (2008). · Zbl 1149.94314
[14] Goldstein, D.; Mayer, A., On the equidistribution of Hecke points, Forum Math., 15, 165-189, (2003) · Zbl 1048.11057
[15] Hanrot, Guillaume; Pujol, Xavier; Stehlé, Damien, Analyzing Blockwise Lattice Algorithms Using Dynamical Systems, 447-464, (2011), Berlin, Heidelberg · Zbl 1287.94072
[16] Korkine, A.; Zolotarev, G., Sur les formes quadratiques, Math. Ann., 6, 366-389, (1873) · JFM 05.0109.01
[17] Lenstra, AK; Lenstra, HW; Lovász, L., Factoring polynomials with rational coefficients, Math. Ann., 261, 515-534, (1982) · Zbl 0488.12001
[18] Matsuda Y., Teruya T., Kashiwabara K.: Estimation of the success probability of random sampling by the Gram-Charlier approximation. IACR ePrint 2018/815 (2018).
[19] Micciancio D., Goldwasser S.: Complexity of Lattice Problems: A Cryptographic Perspective. Springer, New York (2012). · Zbl 1140.94010
[20] Nguyen Q., Vallée B.: The LLL Algorithm. Information Security Cryptography (2010).
[21] Schnorr, Claus Peter, Lattice Reduction by Random Sampling and Birthday Methods, 145-156, (2003), Berlin, Heidelberg · Zbl 1035.68113
[22] Schnorr, CP; Euchner, M., Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Math. Program., 66, 181-199, (1994) · Zbl 0829.90099
[23] Shoup V.: NTL: a library for doing number theory. http://www.shoup.net/ntl/.
[24] Teruya, Tadanori; Kashiwabara, Kenji; Hanaoka, Goichiro, Fast Lattice Basis Reduction Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem, 437-460, (2018), Cham · Zbl 1439.94062
[25] Yamaguchi, Junpei; Yasuda, Masaya, Explicit Formula for Gram-Schmidt Vectors in LLL with Deep Insertions and Its Applications, 142-160, (2018), Cham · Zbl 1423.94115
[26] Yasuda, M.; Yokoyama, K.; Shimoyama, T.; Kogure, J.; Koshiba, T., Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors, J. Math. Cryptol., 11, 1-24, (2017) · Zbl 1391.65099
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.