zbMATH — the first resource for mathematics

PotLLL: a polynomial time version of LLL with deep insertions. (English) Zbl 1297.94067
Summary: Lattice reduction algorithms have numerous applications in number theory, algebra, as well as in cryptanalysis. The most famous algorithm for lattice reduction is the LLL algorithm. In polynomial time it computes a reduced basis with provable output quality. One early improvement of the LLL algorithm was LLL with deep insertions (DeepLLL). The output of this version of LLL has higher quality in practice but the running time seems to explode. Weaker variants of DeepLLL, where the insertions are restricted to blocks, behave nicely in practice concerning the running time. However no proof of polynomial running time is known. In this paper PotLLL, a new variant of DeepLLL with provably polynomial running time, is presented. We compare the practical behavior of the new algorithm to classical LLL, BKZ as well as blockwise variants of DeepLLL regarding both the output quality and running time.

94A60 Cryptography
68R05 Combinatorics in computer science
Full Text: DOI arXiv
[1] Chen Y., Nguyen P.Q.: BKZ 2.0: better lattice security estimates. In: Lee D.H., Wang X. (eds.) Advances in Cryptology—ASIACRYPT 2011. Lecture Notes in Computer Science, vol. 7073, pp. 1-20. Springer, Heidelberg (2011). · Zbl 1227.94037
[2] Cong L., Mow W.H., Howgrave-Graham N.: Reduced and fixed-complexity variants of the lll algorithm for communications. IEEE Trans. Commun. 61(3), 1040-1050 (2013).
[3] Fontein F., Schneider M., Wagner U.: A polynomial time version of LLL with deep insertions. In: Preproceedings of the International Workshop on Coding and Cryptography, WCC ’13 (2013). · Zbl 1297.94067
[4] Gama N., Nguyen P.Q.: Predicting lattice reduction. In: Smart N. (ed.) Advances in Cryptology—EUROCRYPT 2008. LNCS, vol. 4965, pp. 31-51. Springer, Heidelberg (2008). · Zbl 1149.94314
[5] Hanrot G., Pujol X., Stehlé D.: Analyzing blockwise lattice algorithms using dynamical systems. In: Rogaway P. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 6841, pp. 447-464. Springer, Heidelberg (2011). · Zbl 1287.94072
[6] Lenstra A.K., Lenstra Jr H.W., Lovász L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515-534 (1982). · Zbl 0488.12001
[7] Martinet J.: Perfect lattices in Euclidean Spaces. Grundlehren der Mathematischen Wissenschaften (Fundamental Principles of Mathematical Sciences), vol. 327. Springer-Verlag, Berlin (2003). · Zbl 1017.11031
[8] Micciancio D., Goldwasser S.: Complexity of Lattice Problems: A Cryptographic Perspective. The Kluwer International Series in Engineering and Computer Science, vol. 671. Kluwer Academic Publishers, Boston (2002). · Zbl 1140.94010
[9] Micciancio D., Regev O.: Lattice-based cryptography. In: Bernstein D.J., Buchmann J., Dahmen E. (eds.) Post-quantum Cryptography, pp. 147-191. Springer, Heidelberg (2008). · Zbl 1161.81324
[10] Nguyen P.Q., Stehlé D.: Floating-point LLL revisited. In: Cramer R. (ed.) Advances in Cryptology—EUROCRYPT 2005. LNCS, vol. 3494, pp. 215-233. Springer, Heidelberg (2005).
[11] Nguyen P.Q., Stehlé D.: LLL on the average. In: Hess F., Pauli S., Pohst M.E. (eds.) ANTS. Lecture Notes in Computer Science, vol. 4076, pp. 238-256. Springer, Heidelberg (2006). · Zbl 1143.11357
[12] Nguyen P.Q., Vallée B.: The LLL Algorithm: Survey and Applications. Information Security and Cryptography. Springer, Heidelberg (2010).
[13] Novocin A., Stehlé D., Villard G.: An LLL-reduction algorithm with quasi-linear time complexity: extended abstract. In: STOC, pp. 403-412. ACM, New York (2011). · Zbl 1288.68294
[14] Schnorr C.-P., Euchner M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66(2), 181-199 (1994). · Zbl 0829.90099
[15] Schnorr C.-P.: Block reduced lattice bases and successive minima. Comb. Prob. Comput. 3, 507-522 (1994). · Zbl 0845.11025
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.