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 formats: 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