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 Original: eprint.iacr.org/2017/404 ↗

Short generators without quantum computers: the case of multiquadratics

Jens Bauch

Daniel J. Bernstein

Henry de Valence

Tanja Lange

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: Preprint.
History: 2017-05-11: last updated; 2017-05-11: published
Short URL: https://ia.cr/2017/404
License: https://creativecommons.org/licenses/by/4.0/

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}
}