# Efficient Isogeny Computations on Twisted Edwards Curves

Authors: Suhri Kim; Kisoon Yoon; Jihoon Kwon; Seokhie Hong; Young-Ho Park
Journal: Security and Communication Networks
 (2018)

---

## Abstract

The isogeny-based cryptosystem is the most recent category in the field of postquantum cryptography. However, it is widely studied due to short key sizes and compatibility with the current elliptic curve primitives. The main building blocks when implementing the isogeny-based cryptosystem are isogeny computations and point operations. From isogeny construction perspective, since the cryptosystem moves along the isogeny graph, isogeny formula cannot be optimized for specific coefficients of elliptic curves. Therefore, Montgomery curves are used in the literature, due to the efficient point operation on an arbitrary elliptic curve. In this paper, we propose formulas for computing 3 and 4 isogenies on twisted Edwards curves. Additionally, we further optimize our isogeny formulas on Edwards curves and compare the computational cost of Montgomery curves. We also present the implementation results of our isogeny computations and demonstrate that isogenies on Edwards curves are as efficient as those on Montgomery curves.


---

## Body

## 1. Introduction

The security of public key cryptosystems is mostly based on a number of theoretic problems such as the hardness of factoring large numbers or solving discrete logarithms over the finite field. However, due to Shor’s algorithm, these problems can be solved in polynomial time by the quantum adversary, consequently threatening the security of current public key cryptosystems [1]. Therefore, demands for quantum-secure cryptographic primitives are inevitable.Postquantum cryptography (PQC) is alternative cryptographic primitives that are safe against the quantum adversary. Numerous studies have been made on PQC in order to substitute or interoperate with existing systems. The main categories of PQC are multivariate-based cryptography, code-based cryptography, lattice-based cryptography, hash-based digital signature, and isogeny-based cryptography. Although isogeny-based cryptography is the most recent field in PQC, it is considered as one of the prominent candidates due to its short key sizes and the reason that it can be implemented over currently used elliptic curve primitives.The security of isogeny-based cryptography is based on the hardness of finding isogeny between given two elliptic curves. The first isogeny-based cryptosystems using ordinary elliptic curves were proposed by Couveignes and later by Stolbunov [2, 3]. The proposed scheme was extremely inefficient and even suffered from the quantum subexponential algorithm proposed by Childs et al. [4]. In 2011, Jao and De Feo presented a new cryptosystem based on the difficulty of constructing isogenies between supersingular elliptic curves, which is still infeasible against the known quantum attacks [5]. In 2016, Azarderakhsh et al. proposed a key compression method for supersingular isogeny key exchange, which was later improved by Costello et al. [6, 7]. Azarderakhsh et al. also implemented key exchange protocol on ARM-NEON and FPGA devices [8, 9]. Costello et al. proposed faster computation methods and library for supersingular isogeny key exchange [10]. In 2017, isogeny-based digital signature schemes were proposed by Galbraith et al. and Yoo et al., which brought diversity in the isogeny-based cryptography [11, 12]. Additionally, after the National Institute of Standards and Technology (NIST) announced a standardization project for PQC, Supersingular Isogeny Key Encapsulation (SIKE) was submitted as one of the candidates [13]. As stated above, extensive researches have been done in isogeny-based cryptography.Since any curve in isogeny-based cryptosystem has group structure(Z/(p∓1)Z))2, for prime p, either the curve or its twist has a point of order four [5]. As a result, it is isomorphic to a twisted Edwards curve and to a Montgomery curve [14]. Moreover, as coefficients of the elliptic curves change randomly in the isogeny-based cryptosystem, Montgomery curves are used in the state-of-the-art implementations. This is due to the fact that Montgomery ladder reduces the cost of point operations on Montgomery curves compared with any other forms of elliptic curves. However, whether other forms of elliptic curves are efficient as Montgomery curves is still unclear. Costello et al. proposed explicit formulas for 3 and 4 isogenies and also remarked that there might exist savings to be gained in Supersingular Isogeny Diffie–Hellman (SIDH) twisted Edwards version [15]. Meyer et al. proposed the hybrid SIDH scheme which exploits the fact that arithmetic in Edwards curves are efficient in certain cases [16]. Their method uses Edwards curves for point operations and Montgomery curves for isogeny computation. Independent from isogeny-based cryptosystem, Moody and Shumow were the first to propose isogeny formula on elliptic curves other than Weierstrass form [17]. They applied Vélu’s formula on twisted Edwards curves and Huff curves. However, isogeny construction on these curves for cryptographic usage has not been done.The aim of this work is to identify whether (twisted) Edwards curves are as efficient as Montgomery curves for isogeny-based cryptosystems. The following list details the main contributions of this work.(i)
We propose the optimized 3- and 4-isogeny formulas on twisted Edwards curves to be applied in the isogeny-based cryptography. Previous works on constructing isogenies on alternate curves are mostly for the theoretical foundations. To the best of our knowledge, we are the first to propose 4-isogeny formula on (twisted) Edwards curves, given an arbitrary subgroup. The details of our isogeny formulas on twisted Edwards curves are presented in Section3.(ii)
We propose the optimized 3- and 4-isogeny formulas on Edwards curves. The proposed 3- and 4-isogeny formulas on Edwards curves require 6M+5S and 7M+5S, respectively, whereM (resp.,S) refers to field multiplication (resp., a field squaring). All of our formulas are given in terms of projective YZ-coordinates, which can later combine with YZ-coordinates only point operations on Edwards curves. The details of our isogeny formulas on Edwards curves are presented in Section 4.(iii)
We present the implementation results of our isogeny formulas and comprehensive analysis of their performance. We demonstrate that implementation results of isogenies on Edwards curves are similar to Montgomery curves. Therefore, the current isogeny-based cryptosystem can also work with Edwards curves.This paper is organized as follows: A review of some special forms of elliptic curves is provided in Section2. The description of isogeny of elliptic curves and Vélu’s formula to compute isogeny is also presented in Section 2. Specifically, we introduce an existing application of Vélu’s formula on Montgomery curves and twisted Edwards curves. In Section 3, we present our method to compute isogenies in twisted Edwards curves. Our optimized formulas for isogeny on Edwards curves and their implementations are given in Section 4. We draw our conclusions and future work in Section 5.


## 2. Preliminaries

In this section, we introduce the definition of special forms of elliptic curves. There are various forms of elliptic curves, but we will focus on twisted Edwards curves and Montgomery curves in this paper. Next, an isogeny of elliptic curves and Vélu’s formulas are introduced. Due to the work of Vélu, isogeny can be constructed given a finite subgroup. We describe a previous method that applied Vélu’s formula on twisted Edwards curves and Montgomery curves [5, 17].


### 2.1. Models of Elliptic Curve

LetK be a field with the characteristic not equal to 2 or 3. Anelliptic curve defined over K is a smooth, projective algebraic curve of genus 1 with a distinguished point. It is well known that the points of an elliptic curve form an additive group with the distinguished point as the identity element. From the Riemann–Roch theorem, every elliptic curve can be defined by a cubic polynomial equation in two variables. For example, an elliptic curve can be defined by a short Weierstrass equation(1)Wα,β:y2=x3+αx+β,4α3+27β2≠0,or by a Montgomery equation(2)MA,B:By2=x3+Ax2+x,BA2-4≠0.The j-invariants of the above curves are defined as j(Wα,β)=1728·4α3/(4α3+27β2) and j(MA,B)=256(A2-3)3/(A2-4), respectively.Two algebraic curves are said to bebirationally equivalent if their function fields are isomorphic to each other. The representative of a birational class is called amodel. An elliptic curve expressed in Montgomery equation is calledMontgomery model andWeierstrass model if it is expressed in Weierstrass equation. Two models play important roles in the implementation of elliptic curves for cryptographic usage. Note that MA,B has either three rational points of order two or a rational point of order four (possibly both) [19, 20].Another important model is theEdwards model defined by the equation(3)Ed:x2+y2=1+dx2y2,d∈K∖0,1.In fact, Ed is not an elliptic curve as it has singular points (1:0:0) and (0:1:0) at infinity. In Edwards curves, the point (0,1) is the identity element, and the point (0,-1) has order two. The points (1,0) and (-1,0) have order four. The condition that Ed always has a rational point of order four restricts the use of elliptic curves in the Edwards model. To overcome this deficiency, Bernstein et al. proposedtwisted Edwards curves which are defined by the equation(4)Ea,d:ax2+y2=1+dx2y2,for distinct nonzero elements a,d∈K [14]. Clearly, Ea,d is isomorphic to an Edwards curve over K(a). Later in this paper we demonstrate that it is efficient to work with both projective coordinates and projective curve coefficients. Let (A,B,C)∈P2(K) where C∈K-× such that a=A/C and d=D/C. Then Ea,d can be expressed as(5)EA:D:C:Ax2+Cy2=C+Dx2y2.The addition law on twisted Edwards curve is defined as follows, and doubling can be performed with exactly the same formula.(6)x1,y1+x2,y2=x1y2+y1x21+dx1x2y1y2,y1y2-ax1x21-dx1x2y1y2.Bernstein et al. showed the following cryptographically interesting relations on the above three models of elliptic curve [14].Theorem 1.
LetE be an elliptic curve defined over a field K with the characteristic not equal to 2. The group of rational points E(K) has an element of order 4 if and only if E is birationally equivalent over K to an Edwards curve.Theorem 2.
LetK be a field with #K≡3(mod4); then every Montgomery curve over K is birationally equivalent over K to an Edwards curve.As Theorem2 is used to compute 4-isogeny formula in Edwards curves, we shall define K with #K≡3mod4 in the remainder of this paper, unless otherwise specified.


