Deep LLL on Module Lattices
摘要
The LLL algorithm, renowned for its application to Euclidean lattices, plays a crucial role in lattice cryptanalysis by offering a standard method for refining lattice bases. With the increasing importance of module lattices—defined as modules over the ring of integers of a number field—in lattice cryptography, there is a compelling need to adapt the LLL algorithm for module lattices. This paper presents a generalization of the Deep LLL algorithm—a variant of LLL proposed by Schnorr and Euchner [25], which relaxes the restriction on the insertion position—to module lattices. Deep LLL has been widely used in BKZ reduction as a sub-procedure. Our algorithm is suitable as a sub-procedure in adapted BKZ reduction for module lattices. We implemented a proof-of-concept version of our algorithm, and compared to the LLL algorithm on module lattices, our algorithm outperformed it in all of our experimental cases. Additionally, we introduced a simplification that avoids invoking the computation of the Module Hermite Form and corrected mistakes in the previous work.