Short generators without quantum computers: the case of multiquadratics

J. Bauch, D.J. Bernstein, H. de Valence, T. Lange, C. van Vredendaal

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2017
Subtitle of host publication36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 – May 4, 2017, Proceedings, Part I
EditorsJ.-S. Coron, J.B. Nielsen
Place of PublicationDordrecht
PublisherSpringer
Pages27-59
Number of pages33
ISBN (Electronic)978-3-319-56620-7
ISBN (Print)978-3-319-56619-1
DOIs
Publication statusPublished - 2017
Event36th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2017) - Paris, France
Duration: 30 Apr 20174 May 2017
Conference number: 36

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10210 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference36th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2017)
Abbreviated titleEUROCRYPT 2017
CountryFrance
City Paris
Period30/04/174/05/17

Keywords

  • Gentry
  • Ideal lattices
  • Lattice-based cryptography
  • Multiquadratic fields
  • Public-key encryption
  • Smart–Vercauteren
  • Soliloquy
  • Units

Fingerprint Dive into the research topics of 'Short generators without quantum computers: the case of multiquadratics'. Together they form a unique fingerprint.

  • Cite this

    Bauch, J., Bernstein, D. J., de Valence, H., Lange, T., & van Vredendaal, C. (2017). Short generators without quantum computers: the case of multiquadratics. In J-S. Coron, & J. B. Nielsen (Eds.), Advances in Cryptology – EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 – May 4, 2017, Proceedings, Part I (pp. 27-59). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10210 LNCS). Springer. https://doi.org/10.1007/978-3-319-56620-7_2