Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)

Uittreksel

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.

TaalEngels
TitelAdvances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
RedacteurenYuval Ishai, Vincent Rijmen
Plaats van productieCham
UitgeverijSpringer
Pagina's409-441
Aantal pagina's33
ISBN van geprinte versie9783030176556
DOI's
StatusGepubliceerd - 24 apr 2019
Evenement38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019 - Darmstadt, Duitsland
Duur: 19 mei 201923 mei 2019

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11477 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019
LandDuitsland
StadDarmstadt
Periode19/05/1923/05/19

Vingerafdruk

Isogenies
Quantum Circuits
Query
Networks (circuits)
Evaluation
Costs
Attack
Isogeny
Key Exchange
Computer Simulation
Concretes
Computer simulation

Trefwoorden

    Citeer dit

    Bernstein, D. J., Lange, T., Martindale, C., & Panny, L. (2019). Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies. In Y. Ishai, & V. Rijmen (editors), Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (blz. 409-441). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11477 LNCS). Cham: Springer. DOI: 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. redacteur / Yuval Ishai ; Vincent Rijmen. Cham : Springer, 2019. blz. 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 = "Yuval Ishai and Vincent Rijmen",
    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 Y Ishai & V Rijmen (redactie), 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, blz. 409-441, Darmstadt, Duitsland, 19/05/19. DOI: 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. redactie / Yuval Ishai; Vincent Rijmen. Cham : Springer, 2019. blz. 409-441 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11477 LNCS).

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer 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

    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

    PB - Springer

    CY - Cham

    ER -

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