Efficient Theta-Based Algorithms for Computing (ℓ,ℓ)-Isogenies on Kummer Surfaces for Arbitrary Odd ℓ

Isogeny-based cryptography is one of the candidates for post-quantum cryptography. Recently, several 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, i.e., (ℓ,ℓ)-isogenies for an odd ℓ, are also crucial. For an odd ℓ, Lubicz–Robert proposed a formula to compute (ℓ)^g-isogenies in general dimensions g. In this paper, we propose explicit and efficient algorithms to compute (ℓ,ℓ)-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 proposed algorithm and determine the most efficient algorithm in terms of the number of operations for each algorithm for each ℓ. As an application, we implemented the SIDH attack on B-SIDH in SageMath using the most efficient algorithm. In a setting that originally claimed 128-bit security, our implementation was able to recover the secret key in approximately 11 h.