An LLL Algorithm for Module Lattices
| Autor: | Damien Stehlé, Alexandre Wallet, Alice Pellet-Mary, Changmin Lee |
|---|---|
| Přispěvatelé: | Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), NTT Secure Platform Laboratories [Tokyo], Nippon Telegraph & Telephone Corporation - NTT, Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL) |
| Rok vydání: | 2019 |
| Předmět: |
Rank (linear algebra)
Basis (linear algebra) Computer science Generalization Heuristic (computer science) 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Algebraic number field 01 natural sciences Ring of integers Oracle [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] Dimension (vector space) 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering [INFO]Computer Science [cs] Algorithm ComputingMilieux_MISCELLANEOUS |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030346201 ASIACRYPT (2) Advances in Cryptology – ASIACRYPT 2019-25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8–12, 2019, Proceedings, Part II Lecture Notes in Computer Science Lecture Notes in Computer Science-Advances in Cryptology – ASIACRYPT 2019 ASIACRYPT ASIACRYPT, 2019, Kobe, Japan. pp.59-90, ⟨10.1007/978-3-030-34621-8_3⟩ |
| ISSN: | 0302-9743 1611-3349 |
| DOI: | 10.1007/978-3-030-34621-8_3 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|