Paper 2019/1035

An LLL Algorithm for Module Lattices

Changmin Lee, Alice Pellet-Mary, Damien Stehlé, and Alexandre Wallet

Abstract

The LLL algorithm takes as input a basis of a Euclidean lattice, and, within a polynomial number of operations, it outputs another basis of the same lattice but consisting of rather short vectors. We provide a generalization to R-modules contained in K^n for arbitrary number fields K and dimension n, with R denoting the ring of integers of K. Concretely, we introduce an algorithm that efficiently finds short vectors in rank-n modules when given access to an oracle that finds short vectors in rank-2 modules, and an algorithm that efficiently finds short vectors in rank-2 modules given access to a Closest Vector Problem oracle for a lattice that depends only on K. The second algorithm relies on quantum computations and its analysis is heuristic. In the special case of free modules, we propose a dequantized version of this algorithm.

Note: update: dequantizing the algorithm for free modules

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in Asiacrypt 2019
Contact author(s)
changmin lee @ ens-lyon fr
alice pellet-mary @ ens-lyon org
damien stehle @ ens-lyon fr
wallet alexandre @ gmail com
History
2020-06-19: revised
2019-09-16: received
See all versions
Short URL
https://ia.cr/2019/1035
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1035,
      author = {Changmin Lee and Alice Pellet-Mary and Damien Stehlé and Alexandre Wallet},
      title = {An LLL Algorithm for Module Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1035},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1035}},
      url = {https://eprint.iacr.org/2019/1035}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.