#### 2.1.1. Relation between Twisted Edwards Curves and Montgomery Curves

In [14], Bernstein et al. proved that every twisted Edwards curve over K is birationally equivalent over K to a Montgomery curve. Since this relation is used later in this paper, we shall describe it briefly. Let a and d be nonzero elements in K. Then every twisted Edwards curve Ea,d is birationally equivalent to a Montgomery form MA,B via(7)x,y→u,v=1+y1-y,1+y1-yx,where A=2(a+d)/(a-d) and B=4/(a-d). The inverse of the map from MA,B to Ea,d is defined as(8)u,v→x,y=uv,u-1u+1.The first coordinate in map (7) is computed by using only y-coordinate and the second coordinate in map (8) uses only u-coordinate. In projective coordinates, this map becomes remarkably simple [21]. A point (XM:ZM) on a Montgomery curve can be transformed to the corresponding Edwards YZ-coordinates (YE:ZE) and vice versa:(9)XM:ZM→YE:ZE=XM-ZM:XM+ZM,YE:ZE→XM:ZM=YE+ZE:ZE-YE.Therefore, the point conversion between these two curves costs only two additions.


### 2.2. Isogeny and Vélu’s Formulas

Anisogeny between two elliptic curves E1 and E2 is a surjective group homomorphism with a finite kernel. Two elliptic curves E1 and E2 are said to beisogenous over K if there exists an isogeny ϕ:E1→E2 defined over K. If the degree of the isogeny ϕ is equal to the order of the kernel of ϕ, then ϕ is called aseparable isogeny. An isogeny of degree l is called an l-isogeny. Throughout this paper, an l-isogeny is a separable isogeny, unless otherwise stated.For every isogenyϕ:E1→E2, there exists an isogeny ϕ^:E2→E1 such that(10)ϕ∘ϕ^=deg⁡ϕ.The isogeny ϕ^ is called the dual isogeny of ϕ. By using this fact, the relation of isogeny is an equivalence relation. Moreover, E1 and E2 are isogenous over K if and only if the group of the rational points E1(K) and E2(K) has the same cardinality. If ϕ is a separable isogeny of degree 1, then ϕ is an isomorphism. An isomorphism class of elliptic curves is uniquely represented by the j-invariant. That is, two elliptic curves are isomorphic over K- if and only if they have the same j-invariant. Moreover, the kernel of an isogeny is finite. Conversely, if a finite subgroup G of an elliptic curve E is given, then there exists an elliptic curve E′≅E/G and a separable isogeny ϕ:E→E′, with ker⁡ϕ=G.There are two methods to construct isogeny between elliptic curves. Vélu gave the explicit formulas to construct an isogeny with a given elliptic curve and a given finite subgroup as the kernel [22]. Later, Kohel proposed that isogeny ϕ can be computed from the kernel polynomial [23]. In this paper, we focus on Vélu’s method to construct isogenies. Vélu’s formulas are based on the transformation(11)xP,yP→xP+∑Q∈G∖OxP+Q-xQ,yP+∑Q∈G∖OyP+Q-yQ,which is invariant under the translation by the points in the kernel G. In order to compute rational functions given by Vélu, let E be an elliptic curve with short Weierstrass form as in (1) for the simplicity. For a finite subgroup G, partition G∖{O} into two sets, G+ and G-, such that G∖{O}=G+∪G- and Q∈G+ if and only if -Q∈G-. For each point Q∈G, define the following equations:(12)gQx=3xQ2+a,gQy=-2yQ,vQ=2gQx,uQ=gQy2,v=∑Q∈G+vQ,w=∑Q∈G+uQ+xQvQ.Then, the isogeny ϕ is given by(13)ϕx,y→x+∑Q∈G+vQx-xQ-uQx-xQ2,y-∑Q∈G+2uQyx-xQ3+vQy-yQ-gQxgQyx-xQ2.The order of the isogeny is equal to the order of the subgroup G. The equation of the image curve is(14)E′:y2=x3+α-5vx+β-7w.


#### 2.2.1. Vélu’s Formulas on Montgomery Curves

In this section, we describe how even-degree isogenies are induced on Montgomery curves. This method was proposed by Jao and De Feo and later optimized by Costello et al. [5, 10]. The main processes for deriving 4-isogeny are illustrated in projective coordinates. For odd-degree isogenies, refer to [10].LetMA,B be a Montgomery curve defined in (2). It has a point of order two P2=(0,0) and a point of order four P4=(1,(A+2)/B), either defined over a quadratic extension, such that [2]P4=P2. The isogeny—which has degree 2 and maps P4 to (0, 0)—is defined as(15)ϕ:MA,B→FX:Y:Z→XX-Z2:YX2-Z2:X2Z,where x=X/Z and y=Y/Z for (x,y)∈MA,B. The corresponding image curve is given as(16)F:By2=x3+A+6x2+42+Ax.Since the image curve is not in Montgomery form, computing square roots is unavoidable in order to transformF back to Montgomery form. To overcome such problem, consider the isogeny ψ with (0,0) as a kernel, given by(17)ψ:F→MA′,B′X:Y:Z→X′:Y′:Z′,where X′=-X(AZ+X+2Z)(X+4Z), Y′=Y(4AZ2-X2+8Z2), and Z′=(A-2)X2Z in the above equation. The equation of the image curve is given as in Montgomery form:(18)MA′,B′:B2-Ay2=x3-2A+62-Ax2+x.Then, ϕ1=ψ∘ϕ is an isogeny of degree four that maps MA,B to MA′,B′=MA,B/P4. However, this formula cannot be applied twice to obtain isogeny of degree 42. Instead, it would only induce multiplication by 4-isogeny when ϕ1 is computed twice. In order to apply 4-isogeny successively for 4l-isogeny, ϕ1 must be combined with isomorphism of Montgomery curves that maps 4-torsion point to some specific coordinate. This is already apparent as we have computed ϕ with point P4 of a specific form. Let P≠±P4 be a point of order four in MA,B. Let P=(XM:YM:ZM) and [2]P=(X0:Y0:Z0) be the projective coordinates of P and [2]P, respectively. The isomorphism ι defined below maps [2]P to (0,0) and P to point of the form (1,…).(19)ι:MA,B→EX:Y:Z→ZMXZ0-ZX0:YZMZ0:ZXMZ0-ZMX0,with the corresponding curve equation defined below.(20)E:BZMZ0XMZ0-ZMX0y2=x3+ZM3X0+AZ0XMZ0-ZMX0x2+x.Combiningϕ1 with ι, we are able to compute 4-isogeny successively.


#### 2.2.2. Vélu’s Formulas on Twisted Edwards Curves

As denoted in the previous section, there exist birational maps from Edwards curves to Weierstrass curves. Letψ be the transformation from a twisted Edwards curve to a Weierstrass curve W and ϕ be isogeny from W to another curve W′. Let ψ-1 be the transformation from a Weierstrass curve W′ back to a twisted Edwards curve. The intuitive approach toward computing the isogeny between twisted Edwards curves is to combine these maps. However, the transformation from Weierstrass curves to twisted Edwards curves is complicated if the corresponding Weierstrass curve is not of the form below.(21)Wα′,β′′:y2=x3+2a+dx2+a-d2xMoreover, one needs to compute square roots in order to transform back to twisted Edwards form. To solve this issue, Moody and Shumow proposed compact formulas for odd-degree isogenies on twisted Edwards curves [17]. The isogeny of order l=2s+1 on twisted Edwards curves can be computed by using the following theorem.Theorem 3.
SupposeG is a subgroup of the twisted Edwards curve Ea,d with odd order l=2s+1 and points G={(0,1),(±α1,β1),…,(±αs,βs)}. Then a normalized l-isogeny from Ea,d to Ea^,d^, where a^=A4/B4al and d^=A4B4dl, with A=∏i=1sαi, B=∏i=1sβi, is given by(22)Ψx,y=-1sxA2∏i=1sβi2x2-αi2y21-d2αi2βi2x2y2,yB2∏i=1sβi2y2-a2αi2x21-d2αi2βi2x2y2.The idea of the above formula comes from the fact that the map(23)xP,yP⟼∏Q∈GxP+QxQ,∏Q∈GyP+QyQ,is invariant under the translation by an element in G. Note that this idea does not apply for even-degree isogenies since either the abscissa or the ordinate of every 2-torsion point vanishes.


## 2.1. Models of Elliptic Curve

