Computing of Odd Degree Isogenies on Supersingular Twisted Edwards Curves

Abstract

An overview of the properties of three classes of curves in generalized Edwards form Ea,d with two parameters is given. The known formulas for the odd degree isogenies on curves Ed with one parameter are generalized to all classes of curves in Edwards form, and Theorem 1 on the isogenic mapping of the points of these curves is proved. The analysis of the known effective method for computing isogenies in Farashahi-Hosseini w-coordinates, justified for the curve Ed, is given. Theorem 2 proves the applicability of this method to the class of twisted Edwards curves. Examples of 3- and 5-isogenies of twisted Edwards curves are given. Methods for bypassing the exceptional points of such curves in PQC cryptosystems like CSIDH are proposed.

Keywords

• 1 Generalized Edwards form curve
• complete Edwards curve
• twisted Edwards curve
• quadratic Edwards curve
• curve order
• points order
• isomorphism
• isogeny
• w-coordinate
• quadratic residue
• quadratic nonresidue

1. Introduction

Recently, there has been significant progress in the prospects for post-quantum cryptography (PQC) on isogenies of supersingular elliptic curves. An effective alternative to the well-known Supersingular Isogeny Diffie-Hellman (SIDH) [1] protocol is the new faster algorithm with a very short key length— Commutative SIDH (CSIDH) [2]. It offers a non-interactive key exchange protocol based on Alice and Bob’s secret keys. Instead of the extended field 2 in SIDH, operations in CSIDH are performed over a prime field , which for the given halves the length of the field elements and key sizes. Instead of the acyclic curve in SIDH with subgroups of 2i and 3k of higher orders in CSIDH, the elliptic curve contains cyclic subgroups of simple odd-order l1,l2,..,lmax, where lmax is specified by the security level.

The implementation of SIDH and CSIDH algorithms was mainly based on the fastest arithmetic of isogenies of curves in Montgomery form or mixed arithmetic of curves in Montgomery and Edwards form. In [3], a new effective method for computing odd degree isogenies on Edwards curves based on Farashahi-Hosseini w-coordinates [4] was proposed. This work, in turn, is based on Montgomery’s method of differential points addition and adapts it to Edwards curves. The formulae for computing of odd degree isogenies on Edwards curves [5] also contain components of differential points addition, which allowed in [3, 4] with the help of w-coordinates to align the speeds of performing the corresponding operations on the curves in the Montgomery and Edwards forms. The results of the implementation of the CSIDH algorithm on Edwards curves [3] are already ahead of the closest competitor.

To work of the authors [3] was preceded their article [6], in which, in particular, an efficient algorithm for computing 3-isogenies in projective coordinates was developed with the minimal computation cost for today. However, for 5-isogenies, as our analysis showed [7], computations in classical projective coordinates became almost three times more complicated. There are reasons to consider the use of Farashahi-Hosseini w-coordinates and the method [3] as a method for optimal computation of odd degree isogenies on Edwards curves.

Complete Edwards curves with one parameter , defined in [8] ( ( )= −1), have well-known advantages: maximum exponentiation rate of a point, the universality of points addition law, affine coordinates of a neutral element of a group. The introduction of the second parameter on the curve , in [9] expanded the class of curves in the Edwards form and gave rise, according to the classification adopted in [10], to two new classes: twisted and quadratic Edwards curves. The last class, together with complete ones in terminology [9], is called Edwards curves .

The computing of odd degree isogenies on Edwards curves is carried out using the formulas defined by Theorems 2–4 in [5]. Although Theorem 3 of this paper is formulated for normalized Edwards curves , → 1, / , its existence condition for √ is not satisfied in the class of twisted Edwards curves over a prime field . In other words, isogenic mapping , → ′ , remained unknown for this class. One of the goals of this paper is to fill this gap and to prove Theorem 1 with a generalization of results known for curves to curves , over a prime field .

Further, in the work [3], based on Farashahi-Hosseini w-coordinates, a method for computing of odd degree isogenies for Edwards curves were developed and implemented, and Theorems were proved for isogenic mappings of these curves. But the question remained whether this method works in the existing conditions of twisted Edwards curves , . Theorem 2 in this article puts an end to this question as well.

