Paper 2017/142

Computing generator in cyclotomic integer rings, A subfield algorithm for the Principal Ideal Problem in L(1/2) and application to cryptanalysis of a FHE scheme

Jean-François Biasse, 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. 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 showed that solving the SPIP in such cyclotomic rings boiled down to solving the PIP. In this paper, we present a heuristic algorithm that solves the PIP in prime-power cyclotomic fields in subexponential time L(1/2) in the discriminant of the number field. This is achieved by descending to its totally real subfield. The implementation of our algorithm allows to recover in practice the secret key of the Smart and Vercauteren scheme, for the smallest proposed parameters (in dimension 256).

Note: This version is a merger decided by EUROCRYPT PC.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2017
Keywords
Principal Ideal ProblemcryptanalysisFHE
Contact author(s)
alexandre gelin @ uvsq fr
History
2018-06-11: revised
2017-02-20: received
See all versions
Short URL
https://ia.cr/2017/142
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/142,
      author = {Jean-François Biasse and Thomas Espitau and Pierre-Alain Fouque and Alexandre Gélin and Paul Kirchner},
      title = {Computing generator in cyclotomic integer rings, A subfield algorithm for the Principal Ideal Problem in L(1/2) and application to cryptanalysis of a FHE scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2017/142},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/142}},
      url = {https://eprint.iacr.org/2017/142}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.