Paper 2024/1519
Efficient theta-based algorithms for computing $(\ell, \ell)$-isogenies on Kummer surfaces for arbitrary odd $\ell$
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)
- 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
-
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} }