Finding Practical Parameters for   Isogeny-based Cryptography

Maria Corte-Real Santos; Jonathan Komada Eriksen; Michael Meyer; Francisco Rodríguez-Henríquez

doi:10.62056/ayojbhey6b

Finding Practical Parameters for Isogeny-based Cryptography

Authors

Maria Corte-Real Santos, Jonathan Komada Eriksen, Michael Meyer, Francisco Rodríguez-Henríquez

Maria Corte-Real Santos

University College London, London, UK
maria dot santos dot 20 at ucl dot ac dot uk

Jonathan Komada Eriksen

Norwegian University of Science and Technology, Trondheim, Norway
jonathan dot k dot eriksen at ntnu dot no

Michael Meyer

University of Regensburg, Regensburg, Germany
michael at random-oracles dot org

Francisco Rodríguez-Henríquez

Cryptography Research Center, Technology Innovation Institute, Abu Dhabi, United Arab Emirates
francisco dot rodriguez at tii dot ae

Keywords: Post-quantum cryptography isogenies parameter search SQIsign AprèsSQI POKE

Abstract

Isogeny-based schemes often come with special requirements on the field of definition of the involved elliptic curves. For instance, the efficiency of SQIsign, a promising candidate in the NIST signature standardisation process, requires a large power of two and a large smooth integer $T$ to divide $p^{2} - 1$ for its prime parameter $p$ . We present two new methods that combine previous techniques for finding suitable primes: sieve-and-boost and XGCD-and-boost. We use these methods to find primes for the NIST submission of SQIsign. Furthermore, we show that our methods are flexible and can be adapted to find suitable parameters for other isogeny-based schemes such as AprèsSQI or POKE. For all three schemes, the parameters we present offer the best performance among all parameters proposed in the literature.

References

[AAA⁺24a]

Marius A. Aardal, Gora Adj, Arwa Alblooshi, Diego Aranha, Isaac A. Canales-Martínez, Jorge Chávez-Saab, Décio Luiz Gazzoni Filho, Krijn Reijnders, and Francisco Rodríguez-Henríquez. Optimized SQIsign 1D verification on Intel and Cortex-M4. Personal communication, manuscript in preparation. 2024.

Google Scholar ePrint

[AAA⁺24b]

Marius A. Aardal, Gora Adj, Arwa Alblooshi, Diego Aranha, Isaac A. Canales-Martínez, Jorge Chávez-Saab, Décio Luiz Gazzoni Filho, Krijn Reijnders, and Francisco Rodríguez-Henríquez. Scoring primes for computing isogenies in extension fields. Available at: http://delta.cs.cinvestav.mx/ francisco/codigo.html. 2024.

Google Scholar ePrint

[Bas24]

Andrea Basso. POKE: A Framework for Efficient PKEs, Split KEMs, and OPRFs from Higher-dimensional Isogenies. Cryptology ePrint Archive, Paper 2024/624. 2024.

Google Scholar ePrint

