Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Predicting Lattice Reduction

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 4965))

  • 5054Accesses

  • 276Citations

Abstract

Despite their popularity, lattice reduction algorithms remain mysterious cryptanalytical tools. Though it has been widely reported that they behave better than their proved worst-case theoretical bounds, no precise assessment has ever been given. Such an assessment would be very helpful to predict the behaviour of lattice-based attacks, as well as to select keysizes for lattice-based cryptosystems. The goal of this paper is to provide such an assessment, based on extensive experiments performed with the NTL library. The experiments suggest several conjectures on the worst case and the actual behaviour of lattice reduction algorithms. We believe the assessment might also help to design new reduction algorithms overcoming the limitations of current algorithms.

Similar content being viewed by others

Keywords

References

  1. Ajtai, M.: Generating random lattices according to the invariant distribution (Draft of March 2006)

    Google Scholar 

  2. Ajtai, M.: Generating hard instances of lattice problems. In: Proc. of 28th STOC, pp. 99–108. ACM Press, New York (1996)

    Google Scholar 

  3. Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: Proc. of 29th STOC, pp. 284–293. ACM Press, New York (1997)

    Google Scholar 

  4. Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proc. 33rd STOC, pp. 601–610. ACM Press, New York (2001)

    Google Scholar 

  5. Boneh, D., Durfee, G.: Cryptanalysis of RSA with private keyd less thanN0.292. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 1–11. Springer, Heidelberg (1999)

    Google Scholar 

  6. Cohn, H., Elkies, N.: New upper bounds on sphere packings. I. Ann. of Math (2) 157(2), 689–714 (2003)

    Article MathSciNet MATH  Google Scholar 

  7. Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. of Cryptology 10(4), 233–260 (1997); Revised version of two articles from Eurocrypt 1996

    Article MathSciNet MATH  Google Scholar 

  8. Gama, N., Howgrave-Graham, N., Koy, H., Nguyen, P.Q.: Rankin’s constant and blockwise lattice reduction. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 112–130. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  9. Gama, N., Howgrave-Graham, N., Nguyen, P.Q.: Symplectic Lattice Reduction and NTRU. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 233–253. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  10. Gama, N., Nguyen, P.Q.: Finding short lattice vectors within Mordell’s inequality. In: STOC 2008: Proc. of the 40th Annual ACM Symposium on Theory of Computing, ACM Press, New York (2008)

    Google Scholar 

  11. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. Cryptology ePrint Archive, Report 2007/432 (2007) (to appear in STOC 2008),http://eprint.iacr.org/

  12. 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)

    Google Scholar 

  13. Goldstein, D., Mayer, A.: On the equidistribution of Hecke points. Forum Math 15(2), 165–189 (2003)

    Article MathSciNet MATH  Google Scholar 

  14. Han, D., Kim, M.-H., Yeom, Y.: Cryptanalysis of the Paeng-Jung-Ha cryptosystem from PKC 2003. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 107–117. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  15. Hoffstein, J., Pipher, J., Silverman, J.: NTRU: a ring based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  16. Howgrave-Graham, N.A., Smart, N.P.: Lattice attacks on digital signature schemes. Des. Codes Cryptogr. 23(3), 283–290 (2001)

    Article MathSciNet MATH  Google Scholar 

  17. Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: Proc. of 15th STOC, pp. 193–206. ACM Press, New York (1983)

    Google Scholar 

  18. Klein, P.: Finding the closest lattice vector when it’s unusually close. In: Proc. of SODA 2000, ACM–SIAM (2000)

    Google Scholar 

  19. Lagarias, J.C., Odlyzko, A.M.: Solving low-density subset sum problems. In: Journal of the Association for Computing Machinery (January 1985)

    Google Scholar 

  20. Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Ann. 261, 513–534 (1982)

    Google Scholar 

  21. Lovász, L.: An Algorithmic Theory of Numbers, Graphs and Convexity. CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 50. SIAM Publications, Philadelphia (1986)

    Google Scholar 

  22. May, A., Silverman, J.H.: Dimension reduction methods for convolution modular lattices. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  23. Micciancio, D., Goldwasser, S.: Complexity of lattice problems: A cryptographic perspective. In: The Kluwer International Series in Engineering and Computer Science, vol. 671, Kluwer Academic Publishers, Boston (2002)

    Google Scholar 

  24. Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007) (electronic)

    Article MathSciNet MATH  Google Scholar 

  25. Nguyen, P.Q.: Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto 1997. In: Wiener, M.J. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 288–304. Springer, Heidelberg (1999)

    Google Scholar 

  26. Nguyen, P.Q., Shparlinski, I.E.: The insecurity of the digital signature algorithm with partially known nonces. J. Cryptology 15(3), 151–176 (2002)

    Article MathSciNet MATH  Google Scholar 

  27. Nguyen, P.Q., Stehlé, D.: Floating-Point LLL Revisited. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 215–233. Springer, Heidelberg (2005)

    Google Scholar 

  28. Nguyen, P.Q., Stehlé, D.: LLL on the average. In: ANTS, pp. 238–256 (2006)

    Google Scholar 

  29. Nguyen, P.Q., Stern, J.: The two faces of lattices in cryptology. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  30. Nguyen, P.Q., Stern, J.: Adapting density attacks to low-weight knapsacks. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 41–58. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  31. Nguyen, P.Q., Vidick, T.: Sieve algorithms for the shortest vector problem are practical. J. of Mathematical Cryptology (to appear, 2008)

    Google Scholar 

  32. Odlyzko, A.M.: The rise and fall of knapsack cryptosystems. In: Proc. of Cryptology and Computational Number Theory, Proc. of Symposia in Applied Mathematics, vol. 42, pp. 75–88. American Mathematical Society (1989)

    Google Scholar 

  33. Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. Cryptology ePrint Archive, Report 2007/279 (2007) to appear in STOC 2008http://eprint.iacr.org/

  34. Regev, O.: New lattice-based cryptographic constructions. J. ACM 51(6), 899–942 (2004)

    Article MathSciNet MATH  Google Scholar 

  35. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC 2005: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 84–93. ACM Press, New York (2005)

    Chapter  Google Scholar 

  36. Schnorr, C.-P.: A hierarchy of polynomial lattice basis reduction algorithms. Theoretical Computer Science 53, 201–224 (1987)

    Article MathSciNet MATH  Google Scholar 

  37. Schnorr, C.-P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Programming 66, 181–199 (1994)

    Article MathSciNet  Google Scholar 

  38. 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)

    Google Scholar 

  39. Shoup, V.: Number Theory C++ Library (NTL) version 5.4.1,http://www.shoup.net/ntl/

Download references

Author information

Authors and Affiliations

  1. École normale supérieure/CNRS/INRIA, 45 rue d’Ulm, 75005, Paris, France

    Nicolas Gama & Phong Q. Nguyen

Authors
  1. Nicolas Gama
  2. Phong Q. Nguyen

Editor information

Nigel Smart

Rights and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Gama, N., Nguyen, P.Q. (2008). Predicting Lattice Reduction. In: Smart, N. (eds) Advances in Cryptology – EUROCRYPT 2008. EUROCRYPT 2008. Lecture Notes in Computer Science, vol 4965. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78967-3_3

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp