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

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 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	Germany
City	Darmstadt
Period	19/05/19 → 23/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

Bernstein, Daniel J. ; Lange, Tanja ; Martindale, Chloe ; Panny, Lorenz. / 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 = "4",

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

}

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 ; Panny, Lorenz.

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 - optimizing quantum evaluation of isogenies

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 - http://www.scopus.com/inward/record.url?scp=85065876632&partnerID=8YFLogxK

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

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

Access to Document

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

Cryptology ePrint Archive versionFinal author version , 777 KB

Research Output