Cryptology ePrint Archive: Report 2017/404

Short generators without quantum computers: the case of multiquadratics

Jens Bauch and Daniel J. Bernstein and Henry de Valence and Tanja Lange and Christine van Vredendaal

Abstract: Finding a short element $g$ of a number field, given the ideal generated by $g$, is a classic problem in computational algebraic number theory. Solving this problem recovers the private key in cryptosystems introduced by Gentry, Smart-Vercauteren, Gentry-Halevi, Garg-Gentry-Halevi, et al. Work over the last few years has shown that for some number fields this problem has a surprisingly low post-quantum security level. This paper shows, and experimentally verifies, that for some number fields this problem has a surprisingly low pre-quantum security level.

Category / Keywords: public-key cryptography / Public-key encryption, lattice-based cryptography, ideal lattices, Soliloquy, Gentry, Smart--Vercauteren, units, multiquadratic fields

Original Publication (with major differences): IACR-EUROCRYPT-2017

Date: received 10 May 2017, last revised 11 May 2017

Contact author: authorcontact-multiquad at box cr yp to

Available format(s): PDF | BibTeX Citation

Version: 20170511:121019 (All versions of this report)

Short URL: ia.cr/2017/404

Discussion forum: Show discussion | Start new discussion