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 rely heavily on Lyubashevsky and Micciancio's dimension-preserving reduction from @math -unique SVP to @math -GapSVP @cite_37 . Their result is necessary to prove Theorem , and our deterministic bit-by-bit SVP reduction is very similar to Lyubashevsky and Micciancio's reduction. The main difference between our deterministic SVP reduction and that of Lyubashevsky and Micciancio is that @cite_37 work only with lattices that satisfy the promise of @math -unique SVP. They show that this promise is enough to guarantee that the @math -GapSVP oracle essentially behaves as an GapSVP oracle. In contrast, our reduction works over general lattices, so we have to worry about accumulating error. (We also use a different method to reduce the dimension of the lattice. )
@cite_37
1490468194
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.