Cryptology ePrint Archive: Report 2016/957

Computing generator in cyclotomic integer rings

Thomas Espitau and Pierre-Alain Fouque and 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.

Category / Keywords: public-key cryptography / Principal Ideal Problem, lattices, Post-Quantum, Ideal Lattice, FHE

Date: received 4 Oct 2016, last revised 11 Jun 2018

Contact author: alexandre gelin at uvsq fr; t espitau@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20180611:191749 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]