SVP-to-CVP reduction within ideal lattices

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A full-rank lattice $L=L(B)=B\mathbb Z^n\subset\mathbb R^n$ is specified by a rational basis matrix $B$. Length uses the Euclidean norm. Put $\lambda_1(L)=\min\{\|v\|_2:0\ne v\in L\}$. For a monic $f\in\mathbb Z[X]$ of degree $n$, identify $\mathbb Z[X]/(f)$ with $\mathbb Z^n$ by the coefficient vector of the representative of degree less than $n$. An ideal lattice is the full-rank lattice associated to an ideal of this ring in this coefficient embedding. The case $f=X^n-1$ is cyclic: it is invariant under $(v_1,\ldots,v_n)\mapsto(v_n,v_1,\ldots,v_{n-1})$. Exact SVP asks for a nonzero $v\in L$ of length $\lambda_1(L)$. Exact CVP, given the same type of lattice and a rational target $t\in\mathbb Q^n$, asks for $v\in L$ minimizing $\|v-t\|_2$. A polynomial-time oracle reduction may call a solver for the target problem while doing polynomially many operations in the bit length of its rational input.

Statement recorded in the supplied source.

Does SVP admit a polynomial-time reduction to CVP that keeps the oracle lattice inside the class of cyclic lattices? Does such a reduction exist inside the class of ideal lattices? [S2]

Short English statement

Can the known general shortest-vector-to-closest-vector reduction be carried out while preserving cyclic or ideal structure?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 8800067 (AMR-087-0067). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Daniele Micciancio, Ideal Lattices: cryptographic applications and open problems, IPAM Number Theory and Cryptography: Open Problems workshop (9--13 October 2006), PDF pages 5, 8, 23, 36. https://helper.ipam.ucla.edu/publications/SCWS1/SCWS1_6240.pdf.