Paper 2016/957

Computing generator in cyclotomic integer rings

Thomas Espitau, Pierre-Alain Fouque, Alexandre Gélin, and Paul Kirchner

Abstract

The Principal Ideal Problem (resp. Short Principal Ideal Problem), shorten as PIP (resp. SPIP), consists in finding a generator (resp. short generator) of a principal ideal in the ring of integers of a number field. Several lattice-based cryptosystems rely on the presumed hardness of these two problems. Yet, in practice, most of them do not use an arbitrary number field but a power-of-two cyclotomic field. The Smart and Vercauteren fully homomorphic encryption scheme and the multilinear map of Garg, Gentry and Halevi epitomize this common restriction. Recently, Cramer, Ducas, Peikert and Regev show that solving the SPIP in such cyclotomic rings boils down to solving the PIP. We complete their result by an algorithm that solves PIP in cyclotomic fields in subexponential time $L_{|\Delta_K|} (1/2) = 2^{N^{1/2+o(1)}}$, where $\Delta_K$ denotes the discriminant of the number field and N its degree. This asymptotic complexity could be compared with the one obtained by Biasse and Fieker method, that aims at finding a generator as we do, but runs in L_{|\Delta_K|} (2/3). Besides this theoretical improvement, our algorithm permits to recover in practice the secret key of the Smart and Vercauteren scheme, for the smallest proposed parameters.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Principal Ideal ProblemlatticesPost-QuantumIdeal LatticeFHE
Contact author(s)
alexandre gelin @ uvsq fr
t espitau @ gmail com
History
2018-06-11: last of 5 revisions
2016-10-04: received
See all versions
Short URL
https://ia.cr/2016/957
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/957,
      author = {Thomas Espitau and Pierre-Alain Fouque and Alexandre Gélin and Paul Kirchner},
      title = {Computing generator in cyclotomic integer rings},
      howpublished = {Cryptology ePrint Archive, Paper 2016/957},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/957}},
      url = {https://eprint.iacr.org/2016/957}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.