## Cryptology ePrint Archive: Report 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 provably-secure
lattice-based 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 Ajtai-Dwork
and the Regev cryptosystems are based on the hardness of the
worst-case 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 worst-case hardness of GapSVP$_{O(n^3)}$.

**Category / Keywords: **public-key cryptography / lattice cryptography, shortest vector problem

**Date: **received 30 Nov 2008, last revised 1 Dec 2008

**Contact author: **vlyubash at cs ucsd edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Note: **..

**Version: **20081202:020649 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]