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 2 Feb 2017

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

Available format(s): PDF | BibTeX Citation

Version: 20170202:145228 (All versions of this report)

Short URL: ia.cr/2016/957

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]