Paper 2016/957

Computing generator in cyclotomic integer rings

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


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Principal Ideal ProblemlatticesPost-QuantumIdeal LatticeFHE
Contact author(s)
alexandre gelin @ uvsq fr
t espitau @ gmail com
2018-06-11: last of 5 revisions
2016-10-04: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.