Our analysis in this paper is based on the properties of twisted and quadratic Edwards curves connected as pairs of quadratic twists [10, 12]. Supersingular curves of these classes with a similar order = + 1 = 2 , ≥ 3 (n is odd) exist only for = 3 mod4 [11]. The minimum even cofactor of the order of such curves is 8, then for CSIDH algorithm with odd = ∏ m=1ax the field modulus should be chosen as = 8 − 1. To adapt the definitions for the arithmetic of isogenies on Edwards curves and curves in Weierstrass form, we use a modified points addition law [10, 13].

Sect. 2 gives a brief overview of the properties of three classes of Edwards curves according to the classification [10]. In Sect. 3, we consider the properties of odd degree isogenies and prove Theorem 1 for a rational mapping , → ′ ′, ′ expressed by functions of two and one variables, and give examples of isogenies on twisted Edwards curves. In Sect. 4, based on Theorem 1, Theorem 2 is formulated and proved for the isogenic mapping of the curve , in Farashahi-Hosseini w-coordinates. Estimates of the cost of computing isogenies in projective coordinates ( : )[3] are given. Examples are considered for classes of quadratic and twisted Edwards curves and methods are proposed to bypass the exceptional points of the 2nd order on twisted Edwards curves.

2. Classes of Curves in the Generalized Edwards Form

The elliptic curve in the generalized Edwards form [10] is determined by the equation , : 2 + 2 = 1 + 2 2, , ∈ ∗, ≠ 1, ≠ , ≠ 2. ( 1 ) In contrast to the equation of this curve in [9], here we multiply the parameter by 2 instead of 2. With the quadratic character ( )= −1, the curve ( 1 ) is isomorphic to the complete Edwards curve [8] with one parameter

: 2 + 2 = 1 + 2 2, ( )= −1, ≠ 0,1. ( 2 )

In the case ( )= ( )= 1, there is an isomorphism of the curve ( 1 ) with quadratic Edwards curve [10]

: 2 + 2 = 1 + 2 2, ( )= 1, ≠ 0,1, ( 3 ) which, in contrast to ( 2 ), has the parameter defined as a square. This difference leads to radically different properties of curves ( 2 ) and ( 3 ) [10], which are summarized below. Despite this, in world literature, these classes of curves are often combined by the general term Edwards curves [9].

In our paper [13], we proposed to change places of and coordinates in the form ( 1 ) of the Edwards curve. The modified universal law of addition of the points of the curve ( 1 ) has the form: 1 2 + 2 1 ).

