Paper 2017/513
Recovering Short Generators of Principal Fractional Ideals in Cyclotomic Fields of Conductor $p^\alpha q^\beta$
Patrick Holzer and Thomas Wunderer
Abstract
Several recent cryptographic constructions  including a public key encryption scheme, a fully homomorphic encryption scheme, and a candidate multilinear map construction  rely on the hardness of the short generator principal ideal problem (SGPIP): given a $\mathbb{Z}$basis of some principal (fractional) ideal in an algebraic number field that is guaranteed to have an exceptionally short generator with respect to the logarithmic embedding, find a shortest generator of the principal ideal. The folklore approach to solve this problem is to split it into two subproblems. First, recover some arbitrary generator of the ideal, which is known as the principal ideal problem (PIP). Second, solve a bounded distance decoding (BDD) problem in the logunit lattice to transform this arbitrary generator into a shortest generator of the ideal. The first problem, i.e., solving the PIP, is known to be solvable in polynomial time on quantum computers for arbitrary number fields under the generalized Riemann hypothesis due to Biasse and Song. Cramer, Ducas, Peikert, and Regev showed, based on the work of Campbell, Groves, and Shepherd, that the second problem can be solved in polynomial time on classical computers for cyclotomic number fields of primepower conductor. In this work, we extend the work of Cramer, Ducas, Peikert, and Regev to cyclotomic number fields $K=\mathbb{Q}(\xi_m)$ of conductor $m=p^\alpha q^\beta$, where $p,q$ are distinct odd primes. In more detail, we show that the second problem can be solved in classical polynomial time (with quantum polynomial time precomputation) under some sufficient conditions, if $(p,q)$ is an $(\alpha, \beta)$generator prime pair, a new notion introduced in this work. We further provide experimental evidence that suggests that roughly $35\%$ of all prime pairs are $(\alpha, \beta)$generator prime pairs for all $\alpha$ and $\beta$. Combined with the work of Biasse and Song our results show that under sufficient conditions the SGPIP can be solved in quantum polynomial time in cyclotomic number fields of composite conductor of the form $p^\alpha q^\beta$.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 Latticebased cryptographyprincipal ideal latticesSGPIPSVPkey recoverycryptanalysis
 Contact author(s)
 twunderer @ cdc informatik tudarmstadt de
 History
 20170919: last of 2 revisions
 20170605: received
 See all versions
 Short URL
 https://ia.cr/2017/513
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/513, author = {Patrick Holzer and Thomas Wunderer}, title = {Recovering Short Generators of Principal Fractional Ideals in Cyclotomic Fields of Conductor $p^\alpha q^\beta$}, howpublished = {Cryptology ePrint Archive, Paper 2017/513}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/513}}, url = {https://eprint.iacr.org/2017/513} }