An LLL Algorithm for Module Lattices

Changmin Lee; Alice Pellet-Mary; Damien Stehlé; Alexandre Wallet

doi:10.1007/978-3-030-34621-8_3

An LLL Algorithm for Module Lattices

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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ⁿ 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.

Original language	English
Title of host publication	Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Editors	Steven D. Galbraith, Shiho Moriai
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	59-90
Number of pages	32
ISBN (Print)	9783030346201
DOIs	https://doi.org/10.1007/978-3-030-34621-8_3
Publication status	Published - 1 Jan 2019
Externally published	Yes
Event	25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019 - Kobe, Japan Duration: 8 Dec 2019 → 12 Dec 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11922 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019
Country/Territory	Japan
City	Kobe
Period	8/12/19 → 12/12/19

Access to Document

10.1007/978-3-030-34621-8_3

Cite this

Lee, C., Pellet-Mary, A., Stehlé, D., & Wallet, A. (2019). An LLL Algorithm for Module Lattices. In S. D. Galbraith, & S. Moriai (Eds.), Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (pp. 59-90). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11922 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-34621-8_3

Lee, Changmin ; Pellet-Mary, Alice ; Stehlé, Damien et al. / An LLL Algorithm for Module Lattices. Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. editor / Steven D. Galbraith ; Shiho Moriai. Springer Science and Business Media Deutschland GmbH, 2019. pp. 59-90 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{319aeaef110c455c8a0d6de31c2ff3c9,

title = "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 Kn 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.",

author = "Changmin Lee and Alice Pellet-Mary and Damien Stehl{\'e} and Alexandre Wallet",

note = "Publisher Copyright: {\textcopyright} 2019, International Association for Cryptologic Research.; 25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019 ; Conference date: 08-12-2019 Through 12-12-2019",

year = "2019",

month = jan,

day = "1",

doi = "10.1007/978-3-030-34621-8\_3",

language = "English",

isbn = "9783030346201",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "59--90",

editor = "Galbraith, \{Steven D.\} and Shiho Moriai",

booktitle = "Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

}

Lee, C, Pellet-Mary, A, Stehlé, D & Wallet, A 2019, An LLL Algorithm for Module Lattices. in SD Galbraith & S Moriai (eds), Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11922 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 59-90, 25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019, Kobe, Japan, 8/12/19. https://doi.org/10.1007/978-3-030-34621-8_3

An LLL Algorithm for Module Lattices. / Lee, Changmin; Pellet-Mary, Alice; Stehlé, Damien et al.
Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. ed. / Steven D. Galbraith; Shiho Moriai. Springer Science and Business Media Deutschland GmbH, 2019. p. 59-90 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11922 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - An LLL Algorithm for Module Lattices

AU - Lee, Changmin

AU - Pellet-Mary, Alice

AU - Stehlé, Damien

AU - Wallet, Alexandre

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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 Kn 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.

AB - 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 Kn 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.

U2 - 10.1007/978-3-030-34621-8_3

DO - 10.1007/978-3-030-34621-8_3

M3 - Conference contribution

AN - SCOPUS:85077007330

SN - 9783030346201

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 59

EP - 90

BT - Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

A2 - Galbraith, Steven D.

A2 - Moriai, Shiho

PB - Springer Science and Business Media Deutschland GmbH

T2 - 25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019

Y2 - 8 December 2019 through 12 December 2019

ER -

Lee C, Pellet-Mary A, Stehlé D, Wallet A. An LLL Algorithm for Module Lattices. In Galbraith SD, Moriai S, editors, Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Springer Science and Business Media Deutschland GmbH. 2019. p. 59-90. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-34621-8_3

An LLL Algorithm for Module Lattices

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this