Document Open Access Logo

Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices

Authors Shi Bai, Damien Stehlé, Weiqiang Wen

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2016.76.pdf
  • Filesize: 0.74 MB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • Lattices
  • Bounded Distance Decoding Problem
  • Unique Shortest Vector Problem
  • Sparsification

Metrics

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

Abstract

We present a probabilistic polynomial-time reduction from the lattice Bounded Distance Decoding (BDD) problem with parameter 1/( sqrt(2) * gamma) to the unique Shortest Vector Problem (uSVP) with parameter gamma for any gamma > 1 that is polynomial in the lattice dimension n. It improves the BDD to uSVP reductions of [Lyubashevsky and Micciancio, CRYPTO, 2009] and [Liu, Wang, Xu and Zheng, Inf. Process. Lett., 2014], which rely on Kannan's embedding technique. The main ingredient to the improvement is the use of Khot's lattice sparsification [Khot, FOCS, 2003] before resorting to Kannan's embedding, in order to boost the uSVP parameter.

Cite As Get BibTex

Shi Bai, Damien Stehlé, and Weiqiang Wen. Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 76:1-76:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.76

Author Details

Shi Bai
Damien Stehlé
Weiqiang Wen

References

  1. M. Ajtai. The shortest vector problem in l₂ is NP-hard for randomized reductions (extended abstract). In Proc. of STOC, pages 284-293. ACM, 1998. Google Scholar
  2. L. Babai. On Lovász lattice reduction and the nearest lattice point problem. Combinatorica, 6:1-13, 1986. Google Scholar
  3. S. Bai and S. Galbraith. Private communication, 2015. Google Scholar
  4. D. Dadush and G. Kun. Lattice sparsification and the approximate closest vector problem. In Proc. of SODA, pages 1088-1102. SIAM, 2013. Google Scholar
  5. D. Dadush, O. Regev, and N. Stephens-Davidowitz. On the closest vector problem with a distance guarantee. In Proc. of CCC, pages 98-109. IEEE Computer Society Press, 2014. Google Scholar
  6. R. de Buda. The upper error bound of a new near-optimal code. IEEE Trans. on Information Theory, 21(4):441-445, 1975. Google Scholar
  7. U. Fincke and M. Pohst. A procedure for determining algebraic integers of given norm. In Proc. of EUROCAL, volume 162 of LNCS, pages 194-202, 1983. Google Scholar
  8. R. Kannan. Improved algorithms for integer programming and related lattice problems. In Proc. of STOC, pages 99-108. ACM, 1983. Google Scholar
  9. R. Kannan. Minkowski’s convex body theorem and integer programming. Math. Oper. Res., 12(3):415-440, 1987. Google Scholar
  10. S. Khot. Hardness of approximating the shortest vector problem in high L_p norms. In Proc. of FOCS, pages 290-297. IEEE Computer Society Press, 2003. Google Scholar
  11. S. Khot. Hardness of approximating the shortest vector problem in lattices. J. ACM, 52(5):789-808, 2005. Google Scholar
  12. A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász. Factoring polynomials with rational coefficients. Math. Ann, 261:515-534, 1982. Google Scholar
  13. M. Liu, X. Wang, G. Xu, and X. Zheng. A note on BDD problems with λ₂-gap. Inf. Process. Lett., 114(1-2):9-12, January 2014. Google Scholar
  14. Y. K. Liu, V. Lyubashevsky, and D. Micciancio. On bounded distance decoding for general lattices. In Proc. of RANDOM, volume 4110 of LNCS, pages 450-461. Springer, 2006. Google Scholar
  15. V. Lyubashevsky and D. Micciancio. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In Proc. of CRYPTO, pages 577-594, 2009. Google Scholar
  16. D. Micciancio. The shortest vector problem is NP-hard to approximate to within some constant. SIAM J. Comput, 30(6):2008-2035, 2001. Google Scholar
  17. D. Micciancio. Private communication, 2015. Google Scholar
  18. D. Micciancio and S. Goldwasser. Complexity of Lattice problem: A Cryptography Perspective. Kluwer, 2009. Google Scholar
  19. O. Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6), 2009. Google Scholar
  20. C. P. Schnorr. A hierarchy of polynomial lattice basis reduction algorithms. Theor. Comput. Science, 53:201-224, 1987. Google Scholar
  21. N. Stephens-Davidowitz. Discrete Gaussian sampling reduces to CVP and SVP. In Proc. of SODA, pages 1748-1764. SIAM, 2016. Google Scholar
  22. A. Vardy. Algorithmic complexity in coding theory and the minimum distance problem. In Proc. of STOC, pages 92-109. ACM, 1997. 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