SpringerLink
Log in

Lattice Point Enumeration on Block Reduced Bases

  • Conference paper
Information Theoretic Security (ICITS 2015)

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

Included in the following conference series:

Abstract

When analyzing lattice-based cryptosystems, we often need to solve the Shortest Vector Problem (SVP) in some lattice associated to the system under scrutiny. The go-to algorithms in practice to solve SVP are enumeration algorithms, which usually consist of a preprocessing step, followed by an exhaustive search. Obviously, the two steps offer a trade-off and should be balanced in their running time in order to minimize the overall complexity. In practice, the most common approach to control this trade-off is to use block reduction algorithms during the preprocessing. Despite the popularity of this approach, it lacks any well founded analysis and all practical approaches seem to use ad hoc parameters. This weakens our confidence in the cryptanalysis of the systems. In this work, we aim to shed light on at least one side of this trade-off and analyze the effect of block reduction on the exhaustive search. For this, we give asymptotic worst case bounds and present results from both experiments and simulation that show its average case behavior in practice.

Research supported in part by the DARPA PROCEED program and NSF grant CNS-1117936. Opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of DARPA or NSF.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. ACM. STOC (May 2008)

    Google Scholar 

  2. Ajtai, M.: Generating hard instances of lattice problems. Complexity of Computations and Proofs, Quaderni di Matematica, 13:1–13:32 (2004), Preliminary version in STOC 1996

    Google Scholar 

  3. Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: Proceedings of STOC 1997, pp. 284–293. ACM (May 1997)

    Google Scholar 

  4. Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of STOC, pp. 266–275. ACM (July 2001)

    Google Scholar 

  5. Albrecht, M., Cadé, D., Pujol, X., Stehlé, D.: fplll-4.0, A floating-point LLL implementation, http://perso.ens-lyon.fr/damien.stehle

  6. Blömer, J., Naewe, S.: Sampling methods for shortest vectors, closest vectors and successive minima (Preliminary version in ICALP 2007). In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 65–77. Springer, Heidelberg (2007), doi:10.1016/j.tcs.2008.12.045

    Chapter  Google Scholar 

  7. Chen, Y., Nguyen, P.Q.: BKZ 2.0: Better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1–20. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  8. Ding, D., Zhu, G., Wang, X.: A genetic algorithm for searching shortest lattice vector of svp challenge. Cryptology ePrint Archive, Report 2014/489 (2014), http://eprint.iacr.org/

  9. Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Mathematics of Computation 44, 463–471 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  10. Gama, N., Nguyen, P.Q.: Finding short lattice vectors within Mordell’s inequality. In: Proceedings of STOC 2008, pp. 207–216 (2008)

    Google Scholar 

  11. Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  12. Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  13. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of STOC, pp. 169–178. ACM (2009)

    Google Scholar 

  14. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of STOC 2008, pp. 197–206 (2008)

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  16. Hanrot, G., Pujol, X., Stehlé, D.: Terminating BKZ. Cryptology ePrint Archive, Report 2011/198 (2011), http://eprint.iacr.org/

  17. Hanrot, G., Stehlé, D.: Improved analysis of kannan’s shortest lattice vector algorithm. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 170–186. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  18. Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing - STOC 1983, pp. 193–206. ACM (April 1983), Journal version in Math. of Operation Research 12(3), 415-440 (1987)

    Google Scholar 

  19. Khot, S.: Hardness of approximating the shortest vector problem in lattices. Journal of the ACM 52(5), 789–808 (2004), Preliminary version in FOCS 2004

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  21. Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 319–339. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  22. Lyubashevsky, V., Micciancio, D.: Asymptotically efficient lattice-based digital signatures. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 37–54. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  23. Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFT: A modest proposal for FFT hashing. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 54–72. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  24. Micciancio, D.: Inapproximability of the shortest vector problem: Toward a deterministic reduction. Theory of Computing 8(1), 487–512 (2012)

    Article  MathSciNet  Google Scholar 

  25. Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. In: Proceedings of STOC, pp. 351–358 (2010)

    Google Scholar 

  26. Micciancio, D., Voulgaris, P.: Faster exponential time algorithms for the shortest vector problem. In: Proceedings of SODA, pp. 1468–1480. ACM/SIAM (January 2010)

    Google Scholar 

  27. Micciancio, D., Walter, M.: Fast lattice point enumeration with minimal overhead. In: Proceedings of SODA, pp. 276–294. ACM/SIAM (January 2015)

    Google Scholar 

  28. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. Journal of ACM 56(6), 34 (2009), Preliminary version in STOC 2005

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  30. Schnorr, C.-P.: Lattice reduction by random sampling and birthday methods. In: STACS, pp. 145–156 (2003)

    Google Scholar 

  31. Shoup, V.: Ntl: a library for doing number theory, http://www.shoup.net/ntl/index.html

Download references

Author information

Authors and Affiliations

  1. University of California, San Diego, USA

    Michael Walter

Authors
  1. Michael Walter
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michael Walter .

Editor information

Editors and Affiliations

  1. IBM Research Zurich, Rüschlikon, Switzerland

    Anja Lehmann

  2. Università della Svizzera italiana (USI), Lugano, Switzerland

    Stefan Wolf

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Walter, M. (2015). Lattice Point Enumeration on Block Reduced Bases. In: Lehmann, A., Wolf, S. (eds) Information Theoretic Security. ICITS 2015. Lecture Notes in Computer Science(), vol 9063. Springer, Cham. https://doi.org/10.1007/978-3-319-17470-9_16

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-17470-9_16

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-17469-3

  • Online ISBN: 978-3-319-17470-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation