Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time Article Swipe
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.1145/3431725
· OA: W3118425873
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. N OTE . 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].
