We show the first dimension-preserving search-to-decision reductions for approximate SVP and CVP. In particular, for any @math , we obtain an efficient dimension-preserving reduction from @math -SVP to @math -GapSVP and an efficient dimension-preserving reduction from @math -CVP to @math -GapCVP. These results generalize the known equivalences of the search and decision versions of these problems in the exact case when @math . For SVP, we actually obtain something slightly stronger than a search-to-decision reduction---we reduce @math -SVP to @math -unique SVP, a potentially easier problem than @math -GapSVP.
We prove the equivalence, up to a small polynomial approximation factor @math , 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 @math and GapSVP @math , 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.