CryptoDB
An LLL Algorithm for Module Lattices
| Authors: | |
|---|---|
| Download: | |
| 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
}