Article ID: 2025CIP0022
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.