### A fully classical LLL algorithm for modules

##### Abstract

The celebrated LLL algorithm for Euclidean lattices is central to cryptanalysis of well- known and deployed protocols as it provides approximate solutions to the Shortest Vector Problem (SVP). Recent interest in algebrically structured lattices (e.g., for the efficient implementation of lattice- based cryptography) has prompted adapations of LLL to such structured lattices, and, in particular, to module lattices, i.e., lattices that are modules over algebraic ring extensions of the integers. One of these adaptations is a quantum algorithm proposed by Lee, Pellet-Mary, Stehlé and Wallet (Asiacrypt 2019). In this work, we dequantize the algorithm of Lee et al., and provide a fully classical LLL-type algorithm for arbitrary module lattices that achieves same SVP approximation factors, single exponential in the rank of the input module. Just like the algorithm of Lee et al., our algorithm runs in polynomial time given an oracle that solves the Closest Vector Problem (CVP) in a certain, fixed lattice L_K that depends only on the number field K.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Lattices
Contact author(s)
gdemicheli @ eng ucsd edu
daniele @ cs ucsd edu
History
2022-10-14: approved
See all versions
Short URL
https://ia.cr/2022/1356

CC BY

BibTeX

@misc{cryptoeprint:2022/1356,
author = {Gabrielle De Micheli and Daniele Micciancio},
title = {A fully classical LLL algorithm for modules},
howpublished = {Cryptology ePrint Archive, Paper 2022/1356},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1356}},
url = {https://eprint.iacr.org/2022/1356}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.