Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies

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

8 Citations (Scopus)
53 Downloads (Pure)

Abstract

Choosing safe post-quantum parameters for the new CSIDH isogeny-based key-exchange system requires concrete analysis of the cost of quantum attacks. The two main contributions to attack cost are the number of queries in hidden-shift algorithms and the cost of each query. This paper analyzes algorithms for each query, introducing several new speedups while showing that some previous claims were too optimistic for the attacker. This paper includes a full computer-verified simulation of its main algorithm down to the bit-operation level.

Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsVincent Rijmen, Yuval Ishai
Place of PublicationCham
PublisherSpringer
Pages409-441
Number of pages33
ISBN (Print)9783030176556
DOIs
Publication statusPublished - 24 Apr 2019
Event38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019 - Darmstadt, Germany
Duration: 19 May 201923 May 2019

Publication series

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

Conference

Conference38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019
CountryGermany
CityDarmstadt
Period19/05/1923/05/19

    Fingerprint

Keywords

  • Circuits
  • Constant-time computation
  • Cryptanalysis
  • Elliptic curves
  • Isogenies
  • Quantum computation
  • Reversible computation

Cite this

Bernstein, D. J., Lange, T., Martindale, C., & Panny, L. (2019). Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies. In V. Rijmen, & Y. Ishai (Eds.), Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 409-441). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11477 LNCS). Cham: Springer. https://doi.org/10.1007/978-3-030-17656-3_15