Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time
Open Access
- 6 January 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 68 (2), 1-26
- https://doi.org/10.1145/3431725
Abstract
In this article, we study the geometry of units and ideals of cyclotomic rings and derive an algorithm to find a mildly short vector in any given cyclotomic ideal lattice in quantum polynomial time, under some plausible number-theoretic assumptions. More precisely, given an ideal lattice of the cyclotomic ring of conductor m, the algorithm finds an approximation of the shortest vector by a factor exp (Õ(√ m)). This result exposes an unexpected hardness gap between these structured lattices and general lattices: The best known polynomial time generic lattice algorithms can only reach an approximation factor exp (Õ(m)). Following a recent series of attacks, these results call into question the hardness of various problems over structured lattices, such as Ideal-SVP and Ring-LWE, upon which relies the security of a number of cryptographic schemes. NOTE. This article is an extended version of a conference paper [11]. The results are generalized to arbitrary cyclotomic fields. In particular, we also extend some results of Reference [10] to arbitrary cyclotomic fields. In addition, we prove the numerical stability of the method of Reference [10]. These extended results appeared in the Ph.D. dissertation of the third author [46].Keywords
Funding Information
- NWO (639.021.645)
- European Union Horizon 2020 Research and Innovation Program (780701)
This publication has 36 references indexed in Scilit:
- On lattices, learning with errors, random linear codes, and cryptographyJournal of the ACM, 2009
- Expander graphs based on GRH with an application to elliptic curve cryptographyJournal of Number Theory, 2009
- Class numbers of real cyclotomic fields of prime conductorMathematics of Computation, 2002
- Minus class groups of the fields of the 𝑙-th roots of unityMathematics of Computation, 1998
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- On bases of the Stickelberger ideal and of the group of circular units of a cyclotomic fieldJournal of Number Theory, 1992
- Explicit bounds for primality testing and related problemsMathematics of Computation, 1990
- Analytic formulas for the regulator of a number fieldInventiones Mathematicae, 1989
- A hierarchy of polynomial time lattice basis reduction algorithmsTheoretical Computer Science, 1987
- On the Stickelberger Ideal and the Circular Units of a Cyclotomic FieldAnnals of Mathematics, 1978