Welcome to the resource topic for 2025/480
Title:
Worst-case Analysis of Lattice Enumeration Algorithm over Modules
Authors: Jiseung Kim, Changmin Lee, Yongha Son
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 K = \mathbb{Q}[x]/\langle x^d + 1\rangle be a number field with a power-of-two integer d, and suppose that n\ln n = o(\ln d).
Then, the nonzero shortest vector in M \subset K^n can be found in time d^{\frac{d}{2e} + o(d)}, improving upon the previous lattice enumeration bound of (nd)^{\frac{nd}{2e}+ o(nd)}.
Our algorithm naturally extends to solving ideal-SVP. Given an ideal I \subset R, where R = \mathbb{Z}[x]/\langle x^t + 1 \rangle with a power-of-two integer t = nd, we can find the nonzero shortest element of I in time \exp(O(\frac{t}{2e} \ln \ln t)), improving upon the previous enumeration bound of \exp(O(\frac{t}{2e} \ln t)).
ePrint: https://eprint.iacr.org/2025/480
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .