Paper 2016/753

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

Shi Bai, Damien Stehle, and Weiqiang Wen

Abstract

We present a probabilistic polynomial-time reduction from the lattice Bounded Distance Decoding (BDD) problem with parameter 1/($\sqrt{2}\cdot\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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. ICALP 2016
Keywords
LatticesBounded Distance Decoding ProblemUnique Shortest Vector ProblemSparsification
Contact author(s)
weiqiang wen @ ens-lyon fr
History
2016-08-31: last of 2 revisions
2016-08-09: received
See all versions
Short URL
https://ia.cr/2016/753
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/753,
      author = {Shi Bai and Damien Stehle and Weiqiang Wen},
      title = {Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2016/753},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/753}},
      url = {https://eprint.iacr.org/2016/753}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.