Paper 2018/1059

Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies

Daniel J. Bernstein, Tanja Lange, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2019
Keywords
Elliptic curvesisogeniescircuitsconstant-time computationreversible computationquantum computationcryptanalysis
Contact author(s)
authorcontact-qisog @ box cr yp to
History
2019-03-05: revised
2018-11-02: received
See all versions
Short URL
https://ia.cr/2018/1059
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1059,
      author = {Daniel J.  Bernstein and Tanja Lange and Chloe Martindale and Lorenz Panny},
      title = {Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1059},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1059}},
      url = {https://eprint.iacr.org/2018/1059}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.