NP-hardness of ideal-lattice SVP

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})$. For $\gamma\ge1$, the gap decision version of $\gamma$-approximate SVP, given $L$ and a positive rational $r$, distinguishes the promised cases $\lambda_1(L)\le r$ and $\lambda_1(L)>\gamma r$. At $\gamma=1$ this is the exact shortest-vector decision problem. NP-hardness asks whether every problem in NP admits a polynomial-time reduction to the stated problem.

Statement recorded in the supplied source.

Determine whether SVP restricted to ideal lattices is NP-hard in the exact case, and determine the approximation factors for which NP-hardness holds. Address separately the cyclic-lattice subclass $f=X^n-1$. [S2]

Short English statement

Establish or refute NP-hardness of exact and approximate shortest-vector problems on ideal lattices, including cyclic lattices.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 8800064 (AMR-087-0064). 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, 35. https://helper.ipam.ucla.edu/publications/SCWS1/SCWS1_6240.pdf.