Document Open Access Logo

Just Take the Average! An Embarrassingly Simple 2^n-Time Algorithm for SVP (and CVP)

Authors Divesh Aggarwal, Noah Stephens-Davidowitz

PDF
Thumbnail PDF

File

OASIcs.SOSA.2018.12.pdf
  • Filesize: 0.6 MB
  • 19 pages

Document Identifiers

Author Details

Divesh Aggarwal
Noah Stephens-Davidowitz

Cite As Get BibTex

Divesh Aggarwal and Noah Stephens-Davidowitz. Just Take the Average! An Embarrassingly Simple 2^n-Time Algorithm for SVP (and CVP). In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/OASIcs.SOSA.2018.12

Abstract

We show a 2^{n+o(n)}-time (and space) algorithm for the Shortest Vector Problem on lattices (SVP) that works by repeatedly running an embarrassingly simple "pair and average" sieving-like procedure on a list of lattice vectors. This matches the running time (and space) of the current fastest known algorithm, due to Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS, in STOC, 2015), with a far simpler algorithm. Our algorithm is in fact a modification of the ADRS algorithm, with a certain careful rejection sampling step removed.
	
The correctness of our algorithm follows from a more general "meta-theorem," showing that such rejection sampling steps are unnecessary for a certain class of algorithms and use cases. In particular, this also applies to the related 2^{n + o(n)}-time algorithm for the Closest Vector Problem (CVP), due to Aggarwal, Dadush, and Stephens-Davidowitz (ADS, in FOCS, 2015), yielding a similar embarrassingly simple algorithm for gamma-approximate CVP for any gamma = 1+2^{-o(n/log n)}. (We can also remove the rejection sampling procedure from the 2^{n+o(n)}-time ADS algorithm for exact CVP, but the resulting algorithm is still quite complicated.)

Subject Classification

