Welcome to the resource topic for 2024/1519
Title:
Efficient theta-based algorithms for computing (\ell, \ell)-isogenies on Kummer surfaces for arbitrary odd \ell
Authors: Ryo Yoshizumi, Hiroshi Onuki, Ryo Ohashi, Momonari Kudo, Koji Nuida
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.
ePrint: https://eprint.iacr.org/2024/1519
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .