Abstract
The security of lattice-based cryptosystems such as NTRU, GGH and Ajtai-Dwork essentially relies upon the intractability of computing a shortest non-zero lattice vector and a closest lattice vector to a given target vector in high dimensions. The best algorithms for these tasks are due to Kannan, and, though remarkably simple, their complexity estimates have not been improved since over twenty years. Kannan’s algorithm for solving the shortest vector problem (SVP) is in particular crucial in Schnorr’s celebrated block reduction algorithm, on which rely the best known generic attacks against the lattice-based encryption schemes mentioned above. In this paper we improve the complexity upper-bounds of Kannan’s algorithms. The analysis provides new insight on the practical cost of solving SVP, and helps progressing towards providing meaningful key-sizes.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Agrell, E., Eriksson, T., Vardy, A., Zeger, K.: Closest point search in lattices. IEEE Trans. Inform. Theory 48(8), 2201–2214 (2002)
Ajtai, M.: The shortest vector problem in l 2 is NP-hard for randomized reductions (extended abstract). In: Proc. of STOC 1998, pp. 284–293. ACM Press, New York (1998)
Ajtai, M.: The worst-case behavior of Schnorr’s algorithm approximating the shortest nonzero vector in a lattice. In: Proc. of STOC 2003, pp. 396–406. ACM Press, New York (2003)
Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: Proc. of STOC 1997, pp. 284–293. ACM Press, New York (1997)
Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proc. STOC 2001, pp. 601–610. ACM Press, New York (2001)
Babai, L.: On Lovász lattice reduction and the nearest lattice point problem. Combinatorica 6, 1–13 (1986)
Blömer, J.: Closest vectors, successive minima and dual-HKZ bases of lattices. In Proc. of ICALP 2000. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 248–259. Springer, Heidelberg (2000)
Coppersmith, D., Shamir, A.: Lattice attacks on NTRU. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 52–61. Springer, Heidelberg (1997)
Fincke, U., Pohst, M.: A procedure for determining algebraic integers of given norm. In: van Hulzen, J.A. (ed.) ISSAC 1983 and EUROCAL 1983. LNCS, vol. 162, pp. 194–202. Springer, Heidelberg (1983)
Gama, N., Howgrave-Graham, N., Koy, H., Nguyen, P.: Rankin’s constant and blockwise lattice reduction. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 112–130. Springer, Heidelberg (2006)
Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 112–131. Springer, Heidelberg (1997)
Haviv, I., Regev, O.: Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In: Proc. of STOC 2007 (2007)
Helfrich, B.: Algorithms to construct Minkowski reduced and Hermite reduced lattice bases. Theoret. Comput. Sci. 41, 125–139 (1985)
Hermite, C.: Extraits de lettres de M. Hermite à M. Jacobi sur différents objets de la théorie des nombres, deuxième lettre. J. Reine Angew. Math. 40, 279–290 (1850)
Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU : a ring based public key cryptosystem. In: Buhler, J.P. (ed.) Algorithmic Number Theory. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998)
Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: Proc. of STOC 1983, pp. 99–108. ACM Press, New York (1983)
Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 513–534 (1982)
Magma. The Magma computational algebra system for algebra, number theory and geometry. Available at http://magma.maths.usyd.edu.au/magma/
Martinet, J.: Perfect Lattices in Euclidean Spaces. Springer, Heidelberg (2002)
Mazo, J., Odlyzko, A.: Lattice points in high-dimensional spheres. Monatsh. Math. 110, 47–61 (1990)
Micciancio, D., Goldwasser, S.: Complexity of lattice problems: a cryptographic perspective. Kluwer Academic Publishers, Dordrecht (2002)
Minkowski, H.: Geometrie der Zahlen. Teubner-V (1896)
Nguyen, P.: Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto’97. In: Wiener, M.J. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 288–304. Springer, Heidelberg (1999)
Nguyen, P., Stehlé, D.: LLL on the average. In: Hess, F., Pauli, S., Pohst, M. (eds.) Algorithmic Number Theory. LNCS, vol. 4076, pp. 238–256. Springer, Heidelberg (2006)
Nguyen, P., Stern, J.: Cryptanalysis of the Ajtai-Dwork cryptosystem. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 223–242. Springer, Heidelberg (1998)
Nguyen, P., Vidick, T.: Assessing sieve algorithms for the shortest vector problem. Draft (2007)
Regev, O.: Lecture notes of lattices in computer science, taught at the Computer Science Tel Aviv University. Available at http://www.cs.tau.il/~odedr
Schnorr, C.P.: A hierarchy of polynomial lattice basis reduction algorithms. Theoret. Comput. Sci. 53, 201–224 (1987)
Schnorr, C.P.: Lattice reduction by random sampling and birthday methods. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 145–156. Springer, Heidelberg (2003)
Schnorr, C.P., Euchner, M.: Lattice basis reduction : improved practical algorithms and solving subset sum problems. Math. Programming 66, 181–199 (1994)
Schnorr, C.P., Hörner, H.H.: Attacking the Chor-Rivest cryptosystem by improved lattice reduction. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 1–12. Springer, Heidelberg (1995)
Shoup, V.: NTL, Number Theory C++ Library. Available at http://www.shoup.net/ntl/
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hanrot, G., Stehlé, D. (2007). Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm. In: Menezes, A. (eds) Advances in Cryptology - CRYPTO 2007. CRYPTO 2007. Lecture Notes in Computer Science, vol 4622. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74143-5_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-74143-5_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74142-8
Online ISBN: 978-3-540-74143-5
eBook Packages: Computer ScienceComputer Science (R0)