Document Open Access Logo

Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

Authors Divesh Aggarwal, Yanlin Chen, Rajendra Kumar , Yixin Shen

PDF
Thumbnail PDF

File

LIPIcs.STACS.2021.4.pdf
  • Filesize: 0.94 MB
  • 20 pages

Document Identifiers

Author Details

Divesh Aggarwal
  • Centre for Quantum Technologies, Singapore
  • National University of Singapore, Singapore
Yanlin Chen
  • Institute of Information Science, Academia Sinica, Taipei, Taiwan
Rajendra Kumar
  • IIT Kanpur, India
  • National University of Singapore, Singapore
Yixin Shen
  • Université de Paris, IRIF, CNRS, F-75006, France

Funding

  • Aggarwal, Divesh: This work was partially supported by the Singapore Ministry of Education under grant MOE2019-T2-1-145, National Research Foundation under grant R-710-000-012-135.
  • Kumar, Rajendra: Supported in part by National Research Foundation Singapore under its AI Singapore Programme [Award Number: AISG-RP-2018-005].

Acknowledgements

We would like to thank Pierre-Alain Fouque, Paul Kirchner, Amaury Pouly and Noah Stephens-Davidowitz for useful comments and suggestions.

Cite As Get BibTex

Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, and Yixin Shen. Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.STACS.2021.4

Abstract

The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results.  
1) A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer 4 ≤ q ≤ √n, our algorithm takes q^{13n+o(n)} time and requires poly(n)⋅ q^{16n/q²} memory. This tradeoff which ranges from enumeration (q = √n) to sieving (q constant), is a consequence of a new time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter. 
2) A quantum algorithm that runs in time 2^{0.9533n+o(n)} and requires 2^{0.5n+o(n)} classical memory and poly(n) qubits. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [Divesh Aggarwal et al., 2015] that has a time and space complexity 2^{n+o(n)}. 
3) A classical algorithm for SVP that runs in time 2^{1.741n+o(n)} time and 2^{0.5n+o(n)} space. This improves over an algorithm of [Yanlin Chen et al., 2018] that has the same space complexity. 
The time complexity of our classical and quantum algorithms are expressed using a quantity related to the kissing number of a lattice. A known upper bound of this quantity is 2^{0.402n}, but in practice for most lattices, it can be much smaller and even 2^o(n). In that case, our classical algorithm runs in time 2^{1.292n} and our quantum algorithm runs in time 2^{0.750n}.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Lattices
  • Shortest Vector Problem
  • Discrete Gaussian Sampling
  • Time-Space Tradeoff
  • Quantum computation
  • Bounded distance decoding

Metrics

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

Related Versions

