Dimension-Preserving Reductions Between SVP and CVP in Different $p$-Norms

Abstract

We show a number of reductions between the Shortest Vector Problem and the Closest Vector Problem over lattices in different ${\ell }_p$ norms ($\SVP_p$ and $\CVP_p$ respectively). Specifically, we present the following $2^{\eps m}$-time reductions for $1\le p\le q\le \infty$, which all increase the rank $n$ and dimension $m$ of the input lattice by at most one: $\bullet$ a reduction from $\widetilde{O}(1/\eps^{1/p})γ$-approximate $\SVP_q$ to $\gamma$-approximate $\SVP_p$; $\bullet$ a reduction from $\widetilde{O}(1/\eps^{1/p}) γ$-approximate $\CVP_p$ to $\gamma$-approximate $\CVP_q$; and $\bullet$ a reduction from $\widetilde{O}(1/\eps^{1+1/p})$-$\CVP_q$ to $(1+\eps)$-unique $\SVP_p$ (which in turn trivially reduces to $(1+\eps)$-approximate $\SVP_p$). The last reduction is interesting even in the case $p=q$. In particular, this special case subsumes much prior work adapting $2^{O(m)}$-time $\SVP_p$ algorithms to solve $O(1)$-approximate $\CVP_p$. In the (important) special case when $p=q$, $1\le p\le 2$, and the $\SVP_p$ oracle is exact, we show a stronger reduction, from $O(1/\eps^{1/p})\text{-}\CVP_p$ to (exact) $\SVP_p$ in $2^{\eps m}$ time. For example, taking $\eps = \log m/m$ and $p=2$ gives a slight improvement over Kannan's celebrated polynomial-time reduction from $\sqrt{m}\text{-}\CVP_2$ to $\SVP_2$. We also note that the last two reductions can be combined to give a reduction from approximate-$\CVP_p$ to $\SVP_q$ for any $p$ and $q$, regardless of whether $p\le q$ or $p>q$. Our techniques combine those from the recent breakthrough work of Eisenbrand and Venzin (which showed how to adapt the current fastest known algorithm for these problems in the ${\ell }_2$ norm to all ${\ell }_p$ norms) together with sparsification-based techniques.