Dimension-Preserving Reductions Between SVP and CVP in Different p -Norms
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Zeyong Li, Noah Stephens-Davidowitz · Society for Industrial and Applied Mathematics eBooks · 2021
We show a number of reductions between the Shortest Vector Problem and the Closest Vector Problem over lattices in different ℓp norms (SVPp and CVPp respectively). Specifically, we present the following 2∊m-time reductions for 1 ≤ p ≤ q ≤ ∞, which all increase the rank n and dimension m of the input lattice by at most one: a reduction from Õ(1/∊1/p)γ-approximate SVPq to γ-approximate SVPp; a reduction from Õ(1/∊1/p)γ-approximate CVPp to γ-approximate CVPq; and a reduction from Õ(1/∊1+1/p)-CVPq to (1 + ∊)-unique SVPp (which in turn trivially reduces to (1 + ∊)-approximate SVPp). The last reduction is interesting even in the case p = q. In particular, this special case subsumes much prior work adapting 2O(m)-time SVPp algorithms to solve O(1)-approximate CVPp. In fact, we show a stronger result in the special case when 1 ≤ p = q ≤ 2 and the SVPp oracle is exact: a reduction from O(1/∊1/p)-CVPp to (exact) SVPp in 2∊m time. For example, taking ∊ = log m/m and p = 2 gives a slight improvement over Kannan's celebrated polynomial-time reduction from to SVP2. We also note that the last two reductions can be combined to give a reduction from approximate-CVPp to SVPq for any p and q, regardless of whether p ≤ q or p > q. Our techniques combine those from the recent breakthrough work of Eisenbrand and Venzin [21] (which showed how to adapt the current fastest known algorithm for these problems in the ℓ2 norm to all ℓp norms) together with sparsification-based techniques.