Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies

Daniel J. Bernstein; Tanja Lange; Chloe Martindale; Lorenz Panny

doi:10.1007/978-3-030-17656-3_15

Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies

Daniel J. Bernstein
, Tanja Lange
, Chloe Martindale
, Lorenz Panny

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

51 Citations (Scopus)

388 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 language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Editors	Vincent Rijmen, Yuval Ishai
Place of Publication	Cham
Publisher	Springer
Pages	409-441
Number of pages	33
ISBN (Print)	9783030176556
DOIs	https://doi.org/10.1007/978-3-030-17656-3_15
Publication status	Published - 24 Apr 2019
Event	38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019 - Darmstadt, Germany Duration: 19 May 2019 → 23 May 2019

Publication series

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

Conference

Conference	38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019
Country/Territory	Germany
City	Darmstadt
Period	19/05/19 → 23/05/19

Funding

Author list in alphabetical order; see https://www.ams.org/profession/leaders/ culture/CultureStatement04.pdf. This work was supported in part by the Commission of the European Communities through the Horizon 2020 program under project number 643161 (ECRYPT-NET), 645622 (PQCRYPTO), 645421 (ECRYPT-CSA), and CHIST-ERA USEIT (NWO project 651.002.004); the Netherlands Organisation for Scientific Research (NWO) under grants 628.001.028 (FASOR) and 639.073.005; and the U.S. National Science Foundation under grant 1314919. “Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation” (or other funding agencies). Permanent ID of this document: 9b88023d7d9ef3f55b11b6f009131c9f. Date of this document: 2019.02.28.

Keywords

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

Access to Document

10.1007/978-3-030-17656-3_15

Cryptology ePrint Archive versionFinal author version , 777 KB

https://eprint.iacr.org/2018/1059

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). Springer. https://doi.org/10.1007/978-3-030-17656-3_15

Bernstein, Daniel J. ; Lange, Tanja ; Martindale, Chloe et al. / Quantum circuits for the CSIDH : optimizing quantum evaluation of isogenies. Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. editor / Vincent Rijmen ; Yuval Ishai. Cham : Springer, 2019. pp. 409-441 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{27d3080cb960448c8b56cfba98f6f336,

title = "Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies",

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

keywords = "Circuits, Constant-time computation, Cryptanalysis, Elliptic curves, Isogenies, Quantum computation, Reversible computation",

author = "Bernstein, \{Daniel J.\} and Tanja Lange and Chloe Martindale and Lorenz Panny",

year = "2019",

month = apr,

day = "24",

doi = "10.1007/978-3-030-17656-3\_15",

language = "English",

isbn = "9783030176556",

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

publisher = "Springer",

pages = "409--441",

editor = "Vincent Rijmen and Yuval Ishai",

booktitle = "Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings",

address = "Germany",

note = "38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019 ; Conference date: 19-05-2019 Through 23-05-2019",

}

Bernstein, DJ, 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11477 LNCS, Springer, Cham, pp. 409-441, 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019, Darmstadt, Germany, 19/05/19. https://doi.org/10.1007/978-3-030-17656-3_15

Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies. / Bernstein, Daniel J.; Lange, Tanja; Martindale, Chloe et al.
Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. ed. / Vincent Rijmen; Yuval Ishai. Cham: Springer, 2019. p. 409-441 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11477 LNCS).

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

TY - GEN

T1 - Quantum circuits for the CSIDH

T2 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019

AU - Bernstein, Daniel J.

AU - Lange, Tanja

AU - Martindale, Chloe

AU - Panny, Lorenz

PY - 2019/4/24

Y1 - 2019/4/24

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

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

KW - Circuits

KW - Constant-time computation

KW - Cryptanalysis

KW - Elliptic curves

KW - Isogenies

KW - Quantum computation

KW - Reversible computation

UR - https://www.scopus.com/pages/publications/85065876632

U2 - 10.1007/978-3-030-17656-3_15

DO - 10.1007/978-3-030-17656-3_15

M3 - Conference contribution

AN - SCOPUS:85065876632

SN - 9783030176556

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

SP - 409

EP - 441

BT - Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings

A2 - Rijmen, Vincent

A2 - Ishai, Yuval

PB - Springer

CY - Cham

Y2 - 19 May 2019 through 23 May 2019

ER -

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

Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies

Cite this