Algebraic algorithms for ideal-lattice problems

Definitions and mathematical statement

For a number field $K$ of degree $n$ and a nonzero ideal $I$ of a specified order, an ideal lattice is the image $L=\sigma(I)\subset{\mathbb{R}}^n$ under a chosen Euclidean embedding. In a standard canonical convention, real embeddings and the $\sqrt2$-weighted real/imaginary parts of complex embeddings give the Euclidean coordinates. A coefficient embedding in a polynomial quotient is another possible convention and may change the metric problem.

The source asks to use algebraic tools to solve computational problems on ideal lattices efficiently. Examples of distinct lattice tasks include shortest-vector search \[ \text{find }0\ne v\in L\text{ minimizing }\|v\|, \] approximate shortest-vector search $\|v\|\leq\gamma(n)\lambda_1(L)$, closest-vector search, and basis reduction. Ideal arithmetic, ideal equivalence and principal-generator problems are related algebraic tasks but are not automatically equivalent to these metric problems. The source does not designate one task or demand that all be solved.

A precise algorithmic target must fix field/ring families, embeddings and norms, input representations, the exact or approximate output guarantee, worst-case versus average-case promises, and classical versus quantum resources. Efficiency may depend on degree, discriminant and coefficient bit lengths; none of these bounds is given. Thus this is an algebraic-algorithm programme, not an asserted polynomial-time algorithm for unrestricted Ideal-SVP or an implied break of every ring-based cryptographic assumption.

Short English statement

Exploit ideal-lattice algebraic structure to improve specified computational problems. The field family, norm, output quality and computational model must be fixed before efficiency or security implications can be stated.

Sources

• Local UnsolvedMath registry, permanent ID 8800074, exact source code catalogue entry, "Algebraic algorithms for ideal-lattice problems"; attributed to Daniele Micciancio, no proposed year supplied. Registry status partially solved, classification PARTIAL-PROGRESS.
• IPAM Workshop on Number Theory and Cryptography---Open Problems (2006), attachment 6240, PDF page 40, https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule. Supplied pdf-and-legacy-ppt visual audit accessed July 29, 2026; provenance records 17 PDFs/two PPT decks inspected with repeated builds excluded. No PDF/PPT was accessed here.
• The supplied summary reports special-ring algebraic/quantum progress and cites Eisenträger--Hallgren--Kitaev--Song (2014), without a title or exact problem/hypothesis statement. Its broad ring-LWE/Ideal-SVP attack wording is not treated as establishing an equivalence or a general solver. The summary reports no complete efficient general solver; this is an unverified progress assessment, not an impossibility theorem.
• Provenance flags current primary-literature status and redistribution terms NEEDS_REVIEW.