LetK be a field with the characteristic not equal to 2 or 3. Anelliptic curve defined over K is a smooth, projective algebraic curve of genus 1 with a distinguished point. It is well known that the points of an elliptic curve form an additive group with the distinguished point as the identity element. From the Riemann–Roch theorem, every elliptic curve can be defined by a cubic polynomial equation in two variables. For example, an elliptic curve can be defined by a short Weierstrass equation(1)Wα,β:y2=x3+αx+β,4α3+27β2≠0,or by a Montgomery equation(2)MA,B:By2=x3+Ax2+x,BA2-4≠0.The j-invariants of the above curves are defined as j(Wα,β)=1728·4α3/(4α3+27β2) and j(MA,B)=256(A2-3)3/(A2-4), respectively.Two algebraic curves are said to bebirationally equivalent if their function fields are isomorphic to each other. The representative of a birational class is called amodel. An elliptic curve expressed in Montgomery equation is calledMontgomery model andWeierstrass model if it is expressed in Weierstrass equation. Two models play important roles in the implementation of elliptic curves for cryptographic usage. Note that MA,B has either three rational points of order two or a rational point of order four (possibly both) [19, 20].Another important model is theEdwards model defined by the equation(3)Ed:x2+y2=1+dx2y2,d∈K∖0,1.In fact, Ed is not an elliptic curve as it has singular points (1:0:0) and (0:1:0) at infinity. In Edwards curves, the point (0,1) is the identity element, and the point (0,-1) has order two. The points (1,0) and (-1,0) have order four. The condition that Ed always has a rational point of order four restricts the use of elliptic curves in the Edwards model. To overcome this deficiency, Bernstein et al. proposedtwisted Edwards curves which are defined by the equation(4)Ea,d:ax2+y2=1+dx2y2,for distinct nonzero elements a,d∈K [14]. Clearly, Ea,d is isomorphic to an Edwards curve over K(a). Later in this paper we demonstrate that it is efficient to work with both projective coordinates and projective curve coefficients. Let (A,B,C)∈P2(K) where C∈K-× such that a=A/C and d=D/C. Then Ea,d can be expressed as(5)EA:D:C:Ax2+Cy2=C+Dx2y2.The addition law on twisted Edwards curve is defined as follows, and doubling can be performed with exactly the same formula.(6)x1,y1+x2,y2=x1y2+y1x21+dx1x2y1y2,y1y2-ax1x21-dx1x2y1y2.Bernstein et al. showed the following cryptographically interesting relations on the above three models of elliptic curve [14].Theorem 1.
LetE be an elliptic curve defined over a field K with the characteristic not equal to 2. The group of rational points E(K) has an element of order 4 if and only if E is birationally equivalent over K to an Edwards curve.Theorem 2.
LetK be a field with #K≡3(mod4); then every Montgomery curve over K is birationally equivalent over K to an Edwards curve.As Theorem2 is used to compute 4-isogeny formula in Edwards curves, we shall define K with #K≡3mod4 in the remainder of this paper, unless otherwise specified.


### 2.1.1. Relation between Twisted Edwards Curves and Montgomery Curves

In [14], Bernstein et al. proved that every twisted Edwards curve over K is birationally equivalent over K to a Montgomery curve. Since this relation is used later in this paper, we shall describe it briefly. Let a and d be nonzero elements in K. Then every twisted Edwards curve Ea,d is birationally equivalent to a Montgomery form MA,B via(7)x,y→u,v=1+y1-y,1+y1-yx,where A=2(a+d)/(a-d) and B=4/(a-d). The inverse of the map from MA,B to Ea,d is defined as(8)u,v→x,y=uv,u-1u+1.The first coordinate in map (7) is computed by using only y-coordinate and the second coordinate in map (8) uses only u-coordinate. In projective coordinates, this map becomes remarkably simple [21]. A point (XM:ZM) on a Montgomery curve can be transformed to the corresponding Edwards YZ-coordinates (YE:ZE) and vice versa:(9)XM:ZM→YE:ZE=XM-ZM:XM+ZM,YE:ZE→XM:ZM=YE+ZE:ZE-YE.Therefore, the point conversion between these two curves costs only two additions.


## 2.1.1. Relation between Twisted Edwards Curves and Montgomery Curves

In [14], Bernstein et al. proved that every twisted Edwards curve over K is birationally equivalent over K to a Montgomery curve. Since this relation is used later in this paper, we shall describe it briefly. Let a and d be nonzero elements in K. Then every twisted Edwards curve Ea,d is birationally equivalent to a Montgomery form MA,B via(7)x,y→u,v=1+y1-y,1+y1-yx,where A=2(a+d)/(a-d) and B=4/(a-d). The inverse of the map from MA,B to Ea,d is defined as(8)u,v→x,y=uv,u-1u+1.The first coordinate in map (7) is computed by using only y-coordinate and the second coordinate in map (8) uses only u-coordinate. In projective coordinates, this map becomes remarkably simple [21]. A point (XM:ZM) on a Montgomery curve can be transformed to the corresponding Edwards YZ-coordinates (YE:ZE) and vice versa:(9)XM:ZM→YE:ZE=XM-ZM:XM+ZM,YE:ZE→XM:ZM=YE+ZE:ZE-YE.Therefore, the point conversion between these two curves costs only two additions.


## 2.2. Isogeny and Vélu’s Formulas

Anisogeny between two elliptic curves E1 and E2 is a surjective group homomorphism with a finite kernel. Two elliptic curves E1 and E2 are said to beisogenous over K if there exists an isogeny ϕ:E1→E2 defined over K. If the degree of the isogeny ϕ is equal to the order of the kernel of ϕ, then ϕ is called aseparable isogeny. An isogeny of degree l is called an l-isogeny. Throughout this paper, an l-isogeny is a separable isogeny, unless otherwise stated.For every isogenyϕ:E1→E2, there exists an isogeny ϕ^:E2→E1 such that(10)ϕ∘ϕ^=deg⁡ϕ.The isogeny ϕ^ is called the dual isogeny of ϕ. By using this fact, the relation of isogeny is an equivalence relation. Moreover, E1 and E2 are isogenous over K if and only if the group of the rational points E1(K) and E2(K) has the same cardinality. If ϕ is a separable isogeny of degree 1, then ϕ is an isomorphism. An isomorphism class of elliptic curves is uniquely represented by the j-invariant. That is, two elliptic curves are isomorphic over K- if and only if they have the same j-invariant. Moreover, the kernel of an isogeny is finite. Conversely, if a finite subgroup G of an elliptic curve E is given, then there exists an elliptic curve E′≅E/G and a separable isogeny ϕ:E→E′, with ker⁡ϕ=G.There are two methods to construct isogeny between elliptic curves. Vélu gave the explicit formulas to construct an isogeny with a given elliptic curve and a given finite subgroup as the kernel [22]. Later, Kohel proposed that isogeny ϕ can be computed from the kernel polynomial [23]. In this paper, we focus on Vélu’s method to construct isogenies. Vélu’s formulas are based on the transformation(11)xP,yP→xP+∑Q∈G∖OxP+Q-xQ,yP+∑Q∈G∖OyP+Q-yQ,which is invariant under the translation by the points in the kernel G. In order to compute rational functions given by Vélu, let E be an elliptic curve with short Weierstrass form as in (1) for the simplicity. For a finite subgroup G, partition G∖{O} into two sets, G+ and G-, such that G∖{O}=G+∪G- and Q∈G+ if and only if -Q∈G-. For each point Q∈G, define the following equations:(12)gQx=3xQ2+a,gQy=-2yQ,vQ=2gQx,uQ=gQy2,v=∑Q∈G+vQ,w=∑Q∈G+uQ+xQvQ.Then, the isogeny ϕ is given by(13)ϕx,y→x+∑Q∈G+vQx-xQ-uQx-xQ2,y-∑Q∈G+2uQyx-xQ3+vQy-yQ-gQxgQyx-xQ2.The order of the isogeny is equal to the order of the subgroup G. The equation of the image curve is(14)E′:y2=x3+α-5vx+β-7w.


### 2.2.1. Vélu’s Formulas on Montgomery Curves

In this section, we describe how even-degree isogenies are induced on Montgomery curves. This method was proposed by Jao and De Feo and later optimized by Costello et al. [5, 10]. The main processes for deriving 4-isogeny are illustrated in projective coordinates. For odd-degree isogenies, refer to [10].LetMA,B be a Montgomery curve defined in (2). It has a point of order two P2=(0,0) and a point of order four P4=(1,(A+2)/B), either defined over a quadratic extension, such that [2]P4=P2. The isogeny—which has degree 2 and maps P4 to (0, 0)—is defined as(15)ϕ:MA,B→FX:Y:Z→XX-Z2:YX2-Z2:X2Z,where x=X/Z and y=Y/Z for (x,y)∈MA,B. The corresponding image curve is given as(16)F:By2=x3+A+6x2+42+Ax.Since the image curve is not in Montgomery form, computing square roots is unavoidable in order to transformF back to Montgomery form. To overcome such problem, consider the isogeny ψ with (0,0) as a kernel, given by(17)ψ:F→MA′,B′X:Y:Z→X′:Y′:Z′,where X′=-X(AZ+X+2Z)(X+4Z), Y′=Y(4AZ2-X2+8Z2), and Z′=(A-2)X2Z in the above equation. The equation of the image curve is given as in Montgomery form:(18)MA′,B′:B2-Ay2=x3-2A+62-Ax2+x.Then, ϕ1=ψ∘ϕ is an isogeny of degree four that maps MA,B to MA′,B′=MA,B/P4. However, this formula cannot be applied twice to obtain isogeny of degree 42. Instead, it would only induce multiplication by 4-isogeny when ϕ1 is computed twice. In order to apply 4-isogeny successively for 4l-isogeny, ϕ1 must be combined with isomorphism of Montgomery curves that maps 4-torsion point to some specific coordinate. This is already apparent as we have computed ϕ with point P4 of a specific form. Let P≠±P4 be a point of order four in MA,B. Let P=(XM:YM:ZM) and [2]P=(X0:Y0:Z0) be the projective coordinates of P and [2]P, respectively. The isomorphism ι defined below maps [2]P to (0,0) and P to point of the form (1,…).(19)ι:MA,B→EX:Y:Z→ZMXZ0-ZX0:YZMZ0:ZXMZ0-ZMX0,with the corresponding curve equation defined below.(20)E:BZMZ0XMZ0-ZMX0y2=x3+ZM3X0+AZ0XMZ0-ZMX0x2+x.Combiningϕ1 with ι, we are able to compute 4-isogeny successively.


