Communications in Cryptology IACR CiC

Optimizations and Practicality of High-Security CSIDH

Authors

Fabio Campos, Jorge Chávez-Saab, Jesús-Javier Chi-Domínguez, Michael Meyer, Krijn Reijnders, Francisco Rodríguez-Henríquez, Peter Schwabe, Thom Wiggers
Fabio Campos ORCID
RheinMain University of Applied Sciences, Wiesbaden, Germany
campos at sopmac dot de
Jorge Chávez-Saab ORCID
Cryptography Research Center, Technology Innovation Institute, Abu Dhabi, United Arab Emirates
jorge dot saab at tii dot ae
Jesús-Javier Chi-Domínguez ORCID
Cryptography Research Center, Technology Innovation Institute, Abu Dhabi, United Arab Emirates
jesus dot dominguez at tii dot ae
Michael Meyer ORCID
University of Regensburg, Regensburg, Germany
michael at random-oracles dot org
Krijn Reijnders ORCID
Radboud University, Nijmegen, The Netherlands
krijn at cs dot ru dot nl
Francisco Rodríguez-Henríquez ORCID
Cryptography Research Center, Technology Innovation Institute, Abu Dhabi, United Arab Emirates
francisco dot rodriguez at tii dot ae
Peter Schwabe ORCID
Max Planck Institute for Security and Privacy, Bochum, Germany
Radboud University, Nijmegen, The Netherlands
peter at cryptojedi dot org
Thom Wiggers ORCID
PQShield, Nijmegen, The Netherlands
thom at thomwiggers dot nl

Abstract

In this work, we assess the real-world practicality of CSIDH, an isogeny-based non-interactive key exchange. We provide the first thorough assessment of the practicality of CSIDH in higher parameter sizes for conservative estimates of quantum security, and with protection against physical attacks.

This requires a three-fold analysis of CSIDH. First, we describe two approaches to efficient high-security CSIDH implementations, based on SQALE and CTIDH. Second, we optimize such high-security implementations, on a high level by improving several subroutines, and on a low level by improving the finite field arithmetic. Third, we benchmark the performance of high-security CSIDH. As a stand-alone primitive, our implementations outperform previous results by a factor up to 2.53×.

As a real-world use case considering network protocols, we use CSIDH in TLS variants that allow early authentication through a NIKE. Although our instantiations of CSIDH have smaller communication requirements than post-quantum KEM and signature schemes, even our highly-optimized implementations result in too-large handshake latency (tens of seconds), showing that CSIDH is only practical in niche cases.

References

