Computing Generator in Cyclotomic Integer Rings A Subfield Algorithm for the Principal Ideal Problem in L_(∆_K) ((1/2)) and Application to the Cryptanalysis of a FHE Scheme
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_(∆_K|) (1/2), where ∆_K denotes 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).
展开▼
机译：简称为PIP（respon。SPIP）的理想理想问题（respon。short Principal Ideal Problem），在于在数字字段的整数环中找到具有理想理想的生成器（respon。short generator）。几种基于晶格的密码系统依赖于这两个问题的假定硬度。实际上，它们中的大多数不使用任意数字字段，而是使用2的幂的环原子字段。 Smart和Vercauteren完全同态加密方案以及Garg，Gentry和Halevi的多线性图体现了这一常见限制。最近，克莱默（Cramer），杜卡斯（Ducas），佩克特（Peikert）和雷格夫（Regev）表明，在这样的环原子环中求解SPIP归结为求解PIP。在本文中，我们提出了一种启发式算法，可以解决次幂时间L_（∆_K |）（1/2）中素数功率旋回场中的PIP，其中∆_K表示数字场的判别式。这是通过下降到其完全真实的子字段来实现的。我们算法的实现允许针对最小的建议参数（在维数256中）在实践中恢复Smart和Vercauteren方案的秘密密钥。
展开▼
