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 (SG-PIP): 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 log-unit 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 prime-power 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 SG-PIP 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)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Lattice-based cryptographyprincipal ideal latticesSG-PIPSVPkey recoverycryptanalysis
Contact author(s)
twunderer @ cdc informatik tu-darmstadt de
History
2017-09-19: last of 2 revisions
2017-06-05: received
See all versions
Short URL
https://ia.cr/2017/513
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.