Paper 2025/480

Exact SVP and CVP in Structured Lattices: Polynomial-Space Algorithms and Reductions

Abstract

Although module lattices possess richer algebraic structure than general lattices, their algorithmic benefits for exact shortest and closest vector problems (SVP and CVP) remain relatively unexplored. For general $N$-dimensional lattices, the fastest known polynomial-space algorithms take $N^{\Theta(N)}$ time, whereas known $2^{O(N)}$-time algorithms require exponential space. We investigate how the algebraic structure of modules over number fields can be exploited to obtain faster exact algorithms in polynomial space. We develop a common framework based on reduced module flags and lattice-point enumeration in Euclidean balls, with two complementary approaches. The first uses recursive subfield descent, yielding deterministic $2^{O(N)}$-time algorithms for both SVP and CVP on fixed-rank modules over totally real or CM fields with bounded root discriminant and bounded-degree subfield chains. Infinite unramified class field towers provide families of unbounded dimension satisfying these conditions. The second approach reduces lattice-point enumeration in Euclidean balls to exact SVP, without requiring a subfield chain or any bound on the root discriminant. For fixed-rank modules with root discriminant $\rho=d^{o(1)}$, where $d$ is the field degree, this reduction yields deterministic SVP and CVP algorithms in time $d^{d/(2\mathrm e)+o(d)}$. Furthermore, the second approach yields exact CVP algorithms for semistable lattices, including cyclotomic ideal lattices, without any restriction on the root discriminant. The resulting running times are $N^{N/(2\mathrm e)+o(N)}$ deterministically and $N^{N/(4\mathrm e)+o(N)}$ with randomization. While the two approaches above initially focus on fixed-rank modules, we further extend both to modules of growing rank. In particular, for modules of rank $\Theta(\log N)$ over fields with bounded root discriminant, we obtain deterministic SVP and CVP algorithms in times $(\log N)^{N/(2\mathrm e)+o(N)}$ and $(\log N)^{N/2+o(N)}$, respectively.

Note: 2025-10-11. remove worst-bound assumption and revise the paper. 2026-02-20. improve the editorial qualties, and update rank-2 module HKZ