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 encryptionlattice-based cryptographyideal latticesSoliloquyGentrySmart--Vercauterenunitsmultiquadratic fields
Contact author(s)
authorcontact-multiquad @ box cr yp to
History
2017-05-11: received
Short URL
https://ia.cr/2017/404
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2017/404}},
      url = {https://eprint.iacr.org/2017/404}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.