Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One

Abstract

We show the first dimension-preserving search-to-decision reductions for approximate SVP and CVP. In particular, for any $\gamma \le 1+O(\log n/n)$, we obtain an efficient dimension-preserving reduction from ${\gamma }^{O(n/\log n)}$-SVP to $\gamma$-GapSVP and an efficient dimension-preserving reduction from ${\gamma }^{O(n)}$-CVP to $\gamma$-GapCVP. These results generalize the known equivalences of the search and decision versions of these problems in the exact case when $\gamma =1$. For SVP, we actually obtain something slightly stronger than a search-to-decision reduction---we reduce ${\gamma }^{O(n/\log n)}$-SVP to $\gamma$-unique SVP, a potentially easier problem than $\gamma$-GapSVP.

Updated to acknowledge additional prior work

References in corpus (2)

• On the Closest Vector Problem with a Distance Guarantee
• Solving the Closest Vector Problem in $2^n$ Time--- The Discrete Gaussian Strikes Again!