IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Online ISSN : 1745-1337
Print ISSN : 0916-8508
Improving the Efficiency of Odd Degree Isogeny Computations with the Domain as a Product of Elliptic Curves
Ryo YOSHIZUMI
Author information
JOURNAL FREE ACCESS Advance online publication

Article ID: 2025CIP0022

Details
Abstract

Isogeny-based cryptography is one of post-quantum cryptography based on the difficulty of the isogeny problem. The central object is a one-dimensional isogeny, that is, an isogeny between elliptic curves. However, in recent years, not only one-dimensional isogenies but also two-dimensional isogenies have been used to isogeny-based cryptography. Such a two-dimensional isogeny is an isogeny between products of elliptic curves, and it is computed by decomposing to prime degree isogenies. The decomposed isogenies are called a chain of isogenies. Especially, for the decomposition, the first isogeny of the chain has the domain as a product of elliptic curves E1 × E2, and a point x to compute the image is of the form of x = (x(1) , 0E2) ∈ E1 × E2 for x(1)E1. In this paper, we focus on odd prime degree isogenies with the domain as a product of elliptic curves. For such an isogeny, we propose formulas and explicit algorithms based on the formulas. As a result, the computation of the image of a point (x(1) , 0E2) is improved compared to the existing method. For the application, when we compute an odd degree isogeny chain, this result allows efficient computation of the dominant isogeny in the chain by placing the isogeny with the largest prime degree first. In addition, we implemented the proposed algorithm in SageMath and confirmed its improved efficiency over the existing algorithm by comparing running times.

Content from these authors
© 2025 The Institute of Electronics, Information and Communication Engineers
Previous article Next article
feedback
Top