Paper 2025/480

Worst-case Analysis of Lattice Enumeration Algorithm over Modules

Abstract

This paper presents a systematic study of module lattices. We extend the lattice enumeration algorithm from Euclidean lattices to module lattices, providing a generalized framework. To incorporate the refined analysis by Hanrot and Stehlè (CRYPTO'07), we adapt key definitions from Euclidean lattices, such as HKZ-reduced bases and quasi-HKZ-reduced bases, adapting them to the pseudo-basis of modules. Furthermore, we revisit the lattice profile, a crucial aspect of enumeration algorithm analysis, and extend its analysis to module lattices. As a result, we improve the asymptotic performance of the module lattice enumeration algorithm and module-SVP. For instance, let $$ be a number field with a power-of-two integer $$, and suppose that $$. Then, the nonzero shortest vector in $$ can be found in time $$, improving upon the previous lattice enumeration bound of $$. Our algorithm naturally extends to solving ideal-SVP. Given an ideal $$, where $$ with a power-of-two integer $$, we can find the nonzero shortest element of $$ in time $$, improving upon the previous enumeration bound of $$.