Short generators without quantum computers: the case of multiquadratics

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

doi:10.1007/978-3-319-56620-7_2

Short generators without quantum computers: the case of multiquadratics

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

Discrete Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

13 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 language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2017
Subtitle of host publication	36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 – May 4, 2017, Proceedings, Part I
Editors	J.-S. Coron, J.B. Nielsen
Place of Publication	Dordrecht
Publisher	Springer
Pages	27-59
Number of pages	33
ISBN (Electronic)	978-3-319-56620-7
ISBN (Print)	978-3-319-56619-1
DOIs	https://doi.org/10.1007/978-3-319-56620-7_2
Publication status	Published - 2017
Event	36th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2017) - Paris, France Duration: 30 Apr 2017 → 4 May 2017 Conference number: 36

Publication series

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

Conference

Conference	36th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2017)
Abbreviated title	EUROCRYPT 2017
Country/Territory	France
City	Paris
Period	30/04/17 → 4/05/17

Keywords

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

Access to Document

10.1007/978-3-319-56620-7_2

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

Bauch, J. ; Bernstein, D.J. ; de Valence, H. et al. / Short generators without quantum computers : the case of multiquadratics. 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. editor / J.-S. Coron ; J.B. Nielsen. Dordrecht : Springer, 2017. pp. 27-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8c7968c5e9074417b95ea11a55beb681,

title = "Short generators without quantum computers: the case of multiquadratics",

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.",

keywords = "Gentry, Ideal lattices, Lattice-based cryptography, Multiquadratic fields, Public-key encryption, Smart–Vercauteren, Soliloquy, Units",

author = "J. Bauch and D.J. Bernstein and {de Valence}, H. and T. Lange and {van Vredendaal}, C.",

year = "2017",

doi = "10.1007/978-3-319-56620-7_2",

language = "English",

isbn = "978-3-319-56619-1",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "27--59",

editor = "J.-S. Coron and J.B. Nielsen",

booktitle = "Advances in Cryptology – EUROCRYPT 2017",

address = "Germany",

note = "36th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2017), EUROCRYPT 2017 ; Conference date: 30-04-2017 Through 04-05-2017",

}

Bauch, J, Bernstein, DJ, de Valence, H, Lange, T & van Vredendaal, C 2017, Short generators without quantum computers: the case of multiquadratics. in J-S Coron & JB 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10210 LNCS, Springer, Dordrecht, pp. 27-59, 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2017), Paris, France, 30/04/17. https://doi.org/10.1007/978-3-319-56620-7_2

Short generators without quantum computers : the case of multiquadratics. / Bauch, J.; Bernstein, D.J.; de Valence, H. et al.

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. ed. / J.-S. Coron; J.B. Nielsen. Dordrecht : Springer, 2017. p. 27-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10210 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Short generators without quantum computers

T2 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2017)

AU - Bauch, J.

AU - Bernstein, D.J.

AU - de Valence, H.

AU - Lange, T.

AU - van Vredendaal, C.

N1 - Conference code: 36

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Gentry

KW - Ideal lattices

KW - Lattice-based cryptography

KW - Multiquadratic fields

KW - Public-key encryption

KW - Smart–Vercauteren

KW - Soliloquy

KW - Units

UR - http://www.scopus.com/inward/record.url?scp=85018697768&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-56620-7_2

DO - 10.1007/978-3-319-56620-7_2

M3 - Conference contribution

AN - SCOPUS:85018697768

SN - 978-3-319-56619-1

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 27

EP - 59

BT - Advances in Cryptology – EUROCRYPT 2017

A2 - Coron, J.-S.

A2 - Nielsen, J.B.

PB - Springer

CY - Dordrecht

Y2 - 30 April 2017 through 4 May 2017

ER -

Bauch J, Bernstein DJ, de Valence H, Lange T, van Vredendaal C. Short generators without quantum computers: the case of multiquadratics. In Coron J-S, Nielsen JB, editors, 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. Dordrecht: Springer. 2017. p. 27-59. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-56620-7_2

Short generators without quantum computers: the case of multiquadratics

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this