### 2.2.2. Vélu’s Formulas on Twisted Edwards Curves

As denoted in the previous section, there exist birational maps from Edwards curves to Weierstrass curves. Letψ be the transformation from a twisted Edwards curve to a Weierstrass curve W and ϕ be isogeny from W to another curve W′. Let ψ-1 be the transformation from a Weierstrass curve W′ back to a twisted Edwards curve. The intuitive approach toward computing the isogeny between twisted Edwards curves is to combine these maps. However, the transformation from Weierstrass curves to twisted Edwards curves is complicated if the corresponding Weierstrass curve is not of the form below.(21)Wα′,β′′:y2=x3+2a+dx2+a-d2xMoreover, one needs to compute square roots in order to transform back to twisted Edwards form. To solve this issue, Moody and Shumow proposed compact formulas for odd-degree isogenies on twisted Edwards curves [17]. The isogeny of order l=2s+1 on twisted Edwards curves can be computed by using the following theorem.Theorem 3.
SupposeG is a subgroup of the twisted Edwards curve Ea,d with odd order l=2s+1 and points G={(0,1),(±α1,β1),…,(±αs,βs)}. Then a normalized l-isogeny from Ea,d to Ea^,d^, where a^=A4/B4al and d^=A4B4dl, with A=∏i=1sαi, B=∏i=1sβi, is given by(22)Ψx,y=-1sxA2∏i=1sβi2x2-αi2y21-d2αi2βi2x2y2,yB2∏i=1sβi2y2-a2αi2x21-d2αi2βi2x2y2.The idea of the above formula comes from the fact that the map(23)xP,yP⟼∏Q∈GxP+QxQ,∏Q∈GyP+QyQ,is invariant under the translation by an element in G. Note that this idea does not apply for even-degree isogenies since either the abscissa or the ordinate of every 2-torsion point vanishes.


## 2.2.1. Vélu’s Formulas on Montgomery Curves

In this section, we describe how even-degree isogenies are induced on Montgomery curves. This method was proposed by Jao and De Feo and later optimized by Costello et al. [5, 10]. The main processes for deriving 4-isogeny are illustrated in projective coordinates. For odd-degree isogenies, refer to [10].LetMA,B be a Montgomery curve defined in (2). It has a point of order two P2=(0,0) and a point of order four P4=(1,(A+2)/B), either defined over a quadratic extension, such that [2]P4=P2. The isogeny—which has degree 2 and maps P4 to (0, 0)—is defined as(15)ϕ:MA,B→FX:Y:Z→XX-Z2:YX2-Z2:X2Z,where x=X/Z and y=Y/Z for (x,y)∈MA,B. The corresponding image curve is given as(16)F:By2=x3+A+6x2+42+Ax.Since the image curve is not in Montgomery form, computing square roots is unavoidable in order to transformF back to Montgomery form. To overcome such problem, consider the isogeny ψ with (0,0) as a kernel, given by(17)ψ:F→MA′,B′X:Y:Z→X′:Y′:Z′,where X′=-X(AZ+X+2Z)(X+4Z), Y′=Y(4AZ2-X2+8Z2), and Z′=(A-2)X2Z in the above equation. The equation of the image curve is given as in Montgomery form:(18)MA′,B′:B2-Ay2=x3-2A+62-Ax2+x.Then, ϕ1=ψ∘ϕ is an isogeny of degree four that maps MA,B to MA′,B′=MA,B/P4. However, this formula cannot be applied twice to obtain isogeny of degree 42. Instead, it would only induce multiplication by 4-isogeny when ϕ1 is computed twice. In order to apply 4-isogeny successively for 4l-isogeny, ϕ1 must be combined with isomorphism of Montgomery curves that maps 4-torsion point to some specific coordinate. This is already apparent as we have computed ϕ with point P4 of a specific form. Let P≠±P4 be a point of order four in MA,B. Let P=(XM:YM:ZM) and [2]P=(X0:Y0:Z0) be the projective coordinates of P and [2]P, respectively. The isomorphism ι defined below maps [2]P to (0,0) and P to point of the form (1,…).(19)ι:MA,B→EX:Y:Z→ZMXZ0-ZX0:YZMZ0:ZXMZ0-ZMX0,with the corresponding curve equation defined below.(20)E:BZMZ0XMZ0-ZMX0y2=x3+ZM3X0+AZ0XMZ0-ZMX0x2+x.Combiningϕ1 with ι, we are able to compute 4-isogeny successively.


## 2.2.2. Vélu’s Formulas on Twisted Edwards Curves

As denoted in the previous section, there exist birational maps from Edwards curves to Weierstrass curves. Letψ be the transformation from a twisted Edwards curve to a Weierstrass curve W and ϕ be isogeny from W to another curve W′. Let ψ-1 be the transformation from a Weierstrass curve W′ back to a twisted Edwards curve. The intuitive approach toward computing the isogeny between twisted Edwards curves is to combine these maps. However, the transformation from Weierstrass curves to twisted Edwards curves is complicated if the corresponding Weierstrass curve is not of the form below.(21)Wα′,β′′:y2=x3+2a+dx2+a-d2xMoreover, one needs to compute square roots in order to transform back to twisted Edwards form. To solve this issue, Moody and Shumow proposed compact formulas for odd-degree isogenies on twisted Edwards curves [17]. The isogeny of order l=2s+1 on twisted Edwards curves can be computed by using the following theorem.Theorem 3.
SupposeG is a subgroup of the twisted Edwards curve Ea,d with odd order l=2s+1 and points G={(0,1),(±α1,β1),…,(±αs,βs)}. Then a normalized l-isogeny from Ea,d to Ea^,d^, where a^=A4/B4al and d^=A4B4dl, with A=∏i=1sαi, B=∏i=1sβi, is given by(22)Ψx,y=-1sxA2∏i=1sβi2x2-αi2y21-d2αi2βi2x2y2,yB2∏i=1sβi2y2-a2αi2x21-d2αi2βi2x2y2.The idea of the above formula comes from the fact that the map(23)xP,yP⟼∏Q∈GxP+QxQ,∏Q∈GyP+QyQ,is invariant under the translation by an element in G. Note that this idea does not apply for even-degree isogenies since either the abscissa or the ordinate of every 2-torsion point vanishes.


## 3. The Proposed Isogeny Computations on Twisted Edwards Curves

In this section, we propose optimized formulas for 3-isogeny and 4-isogeny on twisted Edwards curves, which are commonly used degrees in the isogeny-based cryptosystem. For 3-isogeny, we use Moody and Shumow’s result as a base formula and optimize it by using projective coordinates, projective curve coefficients, and division polynomial [17]. For even-degree isogeny computation, we exploit the efficiency of computing a birational map between twisted Edwards curves and Montgomery curves. The 4-isogeny formula on twisted Edwards curves can be obtained by composing the birational map and isogeny on Montgomery curves.


### 3.1. 3 Isogenies on Twisted Edwards Curves

