Paper 2008/504
The $n^c$Unique Shortest Vector Problem is Hard
Vadim Lyubashevsky
Abstract
The unique Shortest Vector Problem (uSVP) gained prominence because it was the problem upon which the first provablysecure latticebased cryptosystems were built. But it was an open problem as to whether uSVP was as hard as the standard, more general, version of the shortest vector problem. We show that there is a reduction from the approximate decision version of the shortest vector problem (GapSVP) to the unique shortest vector problem. In particular, we show that for any $\gamma>6\sqrt{n}$, there is a reduction from GapSVP$_\gamma$ to $\frac{\gamma}{6\sqrt{n}}$uSVP. This implies that the AjtaiDwork and the Regev cryptosystems are based on the hardness of the worstcase GapSVP$_{O(n^{2.5})}$ and GapSVP$_{O(n^{2})}$, respectively. Our reduction is quite elementary, but it does use a clever, yet surprisingly simple (in retrospect!), idea of Peikert that was recently used by him to construct a cryptosystem based on the worstcase hardness of GapSVP$_{O(n^3)}$.
Note: ..
Metadata
 Available format(s)
 PDF PS
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 lattice cryptographyshortest vector problem
 Contact author(s)
 vlyubash @ cs ucsd edu
 History
 20081202: received
 Short URL
 https://ia.cr/2008/504
 License

CC BY
BibTeX
@misc{cryptoeprint:2008/504, author = {Vadim Lyubashevsky}, title = {The $n^c$Unique Shortest Vector Problem is Hard}, howpublished = {Cryptology ePrint Archive, Paper 2008/504}, year = {2008}, note = {\url{https://eprint.iacr.org/2008/504}}, url = {https://eprint.iacr.org/2008/504} }