Paper 2015/313
Recovering Short Generators of Principal Ideals in Cyclotomic Rings
Ronald Cramer, Léo Ducas, Chris Peikert, and Oded Regev
Abstract
A handful of recent cryptographic proposals rely on the conjectured hardness of the following problem in the ring of integers of a cyclotomic number field: given a basis of a principal ideal that is guaranteed to have a ``rather short'' generator, find such a generator. Recently, Bernstein and CampbellGrovesShepherd sketched potential attacks against this problem; most notably, the latter authors claimed a \emph{polynomialtime quantum} algorithm. (Alternatively, replacing the quantum component with an algorithm of Biasse and Fieker would yield a \emph{classical subexponentialtime} algorithm.) A key claim of Campbell \etal\ is that one step of their algorithmnamely, decoding the \emph{logunit} lattice of the ring to recover a short generator from an arbitrary oneis classically efficient (whereas the standard approach on general lattices takes exponential time). However, very few convincing details were provided to substantiate this claim. In this work, we clarify the situation by giving a rigorous proof that the logunit lattice is indeed efficiently decodable, for any cyclotomic of primepower index. Combining this with the quantum algorithm from a recent work of Biasse and Song confirms the main claim of Campbell \etal\xspace Our proof consists of two main technical contributions: the first is a geometrical analysis, using tools from analytic number theory, of the standard generators of the group of cyclotomic units. The second shows that for a wide class of typical distributions of the short generator, a standard latticedecoding algorithm can recover it, given any generator. By extending our geometrical analysis, as a second main contribution we obtain an efficient algorithm that, given any generator of a principal ideal (in a primepower cyclotomic), finds a $2^{\tilde{O}(\sqrt{n})}$approximate shortest vector in the ideal. Combining this with the result of Biasse and Song yields a quantum polynomialtime algorithm for the $2^{\tilde{O}(\sqrt{n})}$approximate Shortest Vector Problem on principal ideal lattices.
Note: Moved appendices.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published by the IACR in EUROCRYPT 2016
 Keywords
 Ideal LatticesCryptanalysis
 Contact author(s)
 ducas @ cwi nl
 History
 20160225: last of 3 revisions
 20150406: received
 See all versions
 Short URL
 https://ia.cr/2015/313
 License

CC BY
BibTeX
@misc{cryptoeprint:2015/313, author = {Ronald Cramer and Léo Ducas and Chris Peikert and Oded Regev}, title = {Recovering Short Generators of Principal Ideals in Cyclotomic Rings}, howpublished = {Cryptology ePrint Archive, Paper 2015/313}, year = {2015}, note = {\url{https://eprint.iacr.org/2015/313}}, url = {https://eprint.iacr.org/2015/313} }