LetP=(α,β) be a 3-torsion point on twisted Edwards curve Ea,d defined in (4). Let ϕ be the 3-isogeny with kernel P that maps Ea,d to the twisted Edwards curve Ea′,d′, where Ea′,d′=Ea,d/P. Then, by using the formula proposed by Moody and Shumow [17], ϕ is given by(24)ϕx,y=-1xα2β2x2-α2y21-d2α2β2x2y2,yβ2β2y2-α2a2x21-d2α2β2x2y2,with the curve parameters a′ and d′ such that(25)a′=α4β4a3,d′=α4β4d3.From the curve equation, x2 and α2 can be expressed as x2=1-y2/a-dy2 and α2=1-β2/a-dβ2, respectively. By substituting x2 and α2, the y-coordinate in equation (24) is given by(26)yβ2β2y2-α2a2x21-d2α2β2x2y2=yβ2β2y2-1-β2/a-dβ2a21-y2/a-dy21-d21-β2/a-dβ2β21-y2/a-dy2y2.To prevent inversions when computing isogeny and curve coefficients, we utilize projective coordinates and projective curve coefficients. Let P=(X3:Y3:Z3) be the projective representation of P such that α=X3/Z3 and β=Y3/Z3. Let (Y:Z) be the additional input and Y′:Z′ be its corresponding image. By substituting the projective coordinates in (26) and simplifying the equation, we can obtain(27)Y′Z′=YZ32ZY32·Y32Y2aZ32-dY32aZ2-dY2-Z32Z2Z32-Y32a2Z2-Y2Z32Z2aZ2-dY2aZ32-dY32-d2Y32Y2Z32-X32Z2-Y2=YZ32ZY32·aY32Z2-dY32Y2+aZ32Y2-aZ32Z2dY32Y2-dY32Z2+aZ32Z2-dZ32Y2.Sincey=Y3/Z3 is a root of the 3-division polynomial ψ3(y)=(a-d)3(a+2ay-2dy3-dy4)/24(1-y)4, we can express d=aZ33(Z3+2Y3)/Y33(2Z3+Y3). Then, we have(28)Y′Z′=YZ2Y32+2Z2Y3Z3+Y2Z32ZZ2Y32+2Y2Y3Z3+Y2Z32.In summary, from the additional input(Y:Z), projective version of (26) gives(29)Y′:Z′=YZ2Y32+2Z2Y3Z3+Y2Z32:ZZ2Y32+2Y2Y3Z3+Y2Z32.Now, leta′ and d′ be the curve coefficients of the image curve. Substituting α2=Z32-Y32/aZ32-dY32 and d=aZ33(Z3+2Y3)/Y33(2Z3+Y3) in (25) represented in projective coordinates, we have(30)a′=aY3+2Z32Y32,d′=aZ3Z3+2Y33Y332Z3+Y3.To avoid inversions, projective versions of (30) are(31)A′=AY3Y3+2Z33,D′=AZ3Z3+2Y33,C′=C2Y332Z3+Y3,where a′=A′/C′ and d′=D′/C′ for a=A/C and d=D/C.


### 3.2. 4 Isogenies on Twisted Edwards Curves

Computing 4 isogenies is more complicated than odd-degree isogenies in twisted Edwards curves. There exist roughly two approaches for computing 4 isogenies in twisted Edwards curves. The first method is to transform twisted Edwards curve to corresponding Weierstrass form and apply Vélu’s formula. However, transforming back to twisted Edwards form from Weierstrass form is complicated as square root computations might be required in some cases. The other approach is to use the birational relation between twisted Edwards curves and Montgomery curves. As the transformation between twisted Edwards curves and Montgomery curves costs only two additions, we can compute 4-isogeny on a Montgomery curve and transform back to a twisted Edwards curve. However, when applying the 4-isogeny formula on Montgomery curves proposed by Jao and De Feo, the isomorphismι that maps 4-torsion point to a specific point must be combined to compute 4-isogeny consecutively [5]. Therefore, after transforming a twisted Edwards curve into a Montgomery curve, the isomorphism must be combined with 4-isogeny.In summary, the composition we used is as follows:(32)Ea,d→ψMA,B→ιMA′,B′→ϕ1MA′′,B′′→ψ′-1Ea′,d′,where ψ and ψ′-1 are birational maps and ϕ1 is an isogeny obtained using Vélu’s formulas.LetP=(X4:Y4:Z4) be a 4-torsion point on twisted Edwards curve Ea,d, represented in projective coordinate. The birational map ψ that maps twisted Edwards curve Ea,d to Montgomery curve MA,B sends P as follows:(33)ψY4:Z4→XM:ZM=Y4+Z4:Z4-Y4,where(34)A=2a+da-d,B=4a-d.LetP′=(XM:ZM) be the corresponding 4-torsion point on MA,B. The evaluation of 4-isogeny ϕ=ϕ1∘ι on MA,B with kernel P′ is defined as in [10].(35)X′:Z′=X2XMZMZ-XXM2+ZM2XMX-ZMZ2:Z2XMZMX-ZXM2+ZM2ZMX-XMZ2.Note that this formula is already combined with the isomorphism ι so that additional transform is not necessary. Finally, the birational map ψ′-1, which maps the Montgomery curve back to the twisted Edwards curve Ea′,d′, is defined as follows:(36)ψ′-1X′:Z′→Y′:Z′=X′-Z′:X′+Z′.The curve coefficientsa′ and d′ of the image curve Ea′,d′ are given by(37)a′=A+2B,d′=A-2B.Combining the three mapsψ, ϕ, and ψ′-1 yields 4-isogeny from Ea,d to Ea′,d′. The equation below is the evaluation of the 4-isogeny by computing Y′:Z′, given the additional point (Y:Z) on Ea,d.(38)Y′=X2XMZMZ-XXM2+ZM2XMX-ZMZ2-Z2XMZMX-ZXM2+ZM2ZMX-XMZ2,Z′=X2XMZMZ-XXM2+ZM2XMX-ZMZ2+Z2XMZMX-ZXM2+ZM2ZMX-XMZ2.Simplifying the above equations by substituting XM=Y4+Z4 and ZM=Z4-Y4, we have(39)Y′=Z2Y42+Y2Z42YZY4+Z42,Z′=Z2Y42+Y2Z422+2Y2Z2Y4Z4Y42+Z42.We now describe the evaluation of the curve coefficients of the image curve. For the 4-torsion pointP=(X4:Y4:Z4) on the twisted Edwards curve Ea,d, birational map is used to transform into the Montgomery form MA,B. The curve coefficients, as well as the image of P and [2]P, are as given below.(40)A=2a+da-d,B=4a-d,ψP=XM:ZM,ψ2P=X0:Z0.Here XM=Y4+Z4,  ZM=Z4-Y4, X0=(XM+ZM)2(XM-ZM)2, and Z0=4XMZM((XM-ZM)2+((A+2)/4)(4XMZM)) in the above equation. Next, the isomorphism ι sends ψ(P) to a point of the form (1,…) and ψ([2]P) to (0,0). The coefficients of the corresponding image curve MA′,B′ are(41)A′=ZM3X0+AZ0XMZ0-ZMX0,B′=BZMZ0XMZ0-ZMX0.Then, by combining the isogenyϕ1, coefficients of the image curve are given below.(42)A′′=-2A′+62-A′=2AZMZ0-3ZMX0+6XMZ0AZMZ0+5ZMX0-2XMZ0,(43)B′′=B′2-A′=-BZMZ0AZMZ0+5ZMX0-2XMZ0.Finally, by applying the birational map to transform back to the twisted Edwards curve, we obtain the coefficients of the 4-isogeny twisted Edwards curve. LetEa′,d′=Ea,d/P be the image curve. Then we have(44)a′=A′′+2B′′=-4AZMZ0+ZMX0+2XMZ0BZMZ0,(45)d′=A′′-2B′′=-16ZMX0-XMZ0BZMZ0.SinceXM/ZM is a root of the 4-division polynomial ϕ4=x4+2Ax3+6x2+2Ax+1 of a Montgomery curve MA,B, we can express A in terms of XM and ZM. Simplifying the above equation with expression in terms of Y4 and Z4, we have(46)A′=AY4+Z44,D′=8AY4Z4Y42+Z42,C′=CY44.


## 3.1. 3 Isogenies on Twisted Edwards Curves

LetP=(α,β) be a 3-torsion point on twisted Edwards curve Ea,d defined in (4). Let ϕ be the 3-isogeny with kernel P that maps Ea,d to the twisted Edwards curve Ea′,d′, where Ea′,d′=Ea,d/P. Then, by using the formula proposed by Moody and Shumow [17], ϕ is given by(24)ϕx,y=-1xα2β2x2-α2y21-d2α2β2x2y2,yβ2β2y2-α2a2x21-d2α2β2x2y2,with the curve parameters a′ and d′ such that(25)a′=α4β4a3,d′=α4β4d3.From the curve equation, x2 and α2 can be expressed as x2=1-y2/a-dy2 and α2=1-β2/a-dβ2, respectively. By substituting x2 and α2, the y-coordinate in equation (24) is given by(26)yβ2β2y2-α2a2x21-d2α2β2x2y2=yβ2β2y2-1-β2/a-dβ2a21-y2/a-dy21-d21-β2/a-dβ2β21-y2/a-dy2y2.To prevent inversions when computing isogeny and curve coefficients, we utilize projective coordinates and projective curve coefficients. Let P=(X3:Y3:Z3) be the projective representation of P such that α=X3/Z3 and β=Y3/Z3. Let (Y:Z) be the additional input and Y′:Z′ be its corresponding image. By substituting the projective coordinates in (26) and simplifying the equation, we can obtain(27)Y′Z′=YZ32ZY32·Y32Y2aZ32-dY32aZ2-dY2-Z32Z2Z32-Y32a2Z2-Y2Z32Z2aZ2-dY2aZ32-dY32-d2Y32Y2Z32-X32Z2-Y2=YZ32ZY32·aY32Z2-dY32Y2+aZ32Y2-aZ32Z2dY32Y2-dY32Z2+aZ32Z2-dZ32Y2.Sincey=Y3/Z3 is a root of the 3-division polynomial ψ3(y)=(a-d)3(a+2ay-2dy3-dy4)/24(1-y)4, we can express d=aZ33(Z3+2Y3)/Y33(2Z3+Y3). Then, we have(28)Y′Z′=YZ2Y32+2Z2Y3Z3+Y2Z32ZZ2Y32+2Y2Y3Z3+Y2Z32.In summary, from the additional input(Y:Z), projective version of (26) gives(29)Y′:Z′=YZ2Y32+2Z2Y3Z3+Y2Z32:ZZ2Y32+2Y2Y3Z3+Y2Z32.Now, leta′ and d′ be the curve coefficients of the image curve. Substituting α2=Z32-Y32/aZ32-dY32 and d=aZ33(Z3+2Y3)/Y33(2Z3+Y3) in (25) represented in projective coordinates, we have(30)a′=aY3+2Z32Y32,d′=aZ3Z3+2Y33Y332Z3+Y3.To avoid inversions, projective versions of (30) are(31)A′=AY3Y3+2Z33,D′=AZ3Z3+2Y33,C′=C2Y332Z3+Y3,where a′=A′/C′ and d′=D′/C′ for a=A/C and d=D/C.


