Advertisement
Published in:
2009 | OriginalPaper | Chapter
On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
Authors : Vadim Lyubashevsky, Daniele Micciancio
Published in: Advances in Cryptology - CRYPTO 2009
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We prove the equivalence, up to a small polynomial approximation factor
$\sqrt{n/\log n}$
, of the lattice problems
uSVP
(unique Shortest Vector Problem),
BDD
(Bounded Distance Decoding) and
GapSVP
(the decision version of the Shortest Vector Problem). This resolves a long-standing open problem about the relationship between
uSVP
and the more standard
GapSVP
, as well the
BDD
problem commonly used in coding theory. The main cryptographic application of our work is the proof that the Ajtai-Dwork ([2]) and the Regev ([33]) cryptosystems, which were previously only known to be based on the hardness of
uSVP
, can be equivalently based on the hardness of worst-case GapSVP
${_{O({n^{2.5}})}}$
and GapSVP
${_{O(n^{2})}}$
, respectively. Also, in the case of
uSVP
and
BDD
, our connection is very tight, establishing the equivalence (within a small constant approximation factor) between the two most central problems used in lattice based public key cryptography and coding theory.