Cryptology ePrint Archive: Report 2019/1035

An LLL Algorithm for Module Lattices

Changmin Lee and Alice Pellet-Mary and 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.

Category / Keywords: foundations /

Original Publication (with major differences): IACR-ASIACRYPT-2019

Date: received 11 Sep 2019

Contact author: changmin lee at ens-lyon fr, alice pellet-mary@ens-lyon org, damien stehle@ens-lyon fr, wallet alexandre@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190916:094151 (All versions of this report)

Short URL: ia.cr/2019/1035


[ Cryptology ePrint archive ]