( 4 ) ( 1, 1)+ ( 2, 2)= ( 1 2 − 1 2 ,

1 − 1 2 1 2 1 + 1 2 1 2

If two points from ( 4 ) coincide, we have 2( 1, 1)= ( 12 − 12 , 1 − 12 12 1 + 12 2 1 1

12). 1,2 = (±√ , ∞), ± 1 = (∞, ±

), 1 √ Determining the inverse point as −

= ( 1, − 1)we obtain according to ( 4 ) the coordinates of the neutral element

= ( 1,0 )of the group of points. In addition to the neutral element , the axis also always contains the point 0 = (−1,0)of the 2nd order, such that 2 0 = ( 1,0 )= . Depending on the properties of the parameters

and , we can get two exceptional points of the 2nd order and two exceptional points of 4th order with the coordinates: respectively. ( 1 ) are divided into 3 disjoint classes [10]: where we put the sign ∞ when dividing by 0. They arise in the cases ( )= 1 and ( )= 1, Depending on the properties of the parameters and , the curves in the generalized Edwards form ( 5 ) ( 6 ) ( 7 )

Complete Edwards curves with the conditions C1: (

)= −1.

Twisted Edwards curves with the conditions C2.1: ( )= ( )= −1.

Quadratic Edwards curves with the conditions C2.2: ( )= ( )= 1 [14–16].

Basic properties of curves of these classes:

For the points of the 2nd order, the class of complete Edwards curves over a prime field is the class of cyclic curves (with one point of the 2nd order), while twisted and quadratic Edwards curves form classes of acyclic curves (three points of the second-order each). The maximum order of points of curves of the two last classes is equal to ⁄ .

2

The class of complete Edwards curves does not contain exceptional points.

Twisted Edwards curves contain two exceptional points of the 2nd order 1,2 = (±√ , ∞), and

This parameter distinguishes between isogenic (with different J-invariants) and isomorphic (with equal J-invariants) curves.

3. Odd Degree Isogenies on Twisted Edward Curves

The isogeny from the elliptic curve ( )over the field to the curve ′( )is a homomorphism ( )+ ( )and that there are rational functions [17] ( , )= (

) = ( ′, ′), ( ) ( ) , ( ) ( ) quadratic Edwards curves, besides them, contain two more exceptional points of the 4th order ± 1 = (∞, ± √1 ). transformations: ̃ = , ̃ = , ( )= −1. isomorphism of curves , ~ , .

Twisted and quadratic Edwards curves form quadratic twist pairs based on parameters In the classes of twisted and quadratic Edwards curves, the replacement ↔ gives the Complete and quadratic Edwards curves are isomorphic to the curves with the parameter = 1: , ~ 1, / = ̃ . The introduction of the new parameter into the equation of the curve ( 1 ) is necessary only for the class of twisted Edwards curves.

For the curve ( 1 ) J-invariant is equal to [17] ( , )= 16( 2 + 2 + 14 , ( − )≠ 0.    mapping the points of curve to the points of the curve ′. The maximum of the degrees = deg ( , )= max{deg ( ), deg ( )} is called the degree of isogeny and its kernel ker = is the subgroup

⊆ , the points of which are mapped by the function ( , )into the neutral element of the group ′. The degree of separable isogeny is equal to the order of its kernel. at = 1.

We define

points ± = ( , ± )on the curve .

Isogeny compresses the set of the curve points by a factor ( points of the curve are mapped to one point of the curve ′). At

= isogeny becomes the isomorphism with the degree 1.

The construction of odd degree isogenies on Edwards curves is based on Theorem 2 [5]. Let’s formulate it taking into account the modification ( 4 ) of the points addition law of the curve ( 1 ) Theorem 2 [5]. Let = {( 1,0 ), ± 1, ± 2, . . , ± } the subgroup of odd order = 2 + 1 of the ( )= (∏ ∈ − ∈

+ − , ∏ + ). ′ = 8 and the mapping function

Then ( , )is -isogeny with the kernel from the curve to the curve ′ ′ with the parameter ( , )= ( 2 ∏ =1 ( )2 − ( )2 1 − ( ) ( )= ( ′, ′)= (∏ ∈ − ∈

− + − , ∏

+ − ). ′ = , ′ = 8 , = ∏ =1 and the mapping function

Then ( , )is -isogeny with the kernel from the curve , to the curve ′ ′, ′ with parameters ± = ( , ± ), so for coordinates pairs we have

Its proof is given in [5]. Its important consequence is that isogenic curves are in the same classes as curves (i.e., complete Edwards curves are mapped to complete curves, twisted curves—to twisted ones, and quadratic curves—to quadratic ones). This essentially distinguishes odd degree isogenies from 2-isogenies (for them, the complete Edwards curves are mapped to quadratic ones).

The formula ( 8 ) for the function ( , )directly follows from the definition ( )in the statement of the Theorem and the addition law ( 4 ) for the arbitrary point ( , )= ( , )with the kernel points + − = − 1 ( )2 − ( )2 2 1 − ( , + − = − 1 ( )2 − ( )2 2 1 − ( 2 ) .

The factors x and y before the products in the coordinates of the function ( , )take into account the neutral element

= ( 1,0 ) of the isogeny kernel. It is obvious from ( 8 ) that the property ( 1,0 )= ( 1,0 ) holds, i.e. the neutral element is mapped into itself. For all points of the kernel (± )= ( , ± )= ( 1,0 )is also true. √

Theorem 2[5] and the mapping ( 8 ) are valid only for the classes of complete and quadratic Edwards curves with the parameter

= 1. The authors of [5] further formulated and proved Theorem 3 for curves , in the form ( 1 ), relying on the property of normalization of this curve with isomorphism , ~ 1, / with the change of the coordinate → ⁄ . For the class of twisted Edwards curves ( ( )= ( )= −1) over a prime field such a change does not exist, and the results of Theorem

3[5] are applicable only for the curves over the extended fields ,

≥ 2. For the PQC protocol SIDH [1] with implementation on the curves over the field 2 Theorem 3 [5] may be useful. But for the CSIDH protocol [2] with curves over the field , this theorem does not give results for the whole class of twisted Edwards curves. In this paper, we fill this gap and for the first time present mapping formulas ( )for the curve ( 1 ) that depends on two parameters and .

Theorem 1. Let = {( 1,0 ), ± 1, ± 2, . . , ± } is a subgroup of odd order = 2 + 1 of the points ± = ( , ± )of the curve over the field .

We define 4

( 8 ) ( 9 ) of the first coordinate ′in ( 9 ), each factor is transformed as:

From ( 1 ) it is true that 2 = (1 − 2)/( − 2), 2 + 2 = 1 + 2 2. Then, in the numerator = 2 2 − 2 2 = 2 2 − 2 2 1−− 22 =

Similarly, we transform the factors of the common denominator of coordinates ′and ′into ( 9 ): = 1 − ( )2 = 1 − 2 2

2 2 1 − 2 − 2 = − 2 − 2 2 2 2 + 2 2

2 4 − 2 = or the curve ( 1 ).

Proof. The formula ( 9 ) follows directly from the definition ( )and the points addition law ( 4 ) of

−2 − 22).

After reducing the common factors for the ′-coordinate, we obtain

The second coordinate ′in ( 9 ) as factors in the numerator = ( )2 − ( )2 = 2(1 − 2)− 2 2( − 2) = Then = − 2( 2 + 2 2)+ 2 4 + 2 = − 2 −( 2 − 2)(1 − 2 2)

− 2 = As a result, the function ( 9 ) can be written in the equivalent form ( 10 ) ( , )= ( 2 ∏ =1 2 − 2 , 1 − 2 2 2 ∏ −

and . Formulas for the parameters of the isogenic curve ′ = , ′ = 8 , =

∏

=1 are proved in Theorem 3 [5]. The theorem is proved.

For the curves with the parameter = 1 the formula ( 10 ) is given in Theorem 4 [5]. In this paper, we generalized it for the curves , ( 1 ) with the arbitrary value ≠ , which allows us to compute the isogenies of twisted Edwards curves ( ( )= ( )= −1).

Let’s note that the rational function ( 10 ) corresponds to the classical form ( 7 ). Its obvious advantage over ( 9 ) is its simplicity and minimal computational complexity in affine coordinates. Also, the degree of isogeny as the maximum degree of the polynomial ( )in ( 7 ) is immediately defined as = 2 + 1. The form ( 1 ) of the Edwards curve with the addition law ( 4 ) adapts it to the definitions of isogenies in the Weierstrass form [17].

Let’s consider examples of isogenies of the supersingular twisted Edwards curve (STEC). Such curves exist only at ≡ −1 mod8 and have the order = + 1 ∈ {8 , 16 , … } ( is odd). The curve, for example, contains kernels of the 3rd and 5th order at the smallest value = 15, then the minimum prime number is = 239 and the order of such curve is = 16 = 240. The parameters of the entire family of 118 twisted Edwards curves can be taken as quadratic non-residues = −1, = − 2 mod ,

= 2. .119. Of these, there are 30 STEC’s with the parameters (− ), given in Table 1. They are written as squares in ascending order

For the first curve ( 1 ) −1,−25 = (0, ) from Table 1 we can construct 3- and 5-isogenies and find chains of isogenic curves −( 1), , = 1,2, …, such that , ( ) = (0, ). Then the chain of mappings ( 2 )∘ ( 3 )∘ … ∘ ( )gives dual isogeny −( 11 ), 1 → −(01), 0. The parameter of all isogenic STEC’s can be fixed as the quadratic non-residue = −1, since according to Theorem 3 [5] ( +1) = ( ( )) = −1 for all odd degrees .

The curve −1,−25 contains the point of the 3rd order 1 = (149,64), then according to

Theorem 3[5],

=

∏ =1 = 149, 8 = 8, ( 1 ) = 8( (0))3 = 8 3 = −3.

The calculated parameters − ( ), ( ( ))of the chain of 3-isogenous curves with the starting value = −25 are given in Table 2. The period of the chain = 5 divides the number of all STEC’s equal to 30. Specifying the starting value = −2 not included in Table 2, it is possible to obtain a different sequence − ( ) ∈ {2,61,62,193,5,2} with period 5 with the elements from Table 1 for all STEC’s. For 3-isogenies, we can calculate 6 tables similar to Table 2 with disjoint values − ( )Table 1. We note that all J-invariants ( ( ))of adjacent 3-isogenic curves (except the last pair) are different, i.e. they are not isomorphic.

However, inside the chain, there may be isomorphic curves with equal J-invariants.

The kernel of 5-isogeny on the curve −1,−25 is the subgroup of points of the 5th order ± 1 = ( 1, ± 1)= (−95, ±28), ± 2 = ( 2, ± 2)= (−72, ±119), and 5 1 = = ( 1,0 ). It is uniquely determined by the coordinates 1, 2 of two points and equation ( 1 ). Then for each 5-isogenic curve, we compute ( ) = 1( ) ( ) 2

, ( +1) = ( ( ))8( ( ))5, = 0,1, …. The results of calculations of the parameters of the chain of 5-isogenic curves are given in Table 3. The period of this chain is = 15, so we can build one more similar table (up to a cyclic shift) with the other half of the parameters of , 2( ) 103, −88 79, −91 mapping ( 10 ) of the points = ( , ) of the curve −1,−25 with the kernel = {( 1,0 ), ± 1 = (−90, ±64)} of 3-isogeny has the form:

= ( 3,75 )of the curve −1,−25 is mapped by this function to the point ′ = (−116,94)of the 40th order of the curve ′−1,−3. The point of the maximum odd 15th order

= (−44, −12) is mapped to the point ′ = (−18, −114) of the 5th order, the point = (−95,28)of the 5th order is mapped to the point ′ = (25, −66)of the 5th order, and the point = (−90,64)of the 3rd order is mapped to the point ′ = ( 1,0 )= . As we can see, the function 3( , ) reduces by 3 times the orders of the domain points, which are multiples of 3, and does not change the orders of the other points. In subgroups of orders multiples of 3, three points are mapped into one (surjection property).

For the same curve −1,−25 with the kernel of the 5th order = {( 1,0 ), ± 1 = (−95, ±28), ± 2 = (−72, ±119)} 5-isogeny in the form ( 10 ) is written as 5( , )= ( 2 1 + 252642 2 1 − 252952 2 , 2 1 + 2521192 2 1 − 252722 2),

The point of the 120th order = ( 3,75 )of the curve −1,−25 is mapped by this function to the point ′ = (−116,94)of the 24th order of the curve ′−1,−2. The point mapped to the point ′ = (18, −7)of the 6th order. The point of the 5th order = ( 8, −16 )of the 30th order is = (−95,28)is mapped to the point ′ = ( 1,0 )= , Here, too, in subgroups of orders multiples of 5, five points are mapped into one. 4. The Computing of Isogenies on Supersingular Twisted Edwards Curves in Projective Coordinates of Farashai-Hosseini

Significant progress has been made in the efficiency of computing odd degree isogenies on Edwards curves in paper [3]. It is based on the idea of the method of differential addition (i.e., the addition of two points with the known difference) on the curve in the Farashahi-Hosseini projective coordinates [4]. Since the formulae of isogenies [5] contain the coordinates of the point pairs ± as multipliers, it is possible to obtain results for the isogenies similar to the results of the differential addition on the curve. parameters ′ = , ′ = 8 , = ∏ =1 , and the mapping function

In the paper [3], Theorem 1 was proved, which determines the odd degree isogenic mapping from Edwards curve to the curve ′ in Farashahi-Hosseini coordinates ( , )= 2 2 (or ( , )= 2/ 2). As in the paper [5], it is proved only for the Edwards curve ( = 1), and it is not known whether its results are applicable in the class of twisted Edwards curves , ( ( )= ( )= −1). Below we prove this theorem for all curves in the generalized form , ( 1 ). Instead of the formula ( 8 ) taken as a basis in [3], we proceed from the more laconic formula ( 10 ) obtained above in Theorem 1.

Theorem 2. Let

= {( 1,0 ), ± 1, ± 2, … , ± } is the subgroup of odd order = 2 + 1 of the points ± = ( , ± )of the curve , ( 1 ). Let = 2 2, = 2 2, = ( , )∈ , . Then ( ( , ))= ( ′, ′)is -isogeny with the kernel from the curve , to the curve ′ ′, ′ with the ( )=

∏ sign of the product of isogeny ( 10 ) have the form:

Proof. From the equation of the curve ( 1 ) we have 2 + 2 = 1 + 2 2. The factors under the ( 11 ) Substitution in the last equations 2 = 1 +

− 2 gives: 2 = 2 − (1 + )+ 2 = 2 −

− + (1 + − 2)= 2 = 2 − (1 + )+ 2 = (1 +

− 2)− − + 2 = 2 − (1 + )+

2, 2 − (1 + )+ 2. = (

− )( 2 − 1), = (1 − )( 2 − 1). 2 respectively, we obtain:

Let’s denote the products of numerators and denominators:

= = ( 2 − 2)( 2 − 2), = = (1 − 2 2)( − 2 2).

Then, taking into account 2 + 2 = 1 + and the multiplying of these equations by 2 and = = =1 =1

Then

= −1 − , 1 −

The theorem is proved.

equation of the curve ( = ) = − 2 mod ,

We emphasize that isogeny ( 11 ) for w-coordinate , ( 1 ) does not depend on the parameter a and is equally valid for quadratic and twisted Edwards curves forming quadratic twist pairs [10]. In other words, function ( 11 ) maps the curve points of one of these two classes to the curve points of the same class.

Let’s take as an example the 3-isogeny of the twisted curve −1,−25 of the previous section and its point = ( 3,75 )of the 120th order. For it, we will receive the coordinate = −25 ∙ 32 ∙ 752 = 119. For the kernel point 1 = (149,64), respectively, 1 = −25 ∙ 1492 ∙ 642 = −60. According to the formula ( 11 ) ( ( ))= 78 the point of the isogenic curve ′−1,−3, calculated by the formula ( 10 ), is the point of the 40th order ′ = (−116,94). For it, the coordinate ( ( ))= ′( ′ ′)2 = 78 coincides with the calculations by formula ( 11 ).

Let’s now turn to the quadratic curve 1,25 = 25 as a pair of quadratic torsion of the curve −1,−25. All points of this pair of curves have different coordinates (except for the points (±1,0)) and, accordingly, the curve 25 has the different kernel of the 3rd degree = {( 1,0 ), ± 1 = (97, ±14)}.

Characteristically, the parameter of the isogenic curve ′ = ( 1 ) = 8 (0)3 = 978253 = 110 also changes. For the curve 25 the mapping ( 10 ) of the point of the 120th 40th order ′ = (−16,57)on the isogenic curve 110. For point = (20,108)is the point of the we obtain the coordinate = 25 ∙ 202 ∙ 1082 = 113, for the point of the kernel 1 = 25 ∙ 972 ∙ 142 = 44, respectively. According to formula ( 11 ) ( ( ))= 100. For the point ′ = (−24,57) the w-coordinate is ( ( ))= 110 ∙ 242 ∙ 572 = 100. This corresponds to Theorem 2 and the formula ( 11 ).

The implementation of computing of isogenies ( 11 ) is given in [3]. To calculate the parameters ( ) of the chain of isogenies in projective coordinates, an additional parameter is introduced into the ( 2 ) or ( 3 ). For STEC ( 1 ) at ≡ 3 mod4, we accept = −1, To calculate the parameter ′ of the isogenic curve the formula [5] is used:

∈ {2. . ( − 1)/2} and define the curve: , : 2 − 2 = + 2 2, =

, ( )= −1.

2 ∏ ( ) = −2 ∏ (

2 ) = −2 ∏ As a result, for -isogeny ( 10 ) taking into account the value of the parameter of the isogenic curve ( ( ))= ′( ′ ∙ ′)2 = 8 2 +1 2 2 −8 ∏ ( ) = = 2 2 ∏ (

2 ) = ∏ =1 ′ = 8 , = ∏ , = 2 + 1. ( 12 ) ( 13 )

with the replacement → in [3], the idea of doubling the kernel points is proposed, which does not change the points of subgroups of odd order . From the law of doubling ( 5 ) we have

By squaring the second coordinate, we obtain ′ = ∏ =1 (1 + )8 44 ( , − )= ( , )and for such a pair of points = . Then the formula ( 13 ) takes the form Here we take into account that for each point of the kernel ( , )there exists the reverse point Transition to projective coordinates ( : )allows avoiding inversions in the formula ( 11 ), thus for the curve ( 12 ) then

Here 4 + 2

+ 2 operations in the field are performed for every ( is multiplication, is squaring). If we enter intermediate formulas:

∏( =1 ′ = − )2 , ′ = ∏( −

2 ) .

= ( = ( + )( − ), − )( + ), 2 ′ = ∏( − )2 , 2 ′ =

∏( − )2. ( 2 ) = 1 + 2 4 −1 (1 + )2 = 2 ⟹ 2 2 =

(1 + )2 ⟹ 2 = =1 =1 2

of the isogenic curve ( 12 ) in projective coordinates

And we need only 4

+ 2 operations when calculating one isogeny ( 11 ). according to ( 14 ) we obtain

For calculating the parameter ′ = ′⁄ ′ ′ = ∏( + )8, ′ = ∏(2 ) .

8

Therefore, for the small degrees of isogenies = 2 + 1 ≤ 9( ≤ 4)in each of these formulae, it is enough to perform three squares, within which to substitute values and at different steps. Herewith the cost of calculations is determined by the linear function 2( + 1) + 6 . With the degree of isogeny > 9 additional operations

and are required, the number of which needs an estimate.

Within the limits of the linear trend (lower value), the total cost of calculating -isogenies in Farashahi-Hosseini coordinates [3] is 2(3 + 1) + 8 (the formula of the trend is obtained in this paper). For example, at = 3 and = 5 we obtain 8 + 8 and 14 + 8 , respectively. The calculation of these isogenies in the classical projective coordinates ( : )gives in [6] the best result 6 + 5 for 3-isogenies and the worst result 21 + 12 for 5-isogenies in [7]. With the growth of the calculations of isogenies in coordinates ( : )become significantly more complicated.

Supersingular twisted and quadratic Edwards curves with the same order

= + 1, as follows from Sect. 2, have different structures [10]. STEC has only two exceptional points of the 2nd order, and in the class of quadratic curves, two more exceptional points of the 4th order ( 6 ) are added to them as points in the STEC class, which makes them preferable to quadratic ones in cryptosystems. well as two non- exceptional points of the 4th order ± 0 = (0, ±1). It is easier to bypass exceptional For this purpose, for STEC with the order of the curve with the minimum even cofactor = 8 ( is odd), it is sufficient to select the base point of Alice and Bob as the point of order n or maximum order 4 at the stage of selection of system-wide parameters. In the latter case, quadratic curves are not acceptable, because the mappings to points of the 4th order are possible. At the same time, it is clear for the twisted Edwards curves that with such a choice no chain of isogenies of odd degrees will generate the point of the 2nd order. Another solution to this problem may be to select the point from one of the ( 14 ) three subgroups of the curve that don`t contain exceptional points (they are replaced in this subgroup by the ordinary point of the 2nd order 0 = (−1,0)).

The results of the implementation of the Edwards-CSIDH model [3] in projective coordinates ( : )claim that it is 20% faster than the Montgomery-CSIDH model in coordinates ( : ). It should be noted that this model is built on complete Edwards curves with the order = + 1 = 4 With the same success, it can be realized on supersingular twisted Edwards curves with the order = 8 . Quadratic Edwards curves with redundant exceptional points of the 4th order are outside the recommended range.

5. Conclusions

It can be concluded that the method of computing odd degree isogenies in coordinates ( : ), proposed in [3], using supersingular complete and twisted Edwards curves, allows implementing the fastest calculations to date in the construction of the PQC of protocol CSIDH and the like. The theorems proved in this paper open a class of twisted Edwards curves for their implementation.

6. References

[15] A. V. Bessalov, Calculation of parameters of cryptic curves Edwards over the fields of 5th and 7th characteristic, Cybersecur. Educ. Sci. Tech. 1 (2018) 94–104. doi:10.28925/2663-4023.2018.

1.94104. [Publication in Ukrainian].

[16] A. Bessalov, et al., 3- and 5-isogenies of supersingular Edwards curves, Cybersecur. Educ. Sci.

Tech. 4( 8 ) (2020) 6–21. doi:10.28925/2663-4023.2020.8.621. [17] L. Washington, Elliptic Curves. Discrete Mathematics and Its Applications, 2008. doi:10.1201/9781420071474.

References

[1] D. Jao , L. de Feo, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies , Lect. Notes Comput. Sci . 7071 ( 2011 ) 19 - 34 . doi: 10 .1007/978-3- 642 -25405- 5 _ 2 .

[2] W. Castryck , et al., CSIDH: An efficient post-quantum commutative group action , in: Advances in Cryptology-ASIACRYPT , 2018 , pp. 395 - 427 . doi: 10 .1007/978-3- 030 -03332-3_ 15 .

[3] S. Kim , et al., Optimized method for computing odd-degree isogenies on Edwards curves , in: Advances in Cryptology-ASIACRYPT , 2019 , pp. 273 - 292 . doi: 10 .1007/978-3- 030 -34621- 8_ 10 .

[4] R. R. Farashahi , S. G. Hosseini, Differential addition on twisted Edwards curves , Lect. Notes Comput. Sci . 10343 ( 2017 ) 366 - 378 . doi: 10 .1007/978-3- 319 -59870-3_ 21 .

[5] D. Moody , D. Shumow, Analogues of Velu's formulas for isogenies on alternate models of elliptic curves , Math. Computation 85 ( 300 ) ( 2015 ) 1929 - 1951 . doi: 10 .1090/mcom/3036.

[6] S. Kim , et al., Efficient isogeny computations on twisted Edwards curves , Secur. Commun. Netw . 2018 ( 2018 ). 1 - 11 . doi: 10 .1155/ 2018 /5747642.

[7] A. Bessalov , V. Sokolov , P. Skladannyi , Modeling of 3- and 5-isogenies of supersingular Edwards curves , in: Proceedings of the 2nd International Workshop on Modern Machine Learning Technologies and Data Science, June 2-3 , 2020 , no. I, vol. 2631 , pp. 30 - 39 .

[8] D. J. Bernstein , T. Lange , Faster addition and doubling on elliptic curves , Lect. Notes Comput. Sci . 4833 ( 2007 ) 29 - 50 . doi: 10 .1007/978-3- 540 -76900- 2 _ 3 .

[9] D. J. Bernstein , et al., Twisted Edwards curves, Lect. Notes Comput. Sci . 5023 ( 2008 ) 389 - 405 . doi: 10 .1007/978-3- 540 -68164-9_ 26 .

[10] A. V. Bessalov , Edwards Elliptic Curves and Cryptography , 2017 . [Publication in Russian].

[11] A. V. Bessalov , L. V. Kovalchuk , Supersingular twisted Edwards curves over prime fields. II. Supersingular twisted Edwards curves with the J-invariant equal to 663, Cybern . Syst. Anal . 55 ( 5 ) ( 2019 ) 731 - 741 . doi: 10 .1007/s10559-019-00183-y.

[12] A. V. Bessalov , O. V. Tsygankova , Number of curves in the generalized Edwards form with minimal even cofactor of the curve order , Probl. Inf. Transm . 53 ( 1 ) ( 2017 ) 92 - 101 . doi: 10 .1134/s0032946017010082. [Publication in Russian].

[13] A. V. Bessalov , O. V. Tsygankova , Interrelation of families of points of high order on the Edwards curve over a prime field , Probl. Inf. Transm . 51 ( 4 ) ( 2015 ) 391 - 397 . doi: 10 .1134/s0032946015040080. [Publication in Russian].

[14] A. Bessalov , et al., Analysis of 2-isogeny properties of generalized form Edwards curves , in: Proceedings of the Workshop on Cybersecurity Providing in Information and Telecommunication Systems, July 7 , 2020 , vol. 2746 , pp. 1 - 13 .