Faster cyclic-lattice reduction

Definitions and mathematical statement

Let $R:{\mathbb{R}}^n\to{\mathbb{R}}^n$ be the cyclic coordinate shift $R(a_0,\ldots,a_{n-1})=(a_{n-1},a_0,\ldots,a_{n-2})$. A cyclic lattice is a lattice $L\subset{\mathbb{R}}^n$ preserved by $R$. Thus rotations of a lattice vector are again lattice vectors and have the same Euclidean norm.

A standard illustrative cyclic NTRU lattice is obtained from $A_q=({\mathbb{Z}}/q{\mathbb{Z}})[x]/(x^n-1)$ and $h\in A_q$: \[ L_{h,q}=\{(u,v)\in{\mathbb{Z}}[x]_{<n}^{\,2}:v\equiv hu\text{ in }A_q\}, \] viewed in ${\mathbb{Z}}^{2n}$ by coefficients. Simultaneous cyclic shifts of both blocks preserve this lattice. The source does not specify an NTRU lattice convention, so this example does not restrict its scope.

May's task is to speed up the rotation-augmented reduction algorithms for cyclic or NTRU lattices. Such algorithms exploit rotations of vectors during lattice reduction; the baseline procedure and the way rotations augment it are not supplied. A meaningful speed comparison needs a fixed input representation and distribution or worst-case regime, a baseline cost, and a common output quality or reduction guarantee. Merely accepting longer output vectors or weaker reduction is not automatically the requested speedup. No target complexity, memory bound, approximation factor, or exact-SVP requirement is stated.

Short English statement

Exploit cyclic rotations more efficiently in reduction algorithms for cyclic and NTRU lattices. The source omits the baseline algorithm, output guarantee, and computational benchmark needed to specify the requested speedup.

Sources

• Local UnsolvedMath registry, permanent ID 8800032, source code catalogue entry; attributed to Alexander May; no proposal year supplied; update 2026-08-06.
• IPAM, Workshop on Number Theory and Cryptography --- Open Problems (2006), attachment 6222, PDF page 29, printed slide 23: https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule. Registry access date 2026-07-29; PDF and legacy-PPT visual audit. Provenance reports 19 surviving attachments, 17 PDFs and two legacy PPT decks, with repetitions and solved definitions excluded. Present status and redistribution terms require review.
• The supplied summary mentions partial structural speedups and ring-lattice/NTRU cryptanalysis work without exact papers, a quantitative comparison, or a verified complete resolution.