Paper 2025/480

Worst-case Analysis of Lattice Enumeration Algorithm over Modules

Abstract

We study lattice enumeration in rank-$n$ modules over number fields. Building on the refined Euclidean analysis of Hanrot and Stehl\'e (CRYPTO~2007), we develop a module analogue of Kannan--Hanrot--Stehl\'e enumeration. Our approach works directly with pseudo-bases and introduces module counterparts of HKZ reduction and quasi-HKZ reduction. We also extend the notion of a lattice \emph{profile} to the module setting and prove tail-product bounds for the $\mathbb{Z}$-basis obtained from a module-HKZ-reduced pseudo-basis. These bounds yield a strictly improved asymptotic enumeration complexity compared to the naive reduction that views a rank-$n$ module as an $(nd)$-dimensional Euclidean lattice. As a representative consequence, for $K=\mathbb{Q}[x]/\langle x^d+1\rangle$ with $d$ a power of two and a rank-$n$ module $M\subset K^n$ with $n\ge 3$, we show that module-SVP can be solved in time $\Delta_K\cdot n^{\frac{nd}{2e}+o(nd)}$, where $\Delta_K$ is the discriminant of $K$. This improves over the Euclidean enumeration bound $(nd)^{\frac{nd}{2e}+o(nd)}$. As an application, for $R=\mathbb{Z}[x]/\langle x^t+1\rangle$ with $t$ a power of two and an ideal $I\subset R$, we obtain an ideal-SVP algorithm running in time $\exp\!\bigl(\frac{t}{2e}\ln\ln t + O(t)\bigr)$, improving upon the worst-case enumeration bound $\exp\!\bigl(\frac{t}{2e}\ln t + o(t)\bigr)$.

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