**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 ]