The analysis of the 2-isogeny existence conditions of generalized Edwards form curves over a prime field, including complete, quadratic, and twisted Edwards curves, is presented. An overview of the properties of these three classes of curves is given. Generalization of the results known for the classes of complete and quadratic curves to the class of twisted Edwards curves is obtained. A modified law of point's addition is used to correctly determine the isogeny degree.
One of the well-known prospects of post-quantum cryptography (PQC) is the isogeny of supersingular elliptic curves with as many subgroups of their points as possible. The discrete logarithm problem (DLP) of classical elliptic cryptography is replaced by the problem of finding one of the isogenies of a large number of subgroups of such a noncyclic curve, which is sufficiently resistant to the attacks of a virtual quantum computer. To date, the growing interest in isogenies is associated with the shortest key length in the proposed algorithms in comparison with other known candidates for PQC at a given level of security [1].
Sect. 2 provides a brief review of the literature on this topic. Sect. 3 of the article gives the basic definitions of isomorphic curves in Montgomery and Edwards forms, the laws of the point’s addition, and doubling with a modification adapted to the horizontal symmetry of inverse points. A brief overview of the properties of three classes of generalized Edwards form curves following the classification is given. Sect. 4 summarizes the results of one of the methods for obtaining 2-isogeny for two classes of complete and quadratic Edwards curves [3] to the class of twisted Edwards curves, analyzes the existence conditions for the 2-isogeny in three classes of Edwards curves over a prime field, and includes examples.
Review of the Literature The properties of isogenies for Weierstrass curves are well studied. Effective methods for constructing and isogenies properties of promising classes of curves in the Edwards form are much less known. The Edwards curves with one parameter, defined in [2], have very attractive advantages for cryptography: fastest exponentiation of a point [2], completeness and universality of the law of point’s addition, affine coordinates of a neutral element of a points group, enhanced security against side-channel attacks [2– 4]. 3- and 5-isogenies are considered in previous works [5] and [6].
The programming of group operations is accelerated due to the absence of a singular point at infinity as a neutral element of an Abelian group of points. The introduction of the second curve parameter in [7] extended the class of curves in the Edwards form and gave rise to classes of quadratic and twisted curves with new properties of interest to cryptographic applications. In this paper, the known results for the 2-isogeny of complete and quadratic Edwards curves [3, 8] are generalized to the class of twisted Edwards curves [9, 10]. In particular, an analysis of the existing conditions of such curves over a prime field is given. 3
Isomorphism and Properties of Classes of Generalized Edwards Form Curves The analysis of isogenies of Edwards curves is often based on Weierstrass and their special cases of isomorphic curves in Montgomery or Legendre form. Let’s describe the curve of the Montgomery form over the field , = by the equation [7] , : 2 = 3 + 2 + , = 2 − + , = − 4 , = +2 , =
−2 , 2 ≠ 4. This curve is by a rational transformation of coordinates = , = +1 −1 ⟹ = 1− 1+ , = is mapped into a birationally equivalent in the generalized Edwards form curve of [7, 10] with the equation
, : 2 + 2 = 1 + 2 2, , ∈ ∗, ≠ 1, ≠ , ≠ 2.
Unlike the original equation of this curve in [7] here we multiply the parameter by
2 instead of 2. If the quadratic character (
) = −1, the curve (
: 2 + 2 = 1 + 2 2, ( ) = −1, ≠ 0,1.
In the case of ( ) = 1 and ( ) = ( ) = 1 the curve (
In [10], we proposed to swap the coordinates X and Y in the form of an Edwards
curve. Then the modified universal law of addition of points has the form
(
1− 1 2 1 2 1+ 1 2 1 2
If two points coincide, we obtain from (
1− 12 12 1+2 1121 12).
The use of modified laws (
Let’s define now the inverse point as − 1 = ( 1, − 1) we will acquire according to
(
As follows from (
) of the 4th order, for which ±2 0 = 0 = (−1,0). These points
√
exist over the primary field if the parameter is a square (quadratic residue). The
law of points addition (
Justification of the new classification of generalized Edwards form curves is given in papers [10, 11]. Below are definitions of three classes of these curves and a list of fundamental properties of curves of different classes.
Depending on the properties of the parameters a and d, generalized Edwards form
curves (
1. For points of the second order, the first class of complete Edwards curves over a prime field is the class of cyclic curves, while twisted and quadratic Edwards curves form classes of non-cyclic curves. The maximum order of points of curves of the last 2 classes does not exceed ⁄ .
2
2. The class of complete Edwards curves does not contain singular points. The order of these curves is ≡ 4mod8 or ≡ 0mod8.
3. The twisted Edwards curves contain only two singular points of the 2nd order 1,2 = (±√
(±√
curves is ≡ 0mod8.
; ∞). The order of these curves is ≡ 4mod8 or ≡ 0mod8. 4. Quadratic Edwards curves contain two singular points of the 2nd order 1,2 = ; ∞) and two singular points of the 4th order ± 1 = (∞; ± 1 ). The order of these √ 5. Twisted and quadratic Edwards curves form pairs of quadratic torsion based on the transformation of parameters: ̃ = , ̃ = , ( ) = −1.
6. In the classes of twisted and quadratic Edwards curves, the replacement ↔ gives the isomorphism , ~ , .
7. Complete and quadratic Edwards curves are isomorphic to curves with parameter
= 1: , ~ 1, / . The introduction of the parameter into the equation of curve (
8. Twisted Edwards curves under ≡ 1mod4 do not have the points of the 4th order and have the order = 4 , is odd.
9. For points of odd order, the law of addition of points (
= deg ( , ) = max{deg ( ), deg ( )}, and its kernel is subgroup
⊆ of the order (separable isogeny), the points of which are mapped by the function ( , ) into a neutral element of the group O.
Isogeny compresses the points of the curve at times and is a surjection ( points of the curve are mapped to one point of the curve ′). When = , isogeny becomes isomorphism ( = 1).
The calculation of isogenies is usually carried out using the Velu formulas [12] for
curves in the Weierstrass form. In paper [3] isogeny formulas of the second (2-isogeny)
and odd degrees are obtained, adapted, in particular, to curves in the form of Edwards
(
Let us analyze and extend some of their results to curves (
1. Isomorphic transformation 1( , ) = ( , ) of the Edwards curve into the
2. The construction of 2-isogeny 2( , ) = ( , ).
3. Reverse transformation 3( , ) = ( , ) of the isogenous curve in the
curve and the isogenic curve ′ is found.
transformation (
As a result, the composition ( , ) = 1 ∘ 2 ∘ 3 of three mappings between the
At the first stage, the Edwards curve (
2 = 3 + 2( + ) 2 + ( − )2 .
The point (0,0) is the second-order point of this curve, which, together with the point
at infinity as a neutral element of the group, forms the kernel of the 2-isogeny. It is
required to find parameters ̅ and ̅of the isogenous curve with equation (
For the Montgomery curve of the general view
, : 2 = 3 + 2 + ,
finding 2-isogeny is well known [12]. Based on the Velu formulas, using the laws of
the addition of the points of the curve in the general Weierstrass form, for the curve (
2 ) = ( , ) 2 = 3 − 2 2 + ( 2 − 4 ) .
The discriminant of the quadratic equation on the right-hand side of (
The main question in this work is the question of the existence of 2-isogeny in three
classes of Edwards curves. As follows from (
Thus, the 2-isogenic curve (
The equations (
1: 2 = 3 − 4( + ) 2 + 4
.
1: 2 = ( − 4 )( − 4 ).
(14)
(15)
(16)
The curve (16), up to isomorphism, coincides with the isogenic curve in the form (
2 = 3 + 2( ̅ + ̅) 2 + ( ̅ − ̅)2 .
From this equation and (
we obtain 2 ̅̅−+ ̅̅ 1 = −4( + ), 12 = 16 .
√ +√ )2.
̅+ ̅ = ∓( + ) ⟹ 1̅±1 = ̅1 (√ −√
̅− ̅ 2√
So, for curve (
According to property 5 of Sect. 2, the twisted Edwards curve is the quadratic torsion of the quadratic Edwards curve 1, = with the offset = of the parameters ̃ = , ̃ = , ( ) = −1, where is the parameter of the quadratic Edwards curve ( ( ) = 1). In this case, the parameter can be considered as a fixed factor of the variable parameter , moreover ̃ ± ̃ = (1 ± ). For example, with ≡ 3mod4 for a twisted curve, we can take = −1 аnd with ≡ 1mod4 as the smallest value of the quadratic nonresidue.
Further, instead of the curve , we will use the curve , that leads to the substitution → . This simplifies the formulas for the isogenic curve parameters.
The formula (19) is valid only for one of the three points of the 2nd order (0,0) of the
curve (15). Based on (
The inverse transformation of isogenous curves in the Montgomery form ( 1, 2,
and 3) into the Edwards form , is performed based on rational functions (
3( , ) = ( −+ 11 , 2 √ ̅−1 ̅) = ( , ).
Substitution of these rational functions of the form (
The composition ( , ) = 1 ∘ 2 ∘ 3 of three transformations leads to the 2isogeny formulas for curves in the Edwards form, which are given below in Theorem 1.
In [3], the theorem was proved that is valid for complete and quadratic Edwards
curves ( = 1). We generalize this theorem to all generalized Edwards form curves (
→ ′ , ̅, set by the functions 1, 2, and 3 → ′̅,̅̅ with the parameters 1̅±1 = ̅(11−+ )2; 1 − 2 2
1 − 2 ), 2( , )= (( ( ∓ 1) 2 ± 1 ± 1) 2 ∓ 1,( → ′̅,̅̅ with the parameters 2̅±1 = ̅(1− )2;
1+ 2 ∓ − 3( , )= (− 2 ±
− ,( ± ) ), → ′̅,̅̅ with the parameters 3̅±1 = ̅( −+ )2.
∓ 1) ),
The proof of the theorem for the case = 1 is given in [3]. Let us adapt its formulas
for the curve (
Taking into account the accepted designations, equations (16), (18), (19) of isogenic
1: 2 = 3 − 4 (1 + 2) 2 + (4
2: 2 = 3 + 4 (1 + 2) 2 + (4
3: 2 = 3 + 4 ( 2 + ( )2) 2 + (4
)2 ;
)2 ;
)2 .
1(
1̅±1 = ̅( 2̅±1 = ̅( 3̅±1 = ̅( +
We emphasize that for the curve , they do not depend on the parameter , but they depend on the parameter ̅.
The proof of formulas for mapping rational functions 1, 2, and 3 is based on the composition ( , )= 1 ∘ 2 ∘ 3 of three transformations: from an Edwards curve to a Montgomery shape, an isogenous transformation of a Montgomery curve, and finally the inverse transformation of the latter to an Edwards curve. It repeats the corresponding proof in [3] with the replacement → , → .
It should be noted that the generally accepted definition of the degree of isogeny is
the highest of the degrees of the polynomials of the first rational function ( ) of the
( )
transformation ( , )[11]. It is valid for Weierstrass curves. If we turn to the original
Theorem 1 [3], then we come to a paradoxical result: the degree of 2-isogeny is equal
to 1. The modified law of Edwards curve points addition (
Let’s consider some properties of 2-isogeny of Edwards curve , over a prime field.
Proposition 2. The complete Edwards curve with the order ≡ 0mod8 has a unique mapping 2( , ) over the primary field at ( ) = 1 to the quadratic Edwards curve.
Proof. By doing ( ) = 1 the complete curve has points of the 8th order and its order
is ≡ 0mod8 [10]. At ( ) = 1 there exist elements ± of the field and the
2
parameter 2̅±1 = ̅(1− ) of the quadratic ( ̅ = 1) or twisted ( ( ̅) = −1) Edwards
1+
curve. At ̅ = 1 there exists a 2-isogeny 2( , ) and the corresponding quadratic
curves are isomorphic to each other with parameters 2̅±1. The transformation from a
quadratic curve to a twisted curve as a quadratic torsion change all points of the curve
(except = (
Consequence. The complete Edwards curve with the order ≡ 0mod4 does not have 2-isogeny over the field in all classes of generalized Edwards form curves.
Proof. From Proposition 2 it follows that the complete Edwards curves are mapped exclusively to the quadratic Edwards curves. But the order of quadratic Edwards curves is ≡ 0mod8 [10], that’s why complete Edwards curves with the order ≡ 0mod4, according to the Tate theorem [12], do not have 2-isogeny over the field .
Proposition 3. The quadratic Edwards curve has the only mapping 2( , ) over the prime field to the quadratic Edwards curve at any values and ( ) = 1, and mappings 1( , ) and 3( , ) at ≡ 1mod4 and ( ) = 1.
Proof. Similarly to Proposition 2, there is a unique mapping of the Edwards quadratic curve over the prime field to the Edwards quadratic curve; at ( ) = 1 the only mapping 2( , ) of the Edwards quadratic curve over the prime field to the Edwards quadratic curve takes place. By doing ≡ 1mod4 and ( ) = 1 for quadratic curves there exist the elements of the field = ±√ , = ±√1 − , and = ±√−1, and, respectively, mappings 1( , ) and 3( , ). Proposition 4. The twisted Edwards curve has the only mapping 2( , ) over the primary field to the Edwards twisted curve at ≡ 3mod4 and ( ) = 1.
Proof. According to property 8 of the Sect. 1 [10], at ≡ 1mod4 the twisted Edwards curve over the primary field does not have points of the 4th order, therefore, the corresponding 2-isogeny does not exist in this class of curves. At ≡ 3mod4 over the field there do not exist elements = ±√−1 and, respectively, mappings 1( , ) and 3( , ). The only 2-isogeny in this class at ≡ 3mod4 and ( ) = 1 is the function 2( , ).
Let’s consider examples of the 2-isogeny of complete and quadratic Edwards curves over the field .
Example 1. Let = 11 and the complete Edwards curve = 7: 2 + 2 = 1 + 7 2 2 where ( = 7) = −1, (1 − = 4) = 1 with the order = 16 is given. According to Theorem 1, there exists only a pair of 2-isogeny Edwards quadratic curves ′ = 4 and ′ = 3 with the parameters 1,2 = ̅±1 = {4,3} and the mapping 2( , ). They have the same order = 16 (which corresponds to the well-known Tate theorem [11]), are isomorphic to each other, but instead of one they already have 3 points of the 2nd order (the curves are noncyclic) and 12 points of the 4th order. There are two singular points of the 2nd and 4th order. The points of the original complete curve E are denoted as , and the points of two isogenic curves ′ is as . As with the doubling of points, the mapping 2( , ) compresses the preimage (curve ) in half, i.e. maps a pair of points of curve to one point of curve ′. Unlike doubling, 2isogeny does not necessarily halve the order of a point of even order.
On the curve E , we have points (±1,0), (0, ±1), (±2, ±4), (±3, ±3), (±4, ±2).
Let 1 = (
Example 2. Let’s construct the isogeny for the quadratic curve = 3 from example
1 with the parameters = 3, 1 − = 9, = 3. One of the isogenic curves when
mapping 2( , )has the same parameter = 3 and the same points 1 = (
2( 0, )(
If you reapply the function 2( , )(
2( 0, )(
Thus, the second isogeny returns us to the points of the original curve ( ′′ = ), and
for two steps the mapped points of the curve are doubled (multiplied by : points of
the 4th order are mapped into points of the 2nd order, and points of the 2nd order are to
the point ). This is an example of dual 2-isogeny ̂2 = 2( , )(
Consider the isogenies of twisted Edwards curves over the field . According to Proposition 3, they exist only at ≡ 3mod4 and ( ) = 1, at the same time it is possible to accept = ̅ = −1.
Example 3. Let = 19 and the twisted curve −1,−9 with the parameters = −1,
= −9, = √11 = ±7 is given. Its order is = 16. It has the points , 0,
1,2 = (±6, ∞), and the points of the first quadrant 1 = (
(−7 − 1)22 + 1
± 2( 1, 1∗)(
(−7 + 1)22 − 1
± 2( 2, 2∗)(
= 2, (−7 − 1)2 = 3) = ± 1,
The second isogenous curve ′−1,13 with the reverse meaning of the parameter
2̅−1 = 3−1 = 13 is isomorphic to the first one and contains the points , 0,
′′1,2 = (±4, ∞), 1 = (
= −9, (−7 + 1)2 = 7) = ∓ 3∗,
(−7 + 1)22 − 1
(−7 − 1)22 + 1
± 2( 2, 2∗)(
For isogeny :
→ ′ there exists dual isogeny ̂: ′ → , in such way that ° ̂ = [deg( ) = ] [11]. The formulas of Theorem 2 prove that over the field for the complete Edwards curves, dual isogeny does not exist, but it exists in the extension 2. To find dual isogeny ̂: ′ → , for example to the function 1( , ) with the values of the isogenic curve 1̅±1 = ̅(
It is necessary to solve the inverse problem: from the known value 1̅ of the curve ′ it is necessary to calculate one of the suitable values of the parameter of the curve , which is determined by a similar formula ±1 = 1 − √ ̅−1 1̅ 1 + √ ̅−1 1̅ .
Hence we see that the dual mapping of the curve ′ to the complete and twisted Edwards curves exists only in the extension 2, in which all curves defined over the field , have the properties of quadratic curves. 5
Conclusions Thus, over the field there exists 2-isogenies : → ′ from the complete curves to the quadratic Edwards curves, from the quadratic curves to the quadratic Edwards curves, and also from the twisted curves to the twisted Edwards curves. In the extension 2 all the curves defined over the field become quadratic Edwards curve (their parameters and are the squares in the field 2), and for any such curve, there is a pair of isogenic quadratic curves defined by Theorem 1. In practice, in this regard, the isogenies of curves given over
are calculated over the extension 2. The implementation of one of the promising algorithms for PQC Supersingular Isogenies Diffie-Hellman (SIDH) [13] is based, as is known, on 2- and 3-isogeny of supersingular elliptic curves. The use of fast twisted Edwards curve arithmetic will undoubtedly allow the construction of more efficient cryptosystems.