Keywords
  • Lattices
  • SVP
  • CVP

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. Solving the Shortest Vector Problem in 2ⁿ time via discrete Gaussian sampling. In STOC, 2015. Google Scholar
  2. Divesh Aggarwal, Daniel Dadush, and Noah Stephens-Davidowitz. Solving the Closest Vector Problem in 2ⁿ time - The discrete Gaussian strikes again! In FOCS, 2015. Google Scholar
  3. Miklós Ajtai. The shortest vector problem in L_2 is NP-hard for randomized reductions (extended abstract). In Jeffrey Scott Vitter, editor, Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 10-19. ACM, 1998. URL: http://dx.doi.org/10.1145/276698.276705.
  4. Miklós Ajtai. Generating hard instances of lattice problems. In Complexity of computations and proofs, volume 13 of Quad. Mat., pages 1-32. Dept. Math., Seconda Univ. Napoli, Caserta, 2004. Preliminary version in STOC'96. Google Scholar
  5. Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors, Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 601-610. ACM, 2001. URL: http://dx.doi.org/10.1145/380752.380857.
  6. Miklós Ajtai, Ravi Kumar, and D. Sivakumar. Sampling short lattice vectors and the closest lattice vector problem. In CCC, pages 41-45, 2002. Google Scholar
  7. Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum key exchange - A new hope. In USENIX Security Symposium, 2016. Google Scholar
  8. László Babai. On lovász' lattice reduction and the nearest lattice point problem. Combinatorica, 6(1):1-13, 1986. URL: http://dx.doi.org/10.1007/BF02579403.
  9. Wojciech Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 296(4):625-635, 1993. URL: http://dx.doi.org/10.1007/BF01445125.
  10. Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. In SODA, 2016. Google Scholar
  11. Joppe W. Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth Raghunathan, and Douglas Stebila. Frodo: Take off the ring! Practical, quantum-secure key exchange from LWE. In CCS, 2016. Google Scholar
  12. Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. Classical hardness of learning with errors. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 575-584. ACM, 2013. URL: http://dx.doi.org/10.1145/2488608.2488680.
  13. R. de Buda. Some optimal codes have structure. Selected Areas in Communications, IEEE Journal on, 7(6):893-899, Aug 1989. Google Scholar
  14. Irit Dinur, Guy Kindler, Ran Raz, and Shmuel Safra. Approximating CVP to within almost-polynomial factors is NP-hard. Combinatorica, 23(2):205-243, 2003. Google Scholar
  15. Nicolas Gama and Phong Q. Nguyen. Finding short lattice vectors within Mordell’s inequality. In STOC, 2008. Google Scholar
  16. Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, pages 197-206, 2008. Google Scholar
  17. Oded Goldreich, Daniele Micciancio, Shmuel Safra, and Jean-Pierre Seifert. Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Inf. Process. Lett., 71(2):55-61, 1999. URL: http://dx.doi.org/10.1016/S0020-0190(99)00083-6.
  18. Ishay Haviv and Oded Regev. Tensor-based hardness of the Shortest Vector Problem to within almost polynomial factors. Theory of Computing, 8(23):513-531, 2012. Preliminary version in STOC'07. Google Scholar
  19. Hendrik W. Lenstra Jr. Integer programming with a fixed number of variables. Math. Oper. Res., 8(4):538-548, 1983. URL: http://dx.doi.org/10.1287/moor.8.4.538.
  20. Ravi Kannan. Minkowski’s convex body theorem and integer programming. Math. Oper. Res., 12(3):415-440, 1987. URL: http://dx.doi.org/10.1287/moor.12.3.415.
  21. Subhash Khot. Hardness of approximating the Shortest Vector Problem in lattices. Journal of the ACM, 52(5):789-808, 2005. Preliminary version in FOCS'04. Google Scholar
  22. Philip Klein. Finding the closest lattice vector when it’s unusually close. In SODA, 2000. Google Scholar
  23. A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261(4):515-534, 1982. URL: http://dx.doi.org/10.1007/BF01457454.
  24. Daniele Micciancio. The Shortest Vector Problem is NP-hard to approximate to within some constant. SIAM Journal on Computing, 30(6):2008-2035, 2001. Preliminary version in FOCS 1998. Google Scholar
  25. Daniele Micciancio and Panagiotis Voulgaris. Faster exponential time algorithms for the Shortest Vector Problem. In SODA, 2010. Google Scholar
  26. Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. SIAM Journal on Computing, 42(3):1364-1391, 2013. Google Scholar
  27. Daniele Micciancio and Michael Walter. Practical, predictable lattice basis reduction. In Eurocrypt, 2016. Google Scholar
  28. NIST post-quantum standardization call for proposals. http://csrc.nist.gov/groups/ST/post-quantum-crypto/cfp-announce-dec2016.html, 2016. Accessed: 2017-04-02.
  29. Chris Peikert. A decade of lattice cryptography. Foundations and Trends in Theoretical Computer Science, 10(4):283-424, 2016. Google Scholar
  30. Xavier Pujol and Damien Stehlé. Solving the Shortest Lattice Vector Problem in time 2^2.465 n. IACR Cryptology ePrint Archive, 2009:605, 2009. Google Scholar
  31. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):34:1-34:40, 2009. URL: http://dx.doi.org/10.1145/1568318.1568324.
  32. Oded Regev and Noah Stephens-Davidowitz. An inequality for Gaussians on lattices. SIDMA, 2017. Google Scholar
  33. Claus-Peter Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci., 53:201-224, 1987. URL: http://dx.doi.org/10.1016/0304-3975(87)90064-8.
  34. Adi Shamir. A polynomial-time algorithm for breaking the basic merkle-hellman cryptosystem. IEEE Trans. Information Theory, 30(5):699-704, 1984. URL: http://dx.doi.org/10.1109/TIT.1984.1056964.
  35. Noah Stephens-Davidowitz. On the Gaussian Measure Over Lattices. PhD thesis, New York University, 2017. Google Scholar
  36. Peter van Emde Boas. Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical report, University of Amsterdam, Department of Mathematics, Netherlands, 1981. Technical Report 8104. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact