International Association for Cryptologic Research

International Association
for Cryptologic Research

Transactions on Cryptographic Hardware and Embedded Systems, Volume 2021

CTIDH: faster constant-time CSIDH


Gustavo Banegas
Inria and Laboratoire d’Informatique de l’Ecole polytechnique, Institut Polytechnique de Paris, Palaiseau, France

Daniel J. Bernstein
Department of Computer Science, University of Illinois at Chicago, USA; Horst Görtz Institute for IT Security, Ruhr University Bochum, Germany

Fabio Campos
Max Planck Institute for Security and Privacy, Bochum, Germany

Tung Chou
Academia Sinica, Taipei, Taiwan

Tanja Lange
Eindhoven University of Technology, Eindhoven, The Netherlands

Michael Meyer
Technical University of Darmstadt, Darmstadt, Germany

Benjamin Smith
Inria and Laboratoire d’Informatique de l’Ecole polytechnique, Institut Polytechnique de Paris, Palaiseau, France

Jana Sotáková
Institute for Logic, Language and Computation, University of Amsterdam, The Netherlands; QuSoft


Keywords: post-quantum cryptography, non-interactive key exchange, small keys, isogeny-based cryptography, CSIDH, constant-time algorithms


Abstract

This paper introduces a new key space for CSIDH and a new algorithm for constant-time evaluation of the CSIDH group action. The key space is not useful with previous algorithms, and the algorithm is not useful with previous key spaces, but combining the new key space with the new algorithm produces speed records for constant-time CSIDH. For example, for CSIDH-512 with a 256-bit key space, the best previous constant-time results used 789000 multiplications and more than 200 million Skylake cycles; this paper uses 438006 multiplications and 125.53 million cycles.

Publication

Transactions of Cryptographic Hardware and Embedded Systems, Volume 2021, Issue 4

Paper

Artifact

Artifact number
tches/2021/a20

Artifact published
September 13, 2021

README

tar.gz (201 KB)  

License


BibTeX How to cite

Banegas, G., Bernstein, D. J., Campos, F., Chou, T., Lange, T., Meyer, M., Smith, B., & Sotáková, J. (2021). CTIDH: faster constant-time CSIDH. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021(4), 351–387. https://doi.org/10.46586/tches.v2021.i4.351-387. Artifact at https://artifacts.iacr.org/tches/2021/a20.