References

  1. Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, and Yixin Shen. Improved (provable) algorithms for the shortest vector problem via bounded distance decoding (full version), 2020. URL: http://arxiv.org/abs/2002.07955.
  2. Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. Solving the shortest vector problem in 2ⁿ time using discrete gaussian sampling: Extended abstract. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 733-742, 2015. URL: https://doi.org/10.1145/2746539.2746606.
  3. Divesh Aggarwal, Jianwei Li, Phong Q. Nguyen, and Noah Stephens-Davidowitz. Slide reduction, revisited - filling the gaps in SVP approximation. CoRR, abs/1908.03724, 2019. URL: http://arxiv.org/abs/1908.03724.
  4. Divesh Aggarwal and Noah Stephens-Davidowitz. (gap/s) eth hardness of svp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 228-238, 2018. Google Scholar
  5. 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, January 7-10, 2018, New Orleans, LA, USA, pages 12:1-12:19, 2018. URL: https://doi.org/10.4230/OASIcs.SOSA.2018.12.
  6. Miklós Ajtai. Generating hard instances of lattice problems (extended abstract). In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 99-108, 1996. URL: https://doi.org/10.1145/237814.237838.
  7. Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, STOC '01, pages 601-610, New York, NY, USA, 2001. ACM. URL: https://doi.org/10.1145/380752.380857.
  8. Martin R Albrecht, Léo Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W Postlethwaite, and Marc Stevens. The general sieve kernel and new records in lattice reduction. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 717-746. Springer, 2019. Google Scholar
  9. Yoshinori Aono, Phong Q. Nguyen, and Yixin Shen. Quantum lattice enumeration and tweaking discrete pruning. In Thomas Peyrin and Steven Galbraith, editors, Advances in Cryptology - ASIACRYPT 2018, pages 405-434, Cham, 2018. Springer International Publishing. Google Scholar
  10. Shi Bai, Thijs Laarhoven, and Damien Stehlé. Tuple lattice sieving. IACR Cryptology ePrint Archive, 2016:713, 2016. URL: http://eprint.iacr.org/2016/713.
  11. Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 10-24, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch2.
  12. Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. Classical hardness of learning with errors. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 575-584. ACM, 2013. Google Scholar
  13. Zvika Brakerski and Vinod Vaikuntanathan. Lattice-based FHE as secure as PKE. In Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pages 1-12, 2014. URL: https://doi.org/10.1145/2554797.2554799.
  14. Ernest F. Brickell. Breaking iterated knapsacks. In Advances in Cryptology, Proceedings of CRYPTO '84, Santa Barbara, California, USA, August 19-22, 1984, Proceedings, pages 342-358, 1984. URL: https://doi.org/10.1007/3-540-39568-7_27.
  15. Yanlin Chen, Kai-Min Chung, and Ching-Yi Lai. Space-efficient classical and quantum algorithms for the shortest vector problem. Quantum Information & Computation, 18(3&4):285-306, 2018. URL: http://www.rintonpress.com/xxqic18/qic-18-34/0285-0306.pdf.
  16. Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. On the closest vector problem with a distance guarantee. In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, pages 98-109, 2014. URL: https://doi.org/10.1109/CCC.2014.18.
  17. Rudi de Buda. Some optimal codes have structure. IEEE Journal on Selected Areas in Communications, 7(6):893-899, 1989. URL: https://doi.org/10.1109/49.29612.
  18. Léo Ducas. Shortest vector from lattice sieving: A few dimensions for free. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part I, volume 10820 of Lecture Notes in Computer Science, pages 125-145. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-78381-9_5.
  19. Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum. CoRR, quant-ph/9607014, 1996. URL: http://arxiv.org/abs/quant-ph/9607014.
  20. András Frank and Éva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1):49-65, 1987. URL: https://doi.org/10.1007/BF02579200.
  21. Nicolas Gama and Phong Q. Nguyen. Finding short lattice vectors within mordell’s inequality. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 207-216, 2008. URL: https://doi.org/10.1145/1374376.1374408.
  22. Nicolas Gama, Phong Q. Nguyen, and Oded Regev. Lattice enumeration using extreme pruning. In Henri Gilbert, editor, Advances in Cryptology - EUROCRYPT 2010, pages 257-278, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  23. Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 169-178, 2009. URL: https://doi.org/10.1145/1536414.1536440.
  24. Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 197-206. ACM, 2008. Google Scholar
  25. Guillaume Hanrot, Xavier Pujol, and Damien Stehlé. Analyzing blockwise lattice algorithms using dynamical systems. In Phillip Rogaway, editor, Advances in Cryptology - CRYPTO 2011, pages 447-464, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. Google Scholar
  26. Guillaume Hanrot and Damien Stehlé. Improved analysis of kannan’s shortest lattice vector algorithm. In Advances in Cryptology - CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007, Proceedings, pages 170-186, 2007. URL: https://doi.org/10.1007/978-3-540-74143-5_10.
  27. Ishay Haviv and Oded Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 469-477, 2007. Google Scholar
  28. Bettina Helfrich. Algorithms to construct minkowski reduced and hermite reduced lattice bases. Theor. Comput. Sci., 41(2–3):125–139, December 1985. Google Scholar
  29. Gottfried Herold and Elena Kirshanova. Improved algorithms for the approximate k-list problem in euclidean norm. In Serge Fehr, editor, Public-Key Cryptography - PKC 2017, pages 16-40, Berlin, Heidelberg, 2017. Springer Berlin Heidelberg. Google Scholar
  30. Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963. Google Scholar
  31. Russell Impagliazzo, Leonid A Levin, and Michael Luby. Pseudo-random generation from one-way functions. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 12-24, 1989. Google Scholar
  32. Hendrik W. Lenstra Jr. Integer programming with a fixed number of variables. Math. Oper. Res., 8(4):538-548, 1983. URL: https://doi.org/10.1287/moor.8.4.538.
  33. Grigorii Anatol'evich Kabatiansky and Vladimir Iosifovich Levenshtein. On bounds for packings on a sphere and in space. Problemy Peredachi Informatsii, 14(1):3-25, 1978. Google Scholar
  34. Ravi Kannan. Minkowski’s convex body theorem and integer programming. Math. Oper. Res., 12(3):415-440, 1987. URL: https://doi.org/10.1287/moor.12.3.415.
  35. Subhash Khot. Hardness of approximating the shortest vector problem in lattices. J. ACM, 52(5):789-808, 2005. URL: https://doi.org/10.1145/1089023.1089027.
  36. Paul Kirchner and Pierre-Alain Fouque. Time-memory trade-off for lattice enumeration in a ball. Cryptology ePrint Archive, Report 2016/222, 2016. URL: https://eprint.iacr.org/2016/222.
  37. Elena Kirshanova, Erik Mårtensson, Eamonn W Postlethwaite, and Subhayan Roy Moulik. Quantum algorithms for the approximate k-list problem and their application to lattice sieving. In International Conference on the Theory and Application of Cryptology and Information Security, pages 521-551. Springer, 2019. Google Scholar
  38. Philip Klein. Finding the closest lattice vector when it’s unusually close. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’00, page 937–941, USA, 2000. Society for Industrial and Applied Mathematics. Google Scholar
  39. Thijs Laarhoven, Michele Mosca, and Joop Van De Pol. Finding shortest lattice vectors faster using quantum search. Designs, Codes and Cryptography, 77, December 2015. URL: https://doi.org/10.1007/s10623-015-0067-5.
  40. J. C. Lagarias and Andrew M. Odlyzko. Solving low-density subset sum problems. J. ACM, 32(1):229-246, 1985. URL: https://doi.org/10.1145/2455.2461.
  41. A.K. Lenstra, H.W. Lenstra, and Lászlo Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261:515-534, 1982. Google Scholar
  42. Daniele Micciancio. The shortest vector in a lattice is hard to approximate to within some constant. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS ’98, page 92, USA, 1998. IEEE Computer Society. Google Scholar
  43. Daniele Micciancio and Chris Peikert. Hardness of SIS and LWE with small parameters. In Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, pages 21-39, 2013. URL: https://doi.org/10.1007/978-3-642-40041-4_2.
  44. Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on gaussian measures. In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 372-381, 2004. URL: https://doi.org/10.1109/FOCS.2004.72.
  45. Daniele Micciancio and Oded Regev. Lattice-based cryptography, 2008. Google Scholar
  46. Daniele Micciancio and Panagiotis Voulgaris. Faster exponential time algorithms for the shortest vector problem. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1468-1480, 2010. URL: https://doi.org/10.1137/1.9781611973075.119.
  47. Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. SIAM J. Comput., 42(3):1364-1391, 2013. URL: https://doi.org/10.1137/100811970.
  48. Daniele Micciancio and Michael Walter. Fast lattice point enumeration with minimal overhead. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 276-294, 2015. URL: https://doi.org/10.1137/1.9781611973730.21.
  49. Phong Q. Nguyen and Thomas Vidick. Sieve algorithms for the shortest vector problem are practical. J. Mathematical Cryptology, 2(2):181-207, 2008. URL: https://doi.org/10.1515/JMC.2008.009.
  50. Xavier Pujol and Damien Stehlé. Solving the shortest lattice vector problem in time 2^2.465n. IACR Cryptology ePrint Archive, 2009:605, 2009. URL: http://eprint.iacr.org/2009/605.
  51. Oded Regev. Lattices in computer science, lecture 8, Fall 2004. Google Scholar
  52. Oded Regev. Lattice-based cryptography. In Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2006, Proceedings, pages 131-141, 2006. URL: https://doi.org/10.1007/11818175_8.
  53. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):34:1-34:40, September 2009. URL: https://doi.org/10.1145/1568318.1568324.
  54. Claus Peter Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci., 53:201-224, 1987. Google Scholar
  55. Claus-Peter Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Math. Program., 66:181-199, 1994. URL: https://doi.org/10.1007/BF01581144.
  56. Adi Shamir. A polynomial-time algorithm for breaking the basic merkle-hellman cryptosystem. IEEE Trans. Information Theory, 30(5):699-704, 1984. URL: https://doi.org/10.1109/TIT.1984.1056964.
  57. SVP Challenges. URL: https://www.latticechallenge.org/svp-challenge/.
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