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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Deep LLL on Module Lattices

  • Yang Zhou,
  • Heyang Cao,
  • Mingsheng Wang

摘要

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.