English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

A family of ring-based cryptosystems, including the multilinear maps of Garg, Gentry and Halevi [Candidate multilinear maps from ideal lattices, Advances in Cryptology—EUROCRYPT 2013, Lecture Notes in Comput. Sci. 7881, Springer, Heidelberg 2013, 1–17] and the fully homomorphic encryption scheme of Smart and Vercauteren [Fully homomorphic encryption with relatively small key and ciphertext sizes, Public Key Cryptography—PKC 2010, Lecture Notes in Comput. Sci. 6056, Springer, Berlin 2010, 420–443], are based on the hardness of finding a short generator of a principal ideal (short-PIP) in a number field typically inℚ  ⁢   (   ζ   2  s    ){\mathbb{Q}(\zeta_{2^{s}})}   . In this paper, we present a polynomial-time quantum algorithm for recovering a generator of a principal ideal inℚ  ⁢   (   ζ   2  s    ){\mathbb{Q}(\zeta_{2^{s}})}   , and we recall how this can be used to attack the schemes relying on the short-PIP inℚ  ⁢   (   ζ   2  s    ){\mathbb{Q}(\zeta_{2^{s}})}    by using the work of Cramer et al. [R. Cramer, L. Ducas, C. Peikert and O. Regev, Recovering short generators of principal ideals in cyclotomic rings, IACR Cryptology ePrint Archive 2015,  https://eprint.iacr.org/2015/313 ], which is derived from observations of Campbell, Groves and Shepherd [SOLILOQUY, a cautionary tale]. We put this attack into perspective by reviewing earlier attempts at providing an efficient quantum algorithm for solving the PIP inℚ  ⁢   (   ζ   2  s    ){\mathbb{Q}(\zeta_{2^{s}})}   . The assumption that short-PIP is hard was challenged by Campbell, Groves and Shepherd. They proposed an approach for solving short-PIP that proceeds in two steps: first they sketched a quantum algorithm for finding  an  arbitrary generator (not necessarily short) of the input principal ideal. Then they suggested that it is feasible to compute a  short  generator efficiently from the generator in step 1. Cramer et al. validated step 2 of the approach by giving a detailed analysis. In this paper, we focus on step 1, and we show that step 1 can run in quantum polynomial time if we use an algorithm for the continuous hidden subgroup problem (HSP) due to Eisenträger et al. [K. Eisenträger, S. Hallgren, A. Kitaev and F. Song, A quantum algorithm for computing the unit group of an arbitrary degree number field, Proceedings of the 2014 ACM Symposium on Theory of Computing—STOC’14, ACM, New York 2014, 293–302].

On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in ℚ(𝜁 2 𝑠 )