Short generators without quantum computers: the case of multiquadratics

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

Paper 2017/404

Short generators without quantum computers: the case of multiquadratics

Jens Bauch, Daniel J. Bernstein, Henry de Valence, 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in EUROCRYPT 2017
Keywords: Public-key encryption lattice-based cryptography ideal lattices Soliloquy Gentry Smart--Vercauteren units multiquadratic fields
Contact author(s): authorcontact-multiquad @ box cr yp to
History: 2017-05-11: received
Short URL: https://ia.cr/2017/404
License: CC BY

BibTeX

@misc{cryptoeprint:2017/404,
      author = {Jens Bauch and Daniel J.  Bernstein and Henry de Valence and Tanja Lange and Christine van Vredendaal},
      title = {Short generators without quantum computers: the case of multiquadratics},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/404},
      year = {2017},
      url = {https://eprint.iacr.org/2017/404}
}