Cryptology ePrint Archive: Report 2018/1059

Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies

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

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.

Category / Keywords: public-key cryptography / Elliptic curves, isogenies, circuits, constant-time computation, reversible computation, quantum computation, cryptanalysis

Original Publication (with major differences): IACR-EUROCRYPT-2019

Date: received 31 Oct 2018, last revised 5 Mar 2019

Contact author: authorcontact-qisog at box cr yp to

Available format(s): PDF | BibTeX Citation

Version: 20190305:153316 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]