## 3.2. 4 Isogenies on Twisted Edwards Curves

Computing 4 isogenies is more complicated than odd-degree isogenies in twisted Edwards curves. There exist roughly two approaches for computing 4 isogenies in twisted Edwards curves. The first method is to transform twisted Edwards curve to corresponding Weierstrass form and apply Vélu’s formula. However, transforming back to twisted Edwards form from Weierstrass form is complicated as square root computations might be required in some cases. The other approach is to use the birational relation between twisted Edwards curves and Montgomery curves. As the transformation between twisted Edwards curves and Montgomery curves costs only two additions, we can compute 4-isogeny on a Montgomery curve and transform back to a twisted Edwards curve. However, when applying the 4-isogeny formula on Montgomery curves proposed by Jao and De Feo, the isomorphismι that maps 4-torsion point to a specific point must be combined to compute 4-isogeny consecutively [5]. Therefore, after transforming a twisted Edwards curve into a Montgomery curve, the isomorphism must be combined with 4-isogeny.In summary, the composition we used is as follows:(32)Ea,d→ψMA,B→ιMA′,B′→ϕ1MA′′,B′′→ψ′-1Ea′,d′,where ψ and ψ′-1 are birational maps and ϕ1 is an isogeny obtained using Vélu’s formulas.LetP=(X4:Y4:Z4) be a 4-torsion point on twisted Edwards curve Ea,d, represented in projective coordinate. The birational map ψ that maps twisted Edwards curve Ea,d to Montgomery curve MA,B sends P as follows:(33)ψY4:Z4→XM:ZM=Y4+Z4:Z4-Y4,where(34)A=2a+da-d,B=4a-d.LetP′=(XM:ZM) be the corresponding 4-torsion point on MA,B. The evaluation of 4-isogeny ϕ=ϕ1∘ι on MA,B with kernel P′ is defined as in [10].(35)X′:Z′=X2XMZMZ-XXM2+ZM2XMX-ZMZ2:Z2XMZMX-ZXM2+ZM2ZMX-XMZ2.Note that this formula is already combined with the isomorphism ι so that additional transform is not necessary. Finally, the birational map ψ′-1, which maps the Montgomery curve back to the twisted Edwards curve Ea′,d′, is defined as follows:(36)ψ′-1X′:Z′→Y′:Z′=X′-Z′:X′+Z′.The curve coefficientsa′ and d′ of the image curve Ea′,d′ are given by(37)a′=A+2B,d′=A-2B.Combining the three mapsψ, ϕ, and ψ′-1 yields 4-isogeny from Ea,d to Ea′,d′. The equation below is the evaluation of the 4-isogeny by computing Y′:Z′, given the additional point (Y:Z) on Ea,d.(38)Y′=X2XMZMZ-XXM2+ZM2XMX-ZMZ2-Z2XMZMX-ZXM2+ZM2ZMX-XMZ2,Z′=X2XMZMZ-XXM2+ZM2XMX-ZMZ2+Z2XMZMX-ZXM2+ZM2ZMX-XMZ2.Simplifying the above equations by substituting XM=Y4+Z4 and ZM=Z4-Y4, we have(39)Y′=Z2Y42+Y2Z42YZY4+Z42,Z′=Z2Y42+Y2Z422+2Y2Z2Y4Z4Y42+Z42.We now describe the evaluation of the curve coefficients of the image curve. For the 4-torsion pointP=(X4:Y4:Z4) on the twisted Edwards curve Ea,d, birational map is used to transform into the Montgomery form MA,B. The curve coefficients, as well as the image of P and [2]P, are as given below.(40)A=2a+da-d,B=4a-d,ψP=XM:ZM,ψ2P=X0:Z0.Here XM=Y4+Z4,  ZM=Z4-Y4, X0=(XM+ZM)2(XM-ZM)2, and Z0=4XMZM((XM-ZM)2+((A+2)/4)(4XMZM)) in the above equation. Next, the isomorphism ι sends ψ(P) to a point of the form (1,…) and ψ([2]P) to (0,0). The coefficients of the corresponding image curve MA′,B′ are(41)A′=ZM3X0+AZ0XMZ0-ZMX0,B′=BZMZ0XMZ0-ZMX0.Then, by combining the isogenyϕ1, coefficients of the image curve are given below.(42)A′′=-2A′+62-A′=2AZMZ0-3ZMX0+6XMZ0AZMZ0+5ZMX0-2XMZ0,(43)B′′=B′2-A′=-BZMZ0AZMZ0+5ZMX0-2XMZ0.Finally, by applying the birational map to transform back to the twisted Edwards curve, we obtain the coefficients of the 4-isogeny twisted Edwards curve. LetEa′,d′=Ea,d/P be the image curve. Then we have(44)a′=A′′+2B′′=-4AZMZ0+ZMX0+2XMZ0BZMZ0,(45)d′=A′′-2B′′=-16ZMX0-XMZ0BZMZ0.SinceXM/ZM is a root of the 4-division polynomial ϕ4=x4+2Ax3+6x2+2Ax+1 of a Montgomery curve MA,B, we can express A in terms of XM and ZM. Simplifying the above equation with expression in terms of Y4 and Z4, we have(46)A′=AY4+Z44,D′=8AY4Z4Y42+Z42,C′=CY44.


## 4. The Proposed Isogeny Computations on Edwards Curves

In this section, we present 3- and 4-isogeny formulas on Edwards curves. Recall that 2-isogeny on twisted Edwards curves requires square root computation when transforming back to twisted Edwards curves [17]. Hence, we assumed twisted Edwards curves to have a 4-torsion point by restricting the order of the field. However, every elliptic curve having a 4-torsion point is birationally equivalent to Edwards curves [14]. Therefore, twisted Edwards curves having a 4-torsion point are in fact Edwards curves, with the curve coefficient a=1. Since the number of curve coefficients is reduced, the proposed isogeny formulas can further be optimized.


### 4.1. 3 Isogenies on Edwards Curves

LetP=(α,β) be a 3-torsion point on Edwards curve Ed, where β=Y3/Z3. Let ϕ:Ed→Ed′ be a 3-isogeny generated by a kernel P, so that Ed′=Ed/P. Since (29) is independent of the curve coefficients, 3-isogeny formula on Edwards curve is identical to 3-isogeny on twisted Edwards curves. The curve coefficient of the isogenous curve Ed′ is(47)d′=β8d3=Y3Z38Z33Z3+2Y3Y332Z3+Y33=Z3+2Y33Z32Z3+Y33Y3.Therefore, in projective coordinates,(48)D′=Z3+2Y33Z3,C′=2Z3+Y33Y3.


### 4.2. 4 Isogenies on Edwards Curves

Similar to the case for computing 3-isogeny on Edwards curves, only the formula for computing image curve coefficient is changed when computing 4-isogeny on Edwards curves. By settinga=1 and starting from (34), we have(49)D′=8Y4Z4Y42+Z42,C′=Y4+Z44.To conclude, note that all of our formulas are given in terms of projective YZ-coordinates. Since point operations such as doubling and tripling on Edwards curves can be performed by YZ-coordinates, our formulas are well-adjusted to the isogeny-based cryptosystem.


### 4.3. Algorithms for Computing Isogenies on Edwards Curves

