Communications in Cryptology IACR CiC

Computing 2-isogenies between Kummer lines


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


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.


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.
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.
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.
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.
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.
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.
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.
Sabyasachi Karati and Palash Sarkar. Kummer for genus one over prime-order fields. Journal of Cryptology, 33(1):92–129, January 2020.
Peter L. Montgomery. Speeding the Pollard and elliptic curve methods of factorization. Mathematics of Computation, 48:243–264, 1987.
Tomoki Moriya, Hiroshi Onuki, Yusuke Aikawa, and Tsuyoshi Takagi. The generalized montgomery coordinate: A new computational tool for isogeny-based cryptography. 2022.
David Mumford. On the equations defining abelian varieties. i. Inventiones mathematicae, 1:287–354, 1966.
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.
Jacques Vélu. Isogénies entre courbes elliptiques. Comptes-Rendus de l'Académie des Sciences, 273:A238–A241, 1971.

PDFPDF Open access

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.


Copyright is held by the author(s)

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