Paper 2024/1519

Efficient theta-based algorithms for computing $(\ell, \ell)$-isogenies on Kummer surfaces for arbitrary odd $\ell$

Ryo Yoshizumi, Kyushu University
Hiroshi Onuki, University of Tokyo
Ryo Ohashi, University of Tokyo
Momonari Kudo, Fukuoka Institute of Technology
Koji Nuida, Kyushu University, National Institute of Advanced Industrial Science and Technology
Abstract

Isogeny-based cryptography is one of the candidates for post-quantum cryptography. Recently, many isogeny-based cryptosystems using isogenies between Kummer surfaces were proposed. Most of those cryptosystems use $(2,2)$-isogenies. However, to enhance the possibility of cryptosystems, higher degree isogenies, say $(\ell,\ell)$-isogenies for an odd $\ell$, is also crucial. For an odd $\ell$, the Lubicz-Robert gave a formula to compute $(\ell)^g$-isogenies in general dimension $g$. In this paper, we propose explicit and efficient algorithms to compute $(\ell,\ell)$-isogenies between Kummer surfaces, based on the Lubicz-Robert formula.In particular, we propose two algorithms for computing the codomain of the isogeny and two algorithms for evaluating the image of a point under the isogeny. Then, we count the number of arithmetic operations required for each of our proposed algorithms, and determine the most efficient algorithm in terms of the number of arithmetic operations from each of two types of algorithms for each $\ell$. As an application, using the most efficient one, we implemented the SIDH attack on B-SIDH in SageMath.In setting that originally claimed 128-bit security, our implementation was able to recover that secret key in about 11 hours.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
post-quantum cryptographyIsogeny-based cryptographyB-SIDHKummer surfacetheta function
Contact author(s)
yoshizumi ryo 483 @ s kyushu-u ac jp
hiroshi-onuki @ g ecc u-tokyo ac jp
ryo-ohashi @ g ecc u-tokyo ac jp
m-kudo @ fit ac jp
nuida @ imi kyushu-u ac jp
History
2024-09-30: approved
2024-09-27: received
See all versions
Short URL
https://ia.cr/2024/1519
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1519,
      author = {Ryo Yoshizumi and Hiroshi Onuki and Ryo Ohashi and Momonari Kudo and Koji Nuida},
      title = {Efficient theta-based algorithms  for computing $(\ell, \ell)$-isogenies  on Kummer surfaces for arbitrary odd $\ell$},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1519},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1519}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.