This section presents an efficient way to compute three and four isogenies on Edwards curves. In order to evaluate 3-isogeny efficiently, consider the difference betweenY and Z coordinates. Let F=Y′+Z′ and G=Y′-Z′, where Y′ and Z′ are defined as in (29). Then, F and G are given by (50)F=ZY3+YZ32Y+Z,G=ZY3-YZ32Y-Z.Therefore,Y′ and Z′ can be obtained alternatively by computing Y′=F+G and Z′=F-G. To compute the coefficients of the image curve, (48) can be rewritten as(51)D′=Z3+2Y33Z3=Z32+4Y3Z3+4Y32Z32+2Y3Z3,C′=2Z3+Y33Y3=D′+Y32-Z32Y3-Z32.Hence, when valuesZ32,Y32,(Y3+Z3)2, and 2Y3Z3 are computed, D′ and C′ can be computed with two field multiplications. Algorithm 1 shows an efficient way to compute 3-isogeny and its corresponding curve coefficients. The total cost for Algorithm 1 is 6M+5S.Algorithm 1:Computing 3-isogeny on Edwards curves.
Require: 3-torsion point P=(Y3:Z3) and a curve point Q=(Y:Z) on Ed Ensure: Image point Q′=(Y′:Z′) on Ed′ and curve coefficients C′,D′ of the image curve Ed′ where d′=D′/C′ 1:t0←Z⋅Y3//t0=ZY3 2:t1←Y⋅Z3//t1=YZ3 3:t2←t0+t1//t2=ZY3+YZ3 4:t3←Y+Z//t3=Y+Z 5:t2←t22//t2=ZY3+YZ32 6:t2←t2⋅t3//t2=ZY3+YZ32(Y+Z) 7:t0←t0-t1//t0=ZY3-YZ3 8:t0←t02//t0=ZY3-YZ32 9:t1←Y-Z//t1=Y-Z 10:t0←t0⋅t1//t0=ZY3-YZ32(Y-Z) 11:Y′←t0+t2//Y′=2Y(Z2Y32+2Z2Y3Z3+Y2Z32) 12:Z′←t2-t0//Z′=2Z(Z2Y32+2Y2Y3Z3+Y2Z32) 13:c0←Y3+Z3//c0=Y3+Z3 14:c0←c02//c0=Y3+Z32 15:c1←Y32//c1=Y32 16:c2←Z32//c2=Z32 17:c3←c0-c1-c2//c3=2Y3Z3 18:t0←c1+c1//t0=2Y32 19:t0←t0+c1//t0=2Y32+Y32 20:t1←c0+c3//t1=Y3+Z32+2Y3Z3 21:t1←t1+t0//t1=Z32+4Y3Z3+4Y32 22:t0←c2+c3//t0=Z32+2Y3Z3 23:D′←t0⋅t1//D′=Z3+2Y32(Z32+2Y3Z3) 24:t0←c1-c2//t0=Y32-Z32 25:t1←c3+c3//t1=4Y3Z3 26:t1←c0-t1//t1=Y3-Z32 27:t0←t0⋅t1//t0=(Y32-Z32)Y3-Z32 28:C′←D′+t0//C′=2Z3+Y33Y3 29: returnY′,Z′,C′,D′Next, to compute 4-isogeny formula on Edwards curves, letF′=Y′+Z′ and G′=Y′-Z′, where Y′ and Z′ are defined as in (39). Then F′ and G′ can be written as(52)F′=YZY42+Z42+Y2Z42+Z2Y42ZY4+YZ42,G′=YZY42+Z42-Y2Z42+Z2Y42ZY4-YZ42.Therefore,Y′ and Z′ can be obtained alternatively by computing Y′=F′+G′ and Z′=F′-G′. Also, note that D′ in (49) equals to(53)D′=Y4+Z44-Y4-Z44=C′-Y4-Z44.The coefficients of the image curve can be computed more efficiently using the above equation. The algorithm for computing 4-isogeny and its corresponding curve coefficients is described in Algorithm2. The total cost for Algorithm 2 is 7M+5S.Algorithm 2:Constructing 4-isogeny on Edwards curves.
Require: 4-torsion point P=(Y4:Z4) and curve point Q=(Y:Z) on Ed Ensure: Image point Q′=(Y′:Z′) on Ed′ and curve coefficients C′,D′ of the image curve Ed′ where d′=D′/C′ 1:t0←Z⋅Y4// t0=ZY4 2:t1←Y⋅Z4//t1=YZ4 3:t2←t0⋅t1//t2=YZY4Z4 4:t2←t2+t2//t2=2YZY4Z4 5:t3←t0+t1//t3=YZ4+ZY4 6:t3←t32//t3=YZ4+ZY42 7:t5←t3-t2//t5=Y2Z42+Z2Y42 8:t4←Y⋅Z//t4=YZ 9:c0←Y4+Z4//c0=Y4+Z4 10:c0←c02//c0=Y4+Z42 11:t4←t4⋅c0//t4=YZY4+Z42 12:t4←t4-t2//t4=YZ(Y42+Z42) 13:Y′←t4+t5//Y′=YZ(Y42+Z42)+(Y2Z42+Z2Y42) 14:Z′←t4-t5//Z′=YZ(Y42+Z42)-(Y2Z42+Z2Y42) 15:t0←Y′⋅t3//t0=F′ 16:t3←t5-t2//t3=(YZ4-ZY4)2 17:t1←Z′⋅t3//t1=G′ 18:Y′←t0+t1//Y′=2(Z2Y42+Y2Z42)YZY4+Z42 19:Z′←t0-t1//Z′=2Z2Y42+Y2Z422+4Y2Z2Y4Z4(Y42+Z42) 20:C′←c02//C′=Y4+Z44 21:c0←Y4-Z4//c0=(Y4-Z4) 22:c0←c02//c0=Y4-Z42 23:c0←c02//c0=Y4-Z44 24:D′←C′-c0//D′=8Y4Z4(Y42+Z42) 25: returnY′,Z′,C′,D′


### 4.4. Implementation Results

To evaluate the performance of the proposed formulas, the algorithms are implemented in C language. We used the isogeny formula implemented in SIDH library version 3.0 for isogenies on Montgomery curves. Moreover, to make an exact comparison with isogenies on Montgomery curves, the field operations implemented in SIDH library were used for both curves. The field operations in SIDH library are written in x64 assembly [18]. As a result, the difference in performance lies purely in the computation of isogenies. All cycle counts were obtained on one core of an Intel Core i7-6700 (Skylake) at 3.40 GHz, running Ubuntu 16.04 LTS. For compilation, we used GNU GCC version 5.4.0.In this section, the fieldK is fixed as K=Fp2, where p is prime, and Fp2=Fp2[X]/(X2+1). For the prime p, we used 503-bit prime p503=2250·3159-1 and 751-bit prime p751=2372·3239-1, presented in [13, 18]. The base field operations were tested in order to visualize the ratio between field operations. To this end, each field operation was repeated 108 times for each prime field. Table 1 summarizes the average cycle counts of field operations over Fp2.Table 1
Cycle counts of the field operations overFp2.
Field size Addition Subtraction Multiplication Squaring p503 79 62 795 640 p751 120 102 1593 1260As in Table1, 1S equals approximately 0.8M, for both 503-bit prime and 751-bit prime. Based on the above result, Table 2 shows the computational cost and corresponding cycle counts of 3 and 4 isogenies, when using Montgomery curves and Edwards curves. For each isogeny computation, we report the average cycles of 108 times. Note that the number of field multiplications and squarings are same for 3-isogeny. Therefore, to better represent the results, we also counted field additions and subtractions. In Table 2,a (resp.,s) refers to field addition (resp., subtraction).Table 2
Implementation results of 3 and 4 isogenies on Montgomery curves and Edwards curves (cc represents the number of clock cycles).
3-isogeny 4-isogeny p 503 p 751 p 503 p 751 Montgomery curves [18] 6M+5S+14a+5s 6M+6S+7a+4s 8,931 cc 17,833 cc 9,146 cc 16,375 cc Edwards curves (This Work) 6M+5S+11a+7s 7M+5S+4a+7s 8,843 cc 17,644 cc 9,363 cc 16,542 ccNote that the base field operations in [18] run in constant time to protect against timing attacks [24]; field additions cost more cycles than field subtractions. Therefore, 3-isogeny on Edwards curves are slightly faster than on Montgomery curves. Overall, because the proposed algorithms used field subtractions more than field additions, the performance gap between Montgomery curves and Edwards curves is small.


## 4.1. 3 Isogenies on Edwards Curves

LetP=(α,β) be a 3-torsion point on Edwards curve Ed, where β=Y3/Z3. Let ϕ:Ed→Ed′ be a 3-isogeny generated by a kernel P, so that Ed′=Ed/P. Since (29) is independent of the curve coefficients, 3-isogeny formula on Edwards curve is identical to 3-isogeny on twisted Edwards curves. The curve coefficient of the isogenous curve Ed′ is(47)d′=β8d3=Y3Z38Z33Z3+2Y3Y332Z3+Y33=Z3+2Y33Z32Z3+Y33Y3.Therefore, in projective coordinates,(48)D′=Z3+2Y33Z3,C′=2Z3+Y33Y3.


## 4.2. 4 Isogenies on Edwards Curves

Similar to the case for computing 3-isogeny on Edwards curves, only the formula for computing image curve coefficient is changed when computing 4-isogeny on Edwards curves. By settinga=1 and starting from (34), we have(49)D′=8Y4Z4Y42+Z42,C′=Y4+Z44.To conclude, note that all of our formulas are given in terms of projective YZ-coordinates. Since point operations such as doubling and tripling on Edwards curves can be performed by YZ-coordinates, our formulas are well-adjusted to the isogeny-based cryptosystem.


## 4.3. Algorithms for Computing Isogenies on Edwards Curves

