The $n^c$-Unique Shortest Vector Problem is Hard

Vadim Lyubashevsky

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 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 , there is a reduction from GapSVP to -uSVP. This implies that the Ajtai-Dwork and the Regev cryptosystems are based on the hardness of the worst-case GapSVP and GapSVP, 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.

Note: ..

Metadata

Available format(s): PDF PS
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: lattice cryptography shortest vector problem
Contact author(s): vlyubash @ cs ucsd edu
History: 2008-12-02: 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},
      url = {https://eprint.iacr.org/2008/504}
}

Paper 2008/504

The nc-Unique Shortest Vector Problem is Hard

Abstract

Metadata

The $n^{c}$ -Unique Shortest Vector Problem is Hard