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].
, ,
Journal of the ACM
Centrum Wiskunde & Informatica, Amsterdam, The Netherlands

Cramer, R.J.F, Ducas, L, & Wesolowski, B.P.C. (2021). Mildly short vectors in cyclotomic ideal lattices in quantum polynomial time. Journal of the ACM, 68(2). doi:10.1145/3431725