This section presents an efficient way to compute three and four isogenies on Edwards curves. In order to evaluate 3-isogeny efficiently, consider the difference betweenY and Z coordinates. Let F=Y′+Z′ and G=Y′-Z′, where Y′ and Z′ are defined as in (29). Then, F and G are given by (50)F=ZY3+YZ32Y+Z,G=ZY3-YZ32Y-Z.Therefore,Y′ and Z′ can be obtained alternatively by computing Y′=F+G and Z′=F-G. To compute the coefficients of the image curve, (48) can be rewritten as(51)D′=Z3+2Y33Z3=Z32+4Y3Z3+4Y32Z32+2Y3Z3,C′=2Z3+Y33Y3=D′+Y32-Z32Y3-Z32.Hence, when valuesZ32,Y32,(Y3+Z3)2, and 2Y3Z3 are computed, D′ and C′ can be computed with two field multiplications. Algorithm 1 shows an efficient way to compute 3-isogeny and its corresponding curve coefficients. The total cost for Algorithm 1 is 6M+5S.Algorithm 1:Computing 3-isogeny on Edwards curves.
Require: 3-torsion point P=(Y3:Z3) and a curve point Q=(Y:Z) on Ed Ensure: Image point Q′=(Y′:Z′) on Ed′ and curve coefficients C′,D′ of the image curve Ed′ where d′=D′/C′ 1:t0←Z⋅Y3//t0=ZY3 2:t1←Y⋅Z3//t1=YZ3 3:t2←t0+t1//t2=ZY3+YZ3 4:t3←Y+Z//t3=Y+Z 5:t2←t22//t2=ZY3+YZ32 6:t2←t2⋅t3//t2=ZY3+YZ32(Y+Z) 7:t0←t0-t1//t0=ZY3-YZ3 8:t0←t02//t0=ZY3-YZ32 9:t1←Y-Z//t1=Y-Z 10:t0←t0⋅t1//t0=ZY3-YZ32(Y-Z) 11:Y′←t0+t2//Y′=2Y(Z2Y32+2Z2Y3Z3+Y2Z32) 12:Z′←t2-t0//Z′=2Z(Z2Y32+2Y2Y3Z3+Y2Z32) 13:c0←Y3+Z3//c0=Y3+Z3 14:c0←c02//c0=Y3+Z32 15:c1←Y32//c1=Y32 16:c2←Z32//c2=Z32 17:c3←c0-c1-c2//c3=2Y3Z3 18:t0←c1+c1//t0=2Y32 19:t0←t0+c1//t0=2Y32+Y32 20:t1←c0+c3//t1=Y3+Z32+2Y3Z3 21:t1←t1+t0//t1=Z32+4Y3Z3+4Y32 22:t0←c2+c3//t0=Z32+2Y3Z3 23:D′←t0⋅t1//D′=Z3+2Y32(Z32+2Y3Z3) 24:t0←c1-c2//t0=Y32-Z32 25:t1←c3+c3//t1=4Y3Z3 26:t1←c0-t1//t1=Y3-Z32 27:t0←t0⋅t1//t0=(Y32-Z32)Y3-Z32 28:C′←D′+t0//C′=2Z3+Y33Y3 29: returnY′,Z′,C′,D′Next, to compute 4-isogeny formula on Edwards curves, letF′=Y′+Z′ and G′=Y′-Z′, where Y′ and Z′ are defined as in (39). Then F′ and G′ can be written as(52)F′=YZY42+Z42+Y2Z42+Z2Y42ZY4+YZ42,G′=YZY42+Z42-Y2Z42+Z2Y42ZY4-YZ42.Therefore,Y′ and Z′ can be obtained alternatively by computing Y′=F′+G′ and Z′=F′-G′. Also, note that D′ in (49) equals to(53)D′=Y4+Z44-Y4-Z44=C′-Y4-Z44.The coefficients of the image curve can be computed more efficiently using the above equation. The algorithm for computing 4-isogeny and its corresponding curve coefficients is described in Algorithm2. The total cost for Algorithm 2 is 7M+5S.Algorithm 2:Constructing 4-isogeny on Edwards curves.
Require: 4-torsion point P=(Y4:Z4) and curve point Q=(Y:Z) on Ed Ensure: Image point Q′=(Y′:Z′) on Ed′ and curve coefficients C′,D′ of the image curve Ed′ where d′=D′/C′ 1:t0←Z⋅Y4// t0=ZY4 2:t1←Y⋅Z4//t1=YZ4 3:t2←t0⋅t1//t2=YZY4Z4 4:t2←t2+t2//t2=2YZY4Z4 5:t3←t0+t1//t3=YZ4+ZY4 6:t3←t32//t3=YZ4+ZY42 7:t5←t3-t2//t5=Y2Z42+Z2Y42 8:t4←Y⋅Z//t4=YZ 9:c0←Y4+Z4//c0=Y4+Z4 10:c0←c02//c0=Y4+Z42 11:t4←t4⋅c0//t4=YZY4+Z42 12:t4←t4-t2//t4=YZ(Y42+Z42) 13:Y′←t4+t5//Y′=YZ(Y42+Z42)+(Y2Z42+Z2Y42) 14:Z′←t4-t5//Z′=YZ(Y42+Z42)-(Y2Z42+Z2Y42) 15:t0←Y′⋅t3//t0=F′ 16:t3←t5-t2//t3=(YZ4-ZY4)2 17:t1←Z′⋅t3//t1=G′ 18:Y′←t0+t1//Y′=2(Z2Y42+Y2Z42)YZY4+Z42 19:Z′←t0-t1//Z′=2Z2Y42+Y2Z422+4Y2Z2Y4Z4(Y42+Z42) 20:C′←c02//C′=Y4+Z44 21:c0←Y4-Z4//c0=(Y4-Z4) 22:c0←c02//c0=Y4-Z42 23:c0←c02//c0=Y4-Z44 24:D′←C′-c0//D′=8Y4Z4(Y42+Z42) 25: returnY′,Z′,C′,D′


## 4.4. Implementation Results

To evaluate the performance of the proposed formulas, the algorithms are implemented in C language. We used the isogeny formula implemented in SIDH library version 3.0 for isogenies on Montgomery curves. Moreover, to make an exact comparison with isogenies on Montgomery curves, the field operations implemented in SIDH library were used for both curves. The field operations in SIDH library are written in x64 assembly [18]. As a result, the difference in performance lies purely in the computation of isogenies. All cycle counts were obtained on one core of an Intel Core i7-6700 (Skylake) at 3.40 GHz, running Ubuntu 16.04 LTS. For compilation, we used GNU GCC version 5.4.0.In this section, the fieldK is fixed as K=Fp2, where p is prime, and Fp2=Fp2[X]/(X2+1). For the prime p, we used 503-bit prime p503=2250·3159-1 and 751-bit prime p751=2372·3239-1, presented in [13, 18]. The base field operations were tested in order to visualize the ratio between field operations. To this end, each field operation was repeated 108 times for each prime field. Table 1 summarizes the average cycle counts of field operations over Fp2.Table 1
Cycle counts of the field operations overFp2.
Field size Addition Subtraction Multiplication Squaring p503 79 62 795 640 p751 120 102 1593 1260As in Table1, 1S equals approximately 0.8M, for both 503-bit prime and 751-bit prime. Based on the above result, Table 2 shows the computational cost and corresponding cycle counts of 3 and 4 isogenies, when using Montgomery curves and Edwards curves. For each isogeny computation, we report the average cycles of 108 times. Note that the number of field multiplications and squarings are same for 3-isogeny. Therefore, to better represent the results, we also counted field additions and subtractions. In Table 2,a (resp.,s) refers to field addition (resp., subtraction).Table 2
Implementation results of 3 and 4 isogenies on Montgomery curves and Edwards curves (cc represents the number of clock cycles).
3-isogeny 4-isogeny p 503 p 751 p 503 p 751 Montgomery curves [18] 6M+5S+14a+5s 6M+6S+7a+4s 8,931 cc 17,833 cc 9,146 cc 16,375 cc Edwards curves (This Work) 6M+5S+11a+7s 7M+5S+4a+7s 8,843 cc 17,644 cc 9,363 cc 16,542 ccNote that the base field operations in [18] run in constant time to protect against timing attacks [24]; field additions cost more cycles than field subtractions. Therefore, 3-isogeny on Edwards curves are slightly faster than on Montgomery curves. Overall, because the proposed algorithms used field subtractions more than field additions, the performance gap between Montgomery curves and Edwards curves is small.


## 5. Conclusion and Future Work

In this paper, we proposed 3- and 4-isogeny formulas on twisted Edwards curves that can be applied in isogeny-based cryptography. For 3-isogeny, we optimized Moody and Shumow’s formula by applying projective coordinates, projective curve coefficients, and division polynomials [17]. For even-degree isogeny, we combined bilinear map between twisted Edwards curves and Montgomery curves and isogeny on Montgomery curves. We further optimized our isogeny formulas by working on with Edwards curves. The computational costs for 3 and 4 isogenies on Edward curves are 6M+5S and 7M+5S, respectively. We also implemented our formulas and demonstrated that isogenies on Edwards curves are as efficient as isogenies on Montgomery curves. For the future work, we plan to implement our isogeny formulas on isogeny-based cryptosystem and measure its performance. Additionally, we plan to consider isogeny formulas on other forms of elliptic curves and report the best isogeny degree for isogeny-based cryptography.



---

*Source: 5747642-2018-07-15.xml*