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 Campbell-Groves-Shepherd sketched
potential attacks against this problem; most notably, the latter
authors claimed a \emph{polynomial-time quantum} algorithm.
(Alternatively, replacing the quantum component with an algorithm of
Biasse and Fieker would yield a \emph{classical subexponential-time}
algorithm.) A key claim of Campbell \etal\ is that one step of their
algorithm---namely, decoding the \emph{log-unit} lattice of the ring
to recover a short generator from an arbitrary one---is 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 log-unit lattice is indeed efficiently decodable, for any
cyclotomic of prime-power 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 lattice-decoding
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 prime-power cyclotomic), finds a
Note: Moved appendices.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Published by the IACR in EUROCRYPT 2016
- Keywords
- Ideal LatticesCryptanalysis
- Contact author(s)
- ducas @ cwi nl
- History
- 2016-02-25: last of 3 revisions
- 2015-04-06: 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}, url = {https://eprint.iacr.org/2015/313} }