Document Open Access Logo

Hardness of Bounded Distance Decoding on Lattices in 𝓁_p Norms

Authors Huck Bennett, Chris Peikert

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2020.36.pdf
  • Filesize: 0.61 MB
  • 21 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Lattices
  • Bounded Distance Decoding
  • NP-hardness
  • Fine-Grained Complexity

Metrics

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

Abstract

Bounded Distance Decoding BDD_{p,α} is the problem of decoding a lattice when the target point is promised to be within an α factor of the minimum distance of the lattice, in the 𝓁_p norm. We prove that BDD_{p, α} is NP-hard under randomized reductions where α → 1/2 as p → ∞ (and for α = 1/2 when p = ∞), thereby showing the hardness of decoding for distances approaching the unique-decoding radius for large p. We also show fine-grained hardness for BDD_{p,α}. For example, we prove that for all p ∈ [1,∞) ⧵ 2ℤ and constants C > 1, ε > 0, there is no 2^((1-ε)n/C)-time algorithm for BDD_{p,α} for some constant α (which approaches 1/2 as p → ∞), assuming the randomized Strong Exponential Time Hypothesis (SETH). Moreover, essentially all of our results also hold (under analogous non-uniform assumptions) for BDD with preprocessing, in which unbounded precomputation can be applied to the lattice before the target is available.
Compared to prior work on the hardness of BDD_{p,α} by Liu, Lyubashevsky, and Micciancio (APPROX-RANDOM 2008), our results improve the values of α for which the problem is known to be NP-hard for all p > p₁ ≈ 4.2773, and give the very first fine-grained hardness for BDD (in any norm). Our reductions rely on a special family of "locally dense" lattices in 𝓁_p norms, which we construct by modifying the integer-lattice sparsification technique of Aggarwal and Stephens-Davidowitz (STOC 2018).

Cite As Get BibTex

Huck Bennett and Chris Peikert. Hardness of Bounded Distance Decoding on Lattices in 𝓁_p Norms. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CCC.2020.36

Author Details

Huck Bennett
  • University of Michigan, Ann Arbor, MI, USA
Chris Peikert
  • University of Michigan, Ann Arbor, MI, USA

Acknowledgements

We thank the Simons Institute for hosting the Spring 2020 program "Lattices: Algorithms, Complexity, and Cryptography," at which some of this work was completed. We also thank Noah Stephens-Davidowitz for sharing his plot-generating code from Aggarwal and Stephens-Davidowitz (STOC 2018) with us.

References

  1. Leonard M. Adleman. Two theorems on random polynomial time. In FOCS, pages 75-83, 1978. Google Scholar
  2. Divesh Aggarwal, Huck Bennett, Alexander Golovnev, and Noah Stephens-Davidowitz. Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else), 2019. URL: http://arxiv.org/abs/1911.02440.
  3. 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 STOC, pages 733-742, 2015. Google Scholar
  4. Divesh Aggarwal, Daniel Dadush, and Noah Stephens-Davidowitz. Solving the closest vector problem in 2ⁿ time - the discrete Gaussian strikes again! In FOCS, pages 563-582, 2015. Google Scholar
  5. Divesh Aggarwal and Noah Stephens-Davidowitz. (Gap/S)ETH hardness of SVP. In STOC, pages 228-238, 2018. Google Scholar
  6. Divesh Aggarwal and Noah Stephens-Davidowitz. Just take the average! An embarrassingly simple 2ⁿ-time algorithm for SVP (and CVP). In Symposium on Simplicity in Algorithms, volume 61, pages 12:1-12:19, 2018. Google Scholar
  7. Miklós Ajtai. The shortest vector problem in L₂ is NP-hard for randomized reductions (extended abstract). In STOC, pages 10-19, 1998. Google Scholar
  8. Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci., 54(2):317-331, 1997. URL: https://doi.org/10.1006/jcss.1997.1472.
  9. Shi Bai, Damien Stehlé, and Weiqiang Wen. Improved reduction from the bounded distance decoding problem to the unique shortest vector problem in lattices. In ICALP, pages 76:1-76:12, 2016. Google Scholar
  10. Huck Bennett, Alexander Golovnev, and Noah Stephens-Davidowitz. On the quantitative hardness of CVP. In FOCS, 2017. Google Scholar
  11. Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. On the closest vector problem with a distance guarantee. In IEEE Conference on Computational Complexity, pages 98-109, 2014. Google Scholar
  12. N. D. Elkies, A. M. Odlyzko, and J. A. Rush. On the packing densities of superballs and other bodies. Inventiones mathematicae, 105:613–639, December 1991. Google Scholar
  13. Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, pages 197-206, 2008. Google Scholar
  14. Ishay Haviv and Oded Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Theory of Computing, 8(1):513-531, 2012. Preliminary version in STOC 2007. Google Scholar
  15. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. Google Scholar
  16. Subhash Khot. Hardness of approximating the shortest vector problem in lattices. J. ACM, 52(5):789-808, 2005. Preliminary version in FOCS 2004. Google Scholar
  17. Subhash Khot. Hardness of approximating the shortest vector problem in high 𝓁_p norms. J. Comput. Syst. Sci., 72(2):206-219, 2006. Google Scholar
  18. Ravi Kumar and D. Sivakumar. On the unique shortest lattice vector problem. Theor. Comput. Sci., 255(1-2):641-648, 2001. Google Scholar
  19. Yi-Kai Liu, Vadim Lyubashevsky, and Daniele Micciancio. On bounded distance decoding for general lattices. In APPROX-RANDOM, pages 450-461, 2006. Google Scholar
  20. Vadim Lyubashevsky and Daniele Micciancio. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In CRYPTO, pages 577-594, 2009. Google Scholar
  21. J. E. Mazo and A. M. Odlyzko. Lattice points in high-dimensional spheres. Monatshefte für Mathematik, 110:47-61, March 1990. Google Scholar
  22. Daniele Micciancio. The shortest vector in a lattice is hard to approximate to within some constant. SIAM J. Comput., 30(6):2008-2035, 2000. Preliminary version in FOCS 1998. Google Scholar
  23. Daniele Micciancio. The hardness of the closest vector problem with preprocessing. IEEE Trans. Information Theory, 47(3):1212-1215, 2001. URL: https://doi.org/10.1109/18.915688.
  24. Daniele Micciancio. Efficient reductions among lattice problems. In SODA, pages 84-93, 2008. Google Scholar
  25. Daniele Micciancio. Inapproximability of the shortest vector problem: Toward a deterministic reduction. Theory of Computing, 8(1):487-512, 2012. Google Scholar
  26. Chris Peikert. Public-key cryptosystems from the worst-case shortest vector problem. In STOC, pages 333-342, 2009. Google Scholar
  27. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):1-40, 2009. Preliminary version in STOC 2005. Google Scholar
  28. Oded Regev and Ricky Rosen. Lattice problems and norm embeddings. In STOC, pages 447-456, 2006. Google Scholar
  29. Noah Stephens-Davidowitz. Discrete Gaussian sampling reduces to CVP and SVP. In SODA, pages 1748-1764, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch121.
  30. Noah Stephens-Davidowitz and Vinod Vaikuntanathan. SETH-hardness of coding problems. In FOCS, pages 287-301, 2019. Google Scholar
  31. Peter van Emde Boas. Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, University of Amsterdam, 1981. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact