Worst cases for LLL on ideal lattices

Definitions and mathematical statement

For a full-rank Euclidean lattice $L=\sum_{i=1}^n{\mathbb{Z}} b_i\subset{\mathbb{R}}^n$, let $\lambda_1(L)=\min\{\|v\|:0\ne v\in L\}$. An LLL-reduced basis with parameter $\delta\in(1/4,1)$ satisfies the standard size-reduction and Lovász conditions. Writing $a=(\delta-1/4)^{-1}$, a usual shortest-vector approximation guarantee is \[ \|b_1\|\leq a^{(n-1)/2}\lambda_1(L). \] For $\delta=3/4$ this gives $2^{(n-1)/2}$. A determinant-based Hermite bound is a different performance measure and must not be substituted for this ratio without specifying the target.

The source asks for cyclic or ideal lattices on which LLL achieves its worst-case approximation factor. One conventional cyclic class consists of full-rank $L\subseteq{\mathbb{Z}}^n$ invariant under cyclic coordinate shift. Ideal lattices require an ideal in a specified order/number field or polynomial quotient ring and an embedding/norm; coefficient and canonical Euclidean embeddings need not yield the same geometry. The source does not choose these conventions.

A precise exhibit would give an infinite dimension-indexed family, its structural proof, and input bases/LLL parameters showing the specified output approximation ratio. The existence of a badly approximating reduced basis and the output of a fixed implementation on a prescribed input are related but distinct tasks. The record does not say whether worst-case means exact equality, arbitrarily close to the guarantee, or matching its asymptotic exponential scale, nor whether cyclic and ideal examples are separately required or either suffices. No general-lattice example is automatically an ideal example without proving the ring structure.

Short English statement

Construct structured cyclic or ideal lattice families attaining the intended worst LLL approximation behavior, with embeddings, parameters and input bases made explicit. The precise worst-case measure and structural class are unspecified.

Sources

• Local UnsolvedMath registry, permanent ID 8800068, exact source code catalogue entry, "Worst cases for LLL on ideal lattices"; 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 37, 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 attributes worst-case modular-knapsack/cyclic constructions to "Nguyen--Stehlé (2000)" and suggests analogous ideal families are implicit. It gives no exact publication, lattice family, embedding or reduction proof; the author/year and structural scope require checking. An implicit analogy is not treated as a verified ideal-lattice exhibit.
• Provenance flags current primary-literature status and redistribution terms NEEDS_REVIEW.