Dimension-Preserving Reductions Between SVP and CVP in Different p-Norms
share
We show a number of reductions between the Shortest Vector Problem and the Closest Vector Problem over lattices in different ℓ_p norms (_p and _p 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 O(1/^1/p)γ-approximate _q to γ-approximate _p; ∙ a reduction from O(1/^1/p) γ-approximate _p to γ-approximate _q; and ∙ a reduction from O(1/^1+1/p)-_q to (1+)-unique _p (which in turn trivially reduces to (1+)-approximate _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 _p algorithms to solve O(1)-approximate _p. In the (important) special case when p = q, 1 ≤ p ≤ 2, and the _p oracle is exact, we show a stronger reduction, from O(1/^1/p)-_p to (exact) _p 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 √(m)-_2 to _2. We also note that the last two reductions can be combined to give a reduction from approximate-_p to _q 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 (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.
READ FULL TEXT