Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
verfasst von : Vadim Lyubashevsky, Daniele Micciancio
Erschienen in: Advances in Cryptology - CRYPTO 2009
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.