The CTIDH key space is a new key space for CSIDH, and the CTIDH algorithm is 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; CTIDH uses 438006 multiplications and 125.53 million cycles.
Contributors (alphabetical order)
- 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, and 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’École Polytechnique, Institut Polytechnique de Paris, Palaiseau, France)
- Jana Sotáková (Institute for Logic, Language and Computation, University of Amsterdam, The Netherlands; QuSoft)
Acknowledgments
This work began at the online Lorentz Center workshop "Post-Quantum Cryptography for Embedded Systems". This work was carried out while the second and fifth authors were visiting Academia Sinica. This work was funded in part by
- the European Commission through H2020 SPARTA,
- the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's Excellence Strategy—EXC 2092 CASA—390781972 "Cyber Security in the Age of Large-Scale Adversaries",
- the Cisco University Research Program,
- the U.S. National Science Foundation under grant 2037867,
- the Taiwan’s Executive Yuan Data Safety and Talent Cultivation Project (AS-KPQ-109-DSTCP),
- Continental AG and Elektrobit Automotive GmbH,
- Taiwan Ministry of Science and Technology (MoST) grant MOST105-2221-E-001-014-MY3, 108-2221-E-001-008 and 109-2222-E-001-001-MY3,
- Academia Sinica Investigator Award AS-IA-104-M01,
- the Netherlands Organisation for Scientific Research (NWO) under grant 628.001.028 (FASOR),
- the German Federal Ministry of Education and Research and the Hessian Ministry of Higher Education, Research, Science and the Arts within their joint support of the National Research Center for Applied Cybersecurity ATHENE,
- the French Agence Nationale de la Recherche through ANR CIAO (ANR-19-CE48-0008), and
- the Dutch Research Council (NWO) through Gravitation-grant Quantum Software Consortium - 024.003.037.
"Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation" (or other funding agencies).
Version: This is version 2021.05.21 of the "Intro" web page.