International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: An LLL Algorithm for Module Lattices

Authors:
Changmin Lee
Alice Pellet-Mary
Damien Stehlé
Alexandre Wallet
Download:
DOI: 10.1007/978-3-030-34621-8_3
Search ePrint
Search Google
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.
BibTeX
@article{asiacrypt-2019-30034,
  title={An LLL Algorithm for Module Lattices},
  booktitle={Advances in Cryptology – ASIACRYPT 2019},
  series={Advances in Cryptology – ASIACRYPT 2019},
  publisher={Springer},
  volume={11922},
  pages={59-90},
  doi={10.1007/978-3-030-34621-8_3},
  author={Changmin Lee and Alice Pellet-Mary and Damien Stehlé and Alexandre Wallet},
  year=2019
}