May 27, Wednesday
12:00 – 14:00
On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
Graduate seminar
Lecturer : Dr. Vadim Lyubashevsky
Affiliation : Tel-Aviv University
Location : 201/37
Host : Graduate seminar
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 and the Regev cryptosystems, which were previously only known to be based on the hardness of uSVP, can be equivalently based on the hardness of the more standard worst-case GapSVP. 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.
This is joint work with Daniele Micciancio and will appear at CRYPTO 2009