[BBC⁺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://tches.iacr.org/index.php/TCHES/article/view/9069 DOI: 10.46586/tches.v2021.i4.351-387

Google Scholar ePrint

[BCC⁺23]

Giacomo Bruno, Maria Corte-Real Santos, Craig Costello, Jonathan Komada Eriksen, Michael Meyer, Michael Naehrig, and Bruno Sterner. Cryptographic Smooth Neighbors. In Jian Guo and Ron Steinfeld, editors, ASIACRYPT 2023, Part VII, volume 14444 of LNCS, pages 190–221. December 2023. Springer, Singapore. DOI: 10.1007/978-981-99-8739-9_7

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, November 2021. DOI: 10.1007/s13389-021-00260-z

Google Scholar ePrint

[BDD⁺24]

Andrea Basso, Luca De Feo, Pierrick Dartois, Antonin Leroux, Luciano Maino, Giacomo Pope, Damien Robert, and Benjamin Wesolowski. SQIsign2D-West: The Fast, the Small, and the Safer. Cryptology ePrint Archive, Paper 2024/760. 2024.

Google Scholar ePrint

[BDLS20]

Daniel J Bernstein, Luca De Feo, Antonin Leroux, and Benjamin Smith. Faster computation of isogenies of large prime degree. Open Book Series, 4(1):39–55, 2020. DOI: 10.2140/obs.2020.4.39

Google Scholar ePrint

[Ber04]

Daniel J. Bernstein. How to find smooth parts of integers. http://cr.yp.to/papers.html#smoothparts. 2004.

Google Scholar ePrint

[BHL⁺22]

Jan Buzek, Junaid Hasan, Jason Liu, Michael Naehrig, and Anthony Vigil. Finding twin smooth integers by solving Pell equations. CoRR, abs/2211.04315, 2022. DOI: 10.48550/ARXIV.2211.04315

Google Scholar ePrint

[BS07]

William D. Banks and Igor E. Shparlinski. Integers with a large smooth divisor. Integers. Electronic Journal of Combinatorial Number Theory, 7:A17, 11, 2007. DOI: 10.5281/zenodo.8281131

Google Scholar ePrint

[CCC⁺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, pages 173–193. October 2019. Springer, Cham. DOI: 10.1007/978-3-030-30530-7_9

Google Scholar ePrint

[CCC⁺24]

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, 1(1), 2024. DOI: 10.62056/ANJBKSDJA

Google Scholar ePrint

[CCD⁺23]

Jorge Chavez-Saab, Maria Corte-Real Santos, Luca De Feo, Jonathan Komada Eriksen, Basil Hess, David Kohel, Antonin Leroux, Patrick Longa, Michael Meyer, Lorenz Panny, Sikhar Patranabis, Christophe Petit, Francisco Rodríguez-Henríquez, Sina Schaeffler, and Benjamin Wesolowski. SQIsign: Algorithm specifications and supporting documentation. National Institute of Standards and Technology. 2023.

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, pages 423–447. April 2023. Springer, Cham. DOI: 10.1007/978-3-031-30589-4_15

Google Scholar ePrint

[CEMR24]

Maria Corte-Real Santos, Jonathan Komada Eriksen, Michael Meyer, and Krijn Reijnders. AprèsSQI: Extra Fast Verification for SQIsign Using Extension-Field Signing. In Marc Joye and Gregor Leander, editors, Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part I, volume 14651 of Lecture Notes in Computer Science, pages 63–93. 2024. Springer. DOI: 10.1007/978-3-031-58716-0_3

Google Scholar ePrint

[Cen18]

Murat Cenk. Karatsuba-like formulae and their associated techniques. Journal of Cryptographic Engineering, 8(3):259–269, September 2018. DOI: 10.1007/s13389-017-0155-8

Google Scholar ePrint

[CHM13]

Brian Conrey, Mark Holmstrom, and Tara McLaughlin. Smooth neighbors. Experimental Mathematics, 22(2):195–202, 2013. DOI: 10.1080/10586458.2013.768483

Google Scholar ePrint

[CMN21]

Craig Costello, Michael Meyer, and Michael Naehrig. Sieving for Twin Smooth Integers with Solutions to the Prouhet-Tarry-Escott Problem. In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part I, volume 12696 of LNCS, pages 272–301. October 2021. Springer, Cham. DOI: 10.1007/978-3-030-77870-5_10

Google Scholar ePrint

[Cos20]

Craig Costello. B-SIDH: Supersingular Isogeny Diffie-Hellman Using Twisted Torsion. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part II, volume 12492 of LNCS, pages 440–463. December 2020. Springer, Cham. DOI: 10.1007/978-3-030-64834-3_15

Google Scholar ePrint

[dB66]

Nicolaas G. de Bruijn. On the number of positive integers

\leq

x and free of prime factors

> y

, II. Indag. Math, 38:239–247, 1966. DOI: 10.1016/S1385-7258(66)50029-4

Google Scholar ePrint

[DF24]

Max Duparc and Tako Boris Fouotsa. SQIPrime: A dimension 2 variant of SQISignHD with non-smooth challenge isogenies. Cryptology ePrint Archive, Paper 2024/773. 2024.

Google Scholar ePrint

[Dic30]

Karl Dickman. On the frequency of numbers containing prime factors of a certain relative magnitude. Arkiv for matematik, astronomi och fysik, 22(10):A–10, 1930.

Google Scholar ePrint

[DKL⁺20]

Luca De Feo, David Kohel, Antonin Leroux, Christophe Petit, and Benjamin Wesolowski. SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part I, volume 12491 of LNCS, pages 64–93. December 2020. Springer, Cham. DOI: 10.1007/978-3-030-64837-4_3

Google Scholar ePrint

[DLLW23]

Luca De Feo, Antonin Leroux, Patrick Longa, and Benjamin Wesolowski. New Algorithms for the Deuring Correspondence - Towards Practical and Secure SQISign Signatures. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part V, volume 14008 of LNCS, pages 659–690. April 2023. Springer, Cham. DOI: 10.1007/978-3-031-30589-4_23

Google Scholar ePrint

[DLRW24]

Pierrick Dartois, Antonin Leroux, Damien Robert, and Benjamin Wesolowski. SQIsignHD: New Dimensions in Cryptography. In Marc Joye and Gregor Leander, editors, Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part I, volume 14651 of Lecture Notes in Computer Science, pages 3–32. 2024. Springer. DOI: 10.1007/978-3-031-58716-0_1

Google Scholar ePrint

[EPSV24]

Jonathan Komada Eriksen, Lorenz Panny, Jana Sotáková, and Mattia Veroni. Deuring for the People: Supersingular elliptic curves with prescribed endomorphism ring in general characteristic. In LuCaNT: LMFDB, computation, and number theory, volume 796 of Contemporary Mathematics, pages 339–373. Amer. Math. Soc., Providence, RI 2024. DOI: 10.1090/conm/796/16008

Google Scholar ePrint

[Leh64]

Derrick H. Lehmer. On a problem of Störmer. Illinois Journal of Mathematics, 8(1):57–79, 1964. DOI: 10.1215/ijm/1256067456

Google Scholar ePrint

[MMP⁺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, pages 448–471. April 2023. Springer, Cham. DOI: 10.1007/978-3-031-30589-4_16

Google Scholar ePrint

[Mon05]

Peter L. Montgomery. Five, Six, and Seven-Term Karatsuba-Like Formulae. IEEE Trans. Computers, 54(3):362–369, 2005. DOI: 10.1109/TC.2005.49

Google Scholar ePrint

[{NIS}23]

NIST. Post-quantum cryptography: Digital signature schemes, 2023. Available at: https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures. Personal communication. 2023.

Google Scholar ePrint

[NO24]

Kohei Nakagawa and Hiroshi Onuki. SQIsign2D-East: A New Signature Scheme Using 2-dimensional Isogenies. Cryptology ePrint Archive, Paper 2024/771. 2024.

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, pages 472–503. April 2023. Springer, Cham. DOI: 10.1007/978-3-031-30589-4_17

Google Scholar ePrint

[Ste23]

Bruno Sterner. Towards Optimally Small Smoothness Bounds for Cryptographic-Sized Twin Smooth Integers and their Isogeny-based Applications. Cryptology ePrint Archive, Paper 2023/1576. 2023.

Google Scholar ePrint

[St{\o }97]

Carl Størmer. Quelques théorèmes sur l'équation de Pell

x^{2} - D y^{2} = \pm 1

et leurs applications. Christiania Videnskabens Selskabs Skrifter, Math. Nat. Kl, 1897. DOI: 10.1215/ijm/1256067456

Google Scholar ePrint

[V{\'e}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

PDF Open access

DOI: https://doi.org/10.62056/ayojbhey6b

History

Submitted: 2024-07-09
Accepted: 2024-09-02
Published: 2024-10-07

How to cite

Maria Corte-Real Santos, Jonathan Komada Eriksen, Michael Meyer, and Francisco Rodríguez-Henríquez, Finding Practical Parameters for Isogeny-based Cryptography. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/ayojbhey6b.

License

Copyright is held by the author(s)

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

@article{10.62056/ayojbhey6b,
         author={Maria Corte-Real Santos and Jonathan Komada Eriksen and Michael Meyer and Francisco Rodríguez-Henríquez},
         title={Finding Practical Parameters for   Isogeny-based Cryptography},
         volume={1},
         number={3},
         year={2024},
         date={2024-10-07},
         issn={3006-5496},
         doi={10.62056/ayojbhey6b},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Maria Corte-Real Santos
AU  - Jonathan Komada Eriksen
AU  - Michael Meyer
AU  - Francisco Rodríguez-Henríquez
PY  - 2024
TI  - Finding Practical Parameters for   Isogeny-based Cryptography
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 3
DO  - 10.62056/ayojbhey6b
UR  - https://doi.org/10.62056/ayojbhey6b
AB  - <p>        Isogeny-based schemes often come with special requirements on         the field of definition of the involved elliptic curves.         For instance, the efficiency of SQIsign, a promising candidate in the NIST         signature standardisation process,         requires a large power of two and a large smooth integer $T$ to         divide $p^2-1$ for its prime parameter $p$.                  We present two new methods that combine previous techniques for finding         suitable primes: sieve-and-boost and XGCD-and-boost.         We use these methods to find primes for the NIST submission of SQIsign.         Furthermore, we show that our methods are flexible and can be adapted         to find suitable parameters for other isogeny-based schemes such as         AprèsSQI or POKE.         For all three schemes, the parameters we present offer the best performance         among all parameters proposed in the literature. </p>
ER  -

Maria Corte-Real Santos, Jonathan Komada Eriksen, Michael Meyer, and Francisco Rodríguez-Henríquez, Finding Practical Parameters for Isogeny-based Cryptography. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/ayojbhey6b.