[ACR22]
Gora Adj, Jesús-Javier Chi-Domínguez, and Francisco Rodríguez-Henríquez. Karatsuba-based square-root Vélu's formulas applied to two isogeny-based protocols. Journal of Cryptographic Engineering, 2022. https://doi.org/10.1007/s13389-022-00293-y.
Google Scholar ePrint
[AJL17]
Reza Azarderakhsh, David Jao, and Christopher Leonardi. Post-quantum static-static key agreement using multiple protocol instances. In Carlisle Adams and Jan Camenisch, editors, SAC 2017, volume 10719 of LNCS, 45–63. Springer, Heidelberg, 2017. https://doi.org/10.1007/978-3-319-72565-9_3.
Google Scholar ePrint
[Ang+22]
Yawning Angel, Benjamin Dowling, Andreas Hülsing, Peter Schwabe, and Florian Weber. Post quantum noise. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, ACM CCS 2022, 97–109. ACM Press, 2022. https://doi.org/10.1145/3548606.3560577.
Google Scholar ePrint
[Ban+21]
Gustavo Banegas, Daniel J. Bernstein, Fabio Campos, Tung Chou, Tanja Lange, Michael Meyer, Benjamin Smith, and Jana Sotáková. CTIDH: faster constant-time CSIDH. IACR TCHES, 2021(4):351–387, 2021. https://doi.org/10.46586/tches.v2021.i4.351-387.
Google Scholar ePrint
[Ban+23]
Gustavo Banegas, Juliane Krämer, Tanja Lange, Michael Meyer, Lorenz Panny, Krijn Reijnders, Jana Sotáková, and Monika Trimoska. Disorientation faults in CSIDH. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology - EUROCRYPT 2023, volume 14008 of LNCS, 310–342. 2023. https://doi.org/10.1007/978-3-031-30589-4_11.
Google Scholar ePrint
[BD21]
Jean-Claude Bajard and Sylvain Duquesne. Montgomery-friendly primes and applications to cryptography. Journal of Cryptographic Engineering, 11(4):399–415, 2021. https://doi.org/10.1007/s13389-021-00260-z.
Google Scholar ePrint
[Ber+19]
Daniel J. Bernstein, Tanja Lange, Chloe Martindale, and Lorenz Panny. Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part II, volume 11477 of LNCS, 409–441. Springer, Heidelberg, 2019. https://doi.org/10.1007/978-3-030-17656-3_15.
Google Scholar ePrint
[Ber+20]
Daniel J. Bernstein, Luca De Feo, Antonin Leroux, and Benjamin Smith. Faster computation of isogenies of large prime degree. In ANTS XIV – Proceedings of the Fourteenth Algorithmic Number Theory Symposium. MSP, 2020.
Google Scholar ePrint
[BGS22]
Gustavo Banegas, Valerie Gilchrist, and Benjamin Smith. Efficient supersingularity testing over $\mathbb F_p$ and CSIDH key validation. Mathematical Cryptology, 2(1):21–35, Oct. 2022.
Google Scholar ePrint
[Bir23]
Joseph Birr-Pixton. A modern TLS library in Rust. 2023.
Google Scholar ePrint
[BKV19]
Ward Beullens, Thorsten Kleinjung, and Frederik Vercauteren. CSI-FiSh: efficient isogeny based signatures through class group computations. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part I, volume 11921 of LNCS, 227–247. Springer, Heidelberg, 2019. https://doi.org/10.1007/978-3-030-34578-5_9.
Google Scholar ePrint
[Bos+15]
Joppe W. Bos, Craig Costello, Michael Naehrig, and Douglas Stebila. Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. In 2015 IEEE Symposium on Security and Privacy, 553–570. IEEE Computer Society Press, 2015. https://doi.org/10.1109/SP.2015.40.
Google Scholar ePrint
[Bra16]
Matt Braithwaite. Experimenting with post-quantum cryptography. 2016.
Google Scholar ePrint
[Bre+20]
Jacqueline Brendel, Marc Fischlin, Felix Günther, Christian Janson, and Douglas Stebila. Towards post-quantum security for Signal's X3DH handshake. In Orr Dunkelman, Michael J. Jacobson Jr., and Colin O'Flynn, editors, SAC 2020, volume 12804 of LNCS, 404–430. Springer, Heidelberg, 2020. https://doi.org/10.1007/978-3-030-81652-0_16.
Google Scholar ePrint
[BS20]
Xavier Bonnetain and André Schrottenloher. Quantum security analysis of CSIDH. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part II, volume 12106 of LNCS, 493–522. Springer, Heidelberg, 2020. https://doi.org/10.1007/978-3-030-45724-2_17.
Google Scholar ePrint
[Cam+20]
Fabio Campos, Matthias J. Kannwischer, Michael Meyer, Hiroshi Onuki, and Marc Stöttinger. Trouble at the CSIDH: protecting CSIDH with dummy-operations against fault injection attacks. In 2020 Workshop on Fault Detection and Tolerance in Cryptography (FDTC), 57–65. IEEE, 2020. https://doi.org/10.1109/FDTC51366.2020.00015.
Google Scholar ePrint
[Cam+22]
Fabio Campos, Michael Meyer, Krijn Reijnders, and Marc Stöttinger. Patient zero and patient six: zero-value and correlation attacks on CSIDH and SIKE. 2022.
Google Scholar ePrint
[Cas+18]
Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes. CSIDH: an efficient post-quantum commutative group action. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part III, volume 11274 of LNCS, 395–427. Springer, Heidelberg, 2018. https://doi.org/10.1007/978-3-030-03332-3_15.
Google Scholar ePrint
[Cas+22]
Wouter Castryck, Thomas Decru, Marc Houben, and Frederik Vercauteren. Horizontal racewalking using radical isogenies. In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part II, volume 13792 of LNCS, 67–96. Springer, Heidelberg, 2022. https://doi.org/10.1007/978-3-031-22966-4_3.
Google Scholar ePrint
[CD20]
Wouter Castryck and Thomas Decru. CSIDH on the surface. In Jintai Ding and Jean-Pierre Tillich, editors, Post-Quantum Cryptography - 11th International Conference, PQCrypto 2020, 111–129. Springer, Heidelberg, 2020. https://doi.org/10.1007/978-3-030-44223-1_7.
Google Scholar ePrint
[CD23]
Wouter Castryck and Thomas Decru. An efficient key recovery attack on SIDH. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part V, volume 14008 of LNCS, 423–447. Springer, Heidelberg, 2023. https://doi.org/10.1007/978-3-031-30589-4_15.
Google Scholar ePrint
[CDV20]
Wouter Castryck, Thomas Decru, and Frederik Vercauteren. Radical isogenies. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part II, volume 12492 of LNCS, 493–519. Springer, Heidelberg, 2020. https://doi.org/10.1007/978-3-030-64834-3_17.
Google Scholar ePrint
[Cer+19]
Daniel Cervantes-Vázquez, Mathilde Chenu, Jesús-Javier Chi-Domínguez, Luca De Feo, Francisco Rodríguez-Henríquez, and Benjamin Smith. Stronger and faster side-channel protections for CSIDH. In Peter Schwabe and Nicolas Thériault, editors, LATINCRYPT 2019, volume 11774 of LNCS, 173–193. Springer, Heidelberg, 2019. https://doi.org/10.1007/978-3-030-30530-7_9.
Google Scholar ePrint
[Chá+22]
Jorge Chávez-Saab, Jesús-Javier Chi-Domínguez, Samuel Jaques, and Francisco Rodríguez-Henríquez. Journal of cryptographic engineering. Journal of Cryptographic Engineering, 12(3):349–368, 2022. https://doi.org/10.1007/s13389-021-00271-w.
Google Scholar ePrint
[CLN16]
Craig Costello, Patrick Longa, and Michael Naehrig. Efficient algorithms for supersingular isogeny Diffie-Hellman. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part I, volume 9814 of LNCS, 572–601. Springer, Heidelberg, 2016. https://doi.org/10.1007/978-3-662-53018-4_21.
Google Scholar ePrint
[Cos+17]
Craig Costello, David Jao, Patrick Longa, Michael Naehrig, Joost Renes, and David Urbanik. Efficient compression of SIDH public keys. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part I, volume 10210 of LNCS, 679–706. Springer, Heidelberg, 2017. https://doi.org/10.1007/978-3-319-56620-7_24.
Google Scholar ePrint
[CR22]
Jesús-Javier Chi-Domínguez and Krijn Reijnders. Fully projective radical isogenies in constant-time. In Steven D. Galbraith, editor, CT-RSA 2022, volume 13161 of LNCS, 73–95. Springer, Heidelberg, 2022. https://doi.org/10.1007/978-3-030-95312-6_4.
Google Scholar ePrint
[CR22]
Jesús-Javier Chi-Domínguez and Francisco Rodríguez-Henríquez. Optimal strategies for CSIDH. Adv. Math. Commun., 16(2):383–411, 2022. https://doi.org/10.3934/amc.2020116.
Google Scholar ePrint
[dKoc18]
Bor de Kock. A non-interactive key exchange based on ring-learning with errors. 2018.
Google Scholar ePrint
[Dol18]
Javad Doliskani. On division polynomial pit and supersingularity. Applicable Algebra in Engineering, Communication and Computing, 29(5):393–407, 2018. https://doi.org/10.1007/S00200-018-0349-Z.
Google Scholar ePrint
[Gaj+24]
Phillip Gajland, Bor de Kock, Miguel Quaresma, Giulio Malavolta, and Peter Schwabe. Swoosh: practical lattice-based non-interactive key exchange. In Proceedings of the 33rd USENIX Security Symposium, to appear. USENIX Association, 2024.
Google Scholar ePrint
[Gal+16]
Steven D. Galbraith, Christophe Petit, Barak Shani, and Yan Bo Ti. On the security of supersingular isogeny cryptosystems. In Jung Hee Cheon and Tsuyoshi Takagi, editors, ASIACRYPT 2016, Part I, volume 10031 of LNCS, 63–91. Springer, Heidelberg, 2016. https://doi.org/10.1007/978-3-662-53887-6_3.
Google Scholar ePrint
[GW22]
Ruben Gonzalez and Thom Wiggers. Kemtls vs. post-quantum tls: performance on embedded systems. In Lejla Batina, Stjepan Picek, and Mainack Mondal, editors, Security, Privacy, and Applied Cryptography Engineering, 99–117. Springer Nature Switzerland, 2022. https://doi.org/10.1007/978-3-031-22829-2.
Google Scholar ePrint
[Ham21]
Mike Hamburg. Computing the jacobi symbol using bernstein-yang. 2021.
Google Scholar ePrint
[Hut+20]
Aaron Hutchinson, Jason T. LeGrow, Brian Koziel, and Reza Azarderakhsh. Further optimizations of CSIDH: A systematic approach to efficient strategies, permutations, and bound vectors. In Mauro Conti, Jianying Zhou, Emiliano Casalicchio, and Angelo Spognardi, editors, ACNS 20, Part I, volume 12146 of LNCS, 481–501. Springer, Heidelberg, 2020. https://doi.org/10.1007/978-3-030-57808-4_24.
Google Scholar ePrint
[JD11]
David Jao and Luca De Feo. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In Bo-Yin Yang, editor, Post-Quantum Cryptography - 4th International Workshop, PQCrypto 2011, 19–34. Springer, Heidelberg, 2011. https://doi.org/10.1007/978-3-642-25405-5_2.
Google Scholar ePrint
[KO63]
Anatolii Karatsuba and Yuri Ofman. Multiplication of multidigit numbers on automata. Soviet Physics Doklady, 7:595–596, 1963.
Google Scholar ePrint
[Kuh18]
Wouter Kuhnen. OPTLS revisited. Master's thesis, Radboud University, 2018.
Google Scholar ePrint
[Kup13]
Greg Kuperberg. Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In Simone Severini and Fernando G. S. L. Brandão, editors, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, volume 22 of LIPIcs 22, 20–34. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2013. https://doi.org/10.4230/LIPIcs.TQC.2013.20.
Google Scholar ePrint
[KV19]
Kris Kwiatkowski and Luke Valenta. The TLS post-quantum experiment. 2019.
Google Scholar ePrint
[KW16]
Hugo Krawczyk and Hoeteck Wee. The OPTLS protocol and TLS 1.3. In 2016 IEEE European Symposium on Security and Privacy (EuroS&P), 81–96. IEEE, 2016. https://doi.org/10.1109/EuroSP.2016.18.
Google Scholar ePrint
[Lan18]
Adam Langley. CECPQ2. 2018.
Google Scholar ePrint
[LH20]
Jason LeGrow and Aaron Hutchinson. An analysis of fault attacks on CSIDH. 2020.
Google Scholar ePrint
[LKP13]
Younho Lee, Il-Hee Kim, and Yongsu Park. Improved multi-precision squaring for low-end RISC microcontrollers. J. Syst. Softw., 86(1):60–71, 2013. https://doi.org/10.1016/j.jss.2012.06.074.
Google Scholar ePrint
[Lon23]
Patrick Longa. IACR trans. cryptogr. hardw. embed. syst. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2023(3):445–472, 2023. https://doi.org/10.46586/tches.v2023.i3.445-472.
Google Scholar ePrint
[Lyu+22]
Vadim Lyubashevsky, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Peter Schwabe, Gregor Seiler, Damien Stehlé, and Shi Bai. CRYSTALS-DILITHIUM. 2022.
Google Scholar ePrint
[Lyu17]
Vadim Lyubashevsky. Converting newhope/lwe key exchange to a diffe-hellman-like algorithm. 2017.
Google Scholar ePrint
[Mai+23]
Luciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope, and Benjamin Wesolowski. A direct key recovery attack on SIDH. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part V, volume 14008 of LNCS, 448–471. Springer, Heidelberg, 2023. https://doi.org/10.1007/978-3-031-30589-4_16.
Google Scholar ePrint
[MCR19]
Michael Meyer, Fabio Campos, and Steffen Reith. On lions and elligators: an efficient constant-time implementation of CSIDH. In Jintai Ding and Rainer Steinwandt, editors, Post-Quantum Cryptography - 10th International Conference, PQCrypto 2019, 307–325. Springer, Heidelberg, 2019. https://doi.org/10.1007/978-3-030-25510-7_17.
Google Scholar ePrint
[MOT20]
Tomoki Moriya, Hiroshi Onuki, and Tsuyoshi Takagi. How to construct CSIDH on Edwards curves. In Stanislaw Jarecki, editor, CT-RSA 2020, volume 12006 of LNCS, 512–537. Springer, Heidelberg, 2020. https://doi.org/10.1007/978-3-030-40186-3_22.
Google Scholar ePrint
[MP16]
Moxie Marlinspike and Trevor Perrin. The X3DH key agreement protocol. 2016.
Google Scholar ePrint
[MR18]
Michael Meyer and Steffen Reith. A faster way to the CSIDH. In Debrup Chakraborty and Tetsu Iwata, editors, INDOCRYPT 2018, volume 11356 of LNCS, 137–152. Springer, Heidelberg, 2018. https://doi.org/10.1007/978-3-030-05378-9_8.
Google Scholar ePrint
[Nat17]
National Institute of Standards and Technology. Post-quantum cryptography standardization. 2017.
Google Scholar ePrint
[Nat23]
National Institute of Standards and Technology. Security requirements for cryptographic modules. 2023. https://doi.org/10.6028/NIST.FIPS.203.ipd.
Google Scholar ePrint
[Onu+19]
Hiroshi Onuki, Yusuke Aikawa, Tsutomu Yamazaki, and Tsuyoshi Takagi. (Short paper) A faster constant-time algorithm of CSIDH keeping two points. In Nuttapong Attrapadung and Takeshi Yagi, editors, IWSEC 19, volume 11689 of LNCS, 23–33. Springer, Heidelberg, 2019. https://doi.org/10.1007/978-3-030-26834-3_2.
Google Scholar ePrint
[Pei20]
Chris Peikert. He gives C-sieves on the CSIDH. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part II, volume 12106 of LNCS, 463–492. Springer, Heidelberg, 2020. https://doi.org/10.1007/978-3-030-45724-2_16.
Google Scholar ePrint
[Pre+22]
Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei Zhang. FALCON. 2022.
Google Scholar ePrint
[Res18]
Eric Rescorla. The transport layer security (TLS) protocol version 1.3. 2018.
Google Scholar ePrint
[Rob23]
Damien Robert. Breaking SIDH in polynomial time. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part V, volume 14008 of LNCS, 472–503. Springer, Heidelberg, 2023. https://doi.org/10.1007/978-3-031-30589-4_17.
Google Scholar ePrint
[RSW20]
Eric Rescorla, Nick Sullivan, and Christopher A. Wood. Semi-Static Diffie-Hellman Key Establishment for TLS 1.3. 2020.
Google Scholar ePrint
[SSW20]
Peter Schwabe, Douglas Stebila, and Thom Wiggers. Post-quantum TLS without handshake signatures. In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, editors, ACM CCS 2020, 1461–1480. ACM Press, 2020. https://doi.org/10.1145/3372297.3423350.
Google Scholar ePrint
[SSW21]
Peter Schwabe, Douglas Stebila, and Thom Wiggers. More efficient post-quantum KEMTLS with pre-distributed public keys. In Elisa Bertino, Haya Shulman, and Michael Waidner, editors, ESORICS 2021, Part I, volume 12972 of LNCS, 3–22. Springer, Heidelberg, 2021. https://doi.org/10.1007/978-3-030-88418-5_1.
Google Scholar ePrint
[Vél71]
Jacques Vélu. Isogénies entre courbes elliptiques. Comptes Rendus de l'Académie des Sciences de Paris, Séries A, 273:238–241, 1971.
Google Scholar ePrint
[vW99]
Paul C. van Oorschot and Michael J. Wiener. Parallel collision search with cryptanalytic applications. Journal of Cryptology, 12(1):1–28, 1999. https://doi.org/10.1007/PL00003816.
Google Scholar ePrint
[WR22]
Bas Westerbaan and Cefan Daniel Rubin. Defending against future threats: Cloudflare goes post-quantum. 2022.
Google Scholar ePrint

PDFPDF Open access

DOI: https://doi.org/10.62056/anjbksdja
History
Submitted: 2024-01-09
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Fabio Campos, Jorge Chávez-Saab, Jesús-Javier Chi-Domínguez, Michael Meyer, Krijn Reijnders, Francisco Rodríguez-Henríquez, Peter Schwabe, and Thom Wiggers, Optimizations and Practicality of High-Security CSIDH. IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/anjbksdja.

Citations

There are at least 2 citations.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.