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

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\mathrm{/}n)$, we obtain an efficient dimension-preserving reduction from $\gamma^{O(n/\log n)}$-SVPto$\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\mathrm{/}\log n)}$-SVP to $\gamma$-unique SVP, a potentially easier problem than $\gamma$-GapSVP.