Search

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(-õ (vm)). 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(-O (m)). Following a recent series of attacks, these results call into question the hardness of various problems over structured lattices, suchas Ideal-SVP and Ring-LWE, upon which relies the security of a number of cryptographic schemes. [ABSTRACT FROM AUTHOR]

In this work we consider the closest vector problem (CVP)-a problem also known as maximum-likelihood decoding-in the tensor of two root lattices of type A ( $$A_m \otimes A_n$$ ), as well as in their duals ( $$A^*_m \otimes A^*_n$$ ). This problem is mainly motivated by lattice based cryptography, where the cyclotomic rings $${\mathbb {Z}}[\zeta _c]$$ (resp. its co-different $${\mathbb {Z}}[\zeta _c]^\vee $$ ) play a central role, and turn out to be isomorphic as lattices to tensors of $$A^*$$ lattices (resp. A root lattices). In particular, our results lead to solving CVP in $${\mathbb {Z}}[\zeta _c]$$ and in $${\mathbb {Z}}[\zeta _c]^\vee $$ for conductors of the form $$c = 2^\alpha p^\beta q^\gamma $$ for any two odd primes p, q. For the primal case $$A_m \otimes A_n$$ , we provide a full characterization of the Voronoi region in terms of simple cycles in the complete directed bipartite graph $$K_{m+1,n+1}$$ . This leads-relying on the Bellman-Ford algorithm for negative cycle detection-to a CVP algorithm running in polynomial time. Precisely, our algorithm performs $$O(l\ m^2 n^2 \min \{m,n\})$$ operations on reals, where l is the number of bits per coordinate of the input target. For the dual case, we use a gluing-construction to solve CVP in sub-exponential time $$O(n m^{n+1})$$ . [ABSTRACT FROM AUTHOR]