Quantum algorithm for 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})$.

Statement recorded in the supplied source.

Develop a quantum algorithm, polynomial in the bit length of the monic polynomial $f$ and a rational basis of its ideal lattice $L$, which outputs $0\ne v\in L$ with $\|v\|_2=\lambda_1(L)$. [S2]

Short English statement

Find an efficient quantum algorithm for exact shortest nonzero vectors in ideal lattices.

Sources

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