Paper 2019/1035 Original: eprint.iacr.org/2019/1035 ↗
An LLL Algorithm for Module Lattices
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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2020-06-19: last updated
- 2019-09-16: published
- Short URL
- https://ia.cr/2019/1035
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2019/1035}
}