Communications in Cryptology IACR CiC

Computing 2-isogenies between Kummer lines

Authors

Damien Robert, Nicolas Sarkis
Damien Robert ORCID
Univ. Bordeaux, CNRS, INRIA, Bordeaux INP, Talence, France
damien dot robert at inria dot fr
Nicolas Sarkis ORCID
Univ. Bordeaux, CNRS, INRIA, Bordeaux INP, Talence, France
nicolas dot sarkis at math dot u-bordeaux dot fr
Keywords: Elliptic curve cryptography Kummer lines Isogenies Scalar multiplication Montgomery ladder

Abstract

We use theta groups to study $2$-isogenies between Kummer lines, with a particular focus on the Montgomery model. This allows us to recover known formulas, along with more efficient forms for translated isogenies, which require only $2S+2m_0$ for evaluation. We leverage these translated isogenies to build a hybrid ladder for scalar multiplication on Montgomery curves with rational $2$-torsion, which cost $3M+6S+2m_0$ per bit, compared to $5M+4S+1m_0$ for the standard Montgomery ladder.

References

[Ber+08]
Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters. Twisted edwards curves. In Serge Vaudenay, editor, Progress in Cryptology - AFRICACRYPT 2008, First International Conference on Cryptology in Africa, Casablanca, Morocco, June 11-14, 2008. Proceedings, volume 5023 of Lecture Notes in Computer Science, 389–405. Springer, 2008. https://doi.org/10.1007/978-3-540-68164-9_26.
Google Scholar ePrint
[CH17]
Craig Costello and Hüseyin Hisil. A simple and compact algorithm for SIDH with arbitrary degree isogenies. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part II, volume 10625 of LNCS, 303–329. December 2017. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-70697-9_11.
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. August 2016. Springer, Heidelberg. https://doi.org/10.1007/978-3-662-53018-4_21.
Google Scholar ePrint
[DIK06]
Christophe Doche, Thomas Icart, and David R. Kohel. Efficient scalar multiplication by isogeny decompositions. In Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, and Tal Malkin, editors, PKC 2006, volume 3958 of LNCS, 191–206. April 2006. Springer, Heidelberg. https://doi.org/10.1007/11745853_13.
Google Scholar ePrint
[FJP14]
Luca De Feo, David Jao, and Jérôme Plût. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. J. Math. Cryptol., 8(3):209–247, 2014. https://doi.org/10.1515/JMC-2012-0015.
Google Scholar ePrint
[GL09]
Pierrick Gaudry and David Lubicz. The arithmetic of characteristic 2 kummer surfaces and of elliptic kummer lines. Finite Fields Their Appl., 15(2):246–260, 2009. https://doi.org/10.1016/J.FFA.2008.12.006.
Google Scholar ePrint
[HR19]
Hüseyin Hisil and Joost Renes. On kummer lines with full rational 2-torsion and their usage in cryptography. ACM Trans. Math. Softw., 45(4):39:1–39:17, 2019. https://doi.org/10.1145/3361680.
Google Scholar ePrint
[KS20]
Sabyasachi Karati and Palash Sarkar. Kummer for genus one over prime-order fields. Journal of Cryptology, 33(1):92–129, January 2020. https://doi.org/10.1007/s00145-019-09320-4.
Google Scholar ePrint
[Mon87]
Peter L. Montgomery. Speeding the Pollard and elliptic curve methods of factorization. Mathematics of Computation, 48:243–264, 1987. https://doi.org/10.2307/2007888.
Google Scholar ePrint
[Mor+22]
Tomoki Moriya, Hiroshi Onuki, Yusuke Aikawa, and Tsuyoshi Takagi. The generalized montgomery coordinate: A new computational tool for isogeny-based cryptography. 2022.
Google Scholar ePrint
[Mum66]
David Mumford. On the equations defining abelian varieties. i. Inventiones mathematicae, 1:287–354, 1966. https://doi.org/?
Google Scholar ePrint
[Ren18]
Joost Renes. Computing isogenies between montgomery curves using the action of (0, 0). In Tanja Lange and Rainer Steinwandt, editors, Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings, volume 10786 of Lecture Notes in Computer Science, 229–247. Springer, 2018. https://doi.org/10.1007/978-3-319-79063-3_11.
Google Scholar ePrint
[Vél71]
Jacques Vélu. Isogénies entre courbes elliptiques. Comptes-Rendus de l'Académie des Sciences, 273:A238–A241, 1971. https://doi.org/?
Google Scholar ePrint

PDFPDF Open access

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

Damien Robert and Nicolas Sarkis, "Computing 2-isogenies between Kummer lines," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/abvua69p1.

License

Copyright is held by the author(s)

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