=Paper=
{{Paper
|id=Vol-2923/paper1
|storemode=property
|title=Computing of Odd Degree Isogenies on Supersingular Twisted Edwards Curves
|pdfUrl=https://ceur-ws.org/Vol-2923/paper1.pdf
|volume=Vol-2923
|authors=Anatoly Bessalov,Volodymyr Sokolov,Pavlo Skladannyi,Oleksii Zhyltsov
|dblpUrl=https://dblp.org/rec/conf/cpits/BessalovSSZ21
}}
==Computing of Odd Degree Isogenies on Supersingular Twisted Edwards Curves==
https://ceur-ws.org/Vol-2923/paper1.pdf
Computing of Odd Degree Isogenies
on Supersingular Twisted Edwards Curves
Anatoly Bessalova, Volodymyr Sokolova, Pavlo Skladannyia, and Oleksii Zhyltsova
a
Borys Grinchenko Kyiv University, 18/2 Bulvarno-Kudriavska str., Kyiv, 04053, Ukraine
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.
Keywords1
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
Cybersecurity Providing in Information and Telecommunication Systems, January 28, 2021, Kyiv, Ukraine
EMAIL: a.bessalov@kubg.edu.ua (A.1); v.sokolov@kubg.edu.ua (A.2); p.skladannyi@kubg.edu.ua (A.3); o.zhyltsov@kubg.edu.ua (A.4)
ORCID: 0000-0002-6967-5001 (A.1); 0000-0002-9349-7946 (A.2); 0000-0002-7775-6039 (A.3); 0000-0002-7253-5990 (A.4)
Β©οΈ 2021 Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR Workshop Proceedings (CEUR-WS.org)
1
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 mod 4 [11]. The minimum even
πmax
cofactor of the order of such curves is 8, then for CSIDH algorithm with odd π = βπ=1 ππ 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 β ππ¦1 π¦2 π₯1 π¦2 + π₯2 π¦1
(π₯1 , π¦1 ) + (π₯2 , π¦2 ) = ( , ). (4)
1 β ππ₯1 π₯2 π¦1 π¦2 1 + ππ₯1 π₯2 π¦1 π¦2
2
If two points from (4) coincide, we have
π₯12 β ππ¦12 2π₯1 π¦1
2(π₯1 , π¦1 ) = ( 2 2, ). (5)
1 β ππ₯1 π¦1 1 + ππ₯12 π¦12
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:
π 1
π·1,2 = (Β±β , β) , Β±πΉ1 = (β, Β± ), (6)
π βπ
where we put the sign β when dividing by 0. They arise in the cases π(ππ) = 1 and π(π) = 1,
respectively.
Depending on the properties of the parameters π and π, the curves in the generalized Edwards form
(1) are divided into 3 disjoint classes [10]:
ο· 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:
1. 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.
2. The class of complete Edwards curves does not contain exceptional points.
π
3. Twisted Edwards curves contain two exceptional points of the 2nd order π·1,2 = (Β±β , β), and
π
quadratic Edwards curves, besides them, contain two more exceptional points of the 4th order Β±πΉ1 =
1
(β, Β± ).
βπ
4. Twisted and quadratic Edwards curves form quadratic twist pairs based on parameters
transformations: πΜ = ππ, πΜ = ππ, π(π) = β1.
5. In the classes of twisted and quadratic Edwards curves, the replacement π β π gives the
isomorphism of curves πΈπ,π ~πΈπ,π .
6. 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ππ)3
π½(π, π) = , ππ(π β π) β 0.
ππ(π β π)4
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
π: πΈ(πΎ) β πΈβ²(πΎ) that is given by rational functions. This means that for all π, π β πΈ(πΎ), π(π + π) =
π(π) + π(π) and that there are rational functions [17]
π(π₯) π(π₯)
π(π₯, π¦) = ( ,π¦ ) = (π₯β², π¦β²), (7)
π(π₯) π(π₯)
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.
3
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)
at π = 1.
Theorem 2 [5]. Let πΊ = {(1,0), Β±π1 , Β±π2 , . . , Β±ππ } the subgroup of odd order π = 2π + 1 of the
points Β±ππ = (πΌπ , Β±π½π ) on the curve πΈπ .
We define
π₯π+ππ π₯πβππ π¦π+π
π(π) = (β ,β ).
π₯ππ π₯βππ π₯π
πβπΊ πβπΊ
Then π(π₯, π¦) is π-isogeny with the kernel πΊ from the curve πΈπ to the curve πΈβ²πβ² with the parameter
π = π΄8 ππ and the mapping function
β²
π π
π₯ (πΌπ π₯)2 β (π½π π¦)2 π¦ (πΌπ π¦)2 β (π½π π₯)2
π(π₯, π¦) = ( 2 β , β ). (8)
π΄ 1 β (ππΌπ π½π π₯π¦)2 π΄2 1 β (ππΌπ π½π π₯π¦)2
π=1 π=1
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
Β±ππ = (πΌπ , Β±π½π ), so for coordinates pairs we have
π₯π+ππ π₯πβππ 1 (πΌπ π₯)2 β (π½π π¦)2 π¦π+ππ π¦πβππ 1 (πΌπ π¦)2 β (π½π π₯)2
= 2 , = .
π₯ππ π₯βππ πΌπ 1 β (ππΌπ π½π π₯π¦)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
π₯π+ππ π₯πβππ π¦π+ππ π¦πβππ
π(π) = (π₯β², π¦β²) = (β ,β ).
π₯ππ π₯βππ π¦ππ π¦βππ
πβπΊ πβπΊ
Then π(π₯, π¦) is π-isogeny with the kernel πΊ from the curve πΈπ,π to the curve πΈβ²πβ² ,πβ² with parameters
π = ππ , πβ² = π΄8 ππ , π΄ = βπ π=1 πΌπ and the mapping function
β²
π π
π₯ (πΌπ π₯)2 β π2 (π½π π¦)2 π¦ (πΌπ π¦)2 β (π½π π₯)2
π(π₯, π¦) = ( 2 β , β ), (9)
π΄ 1 β (ππΌπ π½π π₯π¦)2 π΄2 1 β (ππΌπ π½π π₯π¦)2
π=1 π=1
4
or
π π
π₯ π₯ 2 β ππ½π2 βπ¦ π₯ 2 β πΌπ2
π(π₯, π¦) = ( 2 β , β ). (10)
π΄ 1 β ππ½π π₯ 2 π΄2 π β ππΌπ π₯ 2
π=1 π=1
Proof. The formula (9) follows directly from the definition π(π) and the points addition law (4) of
the curve (1).
From (1) it is true that π¦ 2 = (1 β π₯ 2 )/(π β ππ₯ 2 ), πΌπ2 + ππ½π2 = 1 + ππΌπ2 π½π2. Then, in the numerator
of the first coordinate π₯β² in (9), each factor is transformed as:
1 β π₯2 π(πΌπ2 + ππ½π2 )π₯ 2 β π2 π½π2 β ππΌπ2 π₯ 4
ππ = πΌπ2 π₯ 2 β π½π2 π¦ 2 = πΌπ2 π₯ 2 β π2 π½π2 = =
π β ππ₯ 2 π β ππ₯ 2
π(1 + ππΌπ2 π½π2 )π₯ 2 β π2 π½π2 β ππΌπ2 π₯ 4 π(π₯ 2 β ππ½π2 ) β π(πΌπ2 π₯ 4 β πΌπ2 π½π2 π₯ 2 )
= = =
π β ππ₯ 2 π β ππ₯ 2
2 2 2 2
(π₯ β ππ½π )(π β ππΌπ π₯ )
= .
π β ππ₯ 2
Similarly, we transform the factors of the common denominator of coordinates π₯β² and π¦β² into (9):
2 2 2 2 2
1 β π₯2 π β ππ₯ 2 β π2 πΌπ2 π½π2 π₯ 2 + π2 πΌπ2 π½π2 π₯ 4
ππ = 1 β (ππΌπ π½π π₯π¦) = 1 β π πΌπ π½π π₯ = =
π β ππ₯ 2 π β ππ₯ 2
2 2 2 2 2 2 4 2 2 2 2
π β π(πΌπ + ππ½π )π₯ + π πΌπ π½π π₯ (1 β ππ½π π₯ )(π β ππΌπ π₯ )
= 2
= .
π β ππ₯ π β ππ₯ 2
After reducing the common factors for the π₯β²-coordinate, we obtain
ππ (πΌπ π₯)2 β π2 (π½π π¦)2 π₯ 2 β ππ½π2
= = .
ππ 1 β (ππΌπ π½π π₯π¦)2 1 β ππ½π2 π₯ 2
The second coordinate π¦β² in (9) as factors in the numerator
πΌπ2 (1 β π₯ 2 ) β π½π2 π₯ 2 (π β ππ₯ 2 )
ππ = (πΌπ π¦)2 β (π½π π₯)2 = =
π β ππ₯ 2
βπ₯ 2 (πΌπ2 + ππ½π2 π₯ 2 ) + ππ½π2 π₯ 4 + πΌπ2 βπ₯ 2 (1 + ππΌπ2 π½π2 ) + ππ½π2 π₯ 4 + πΌπ2
= = =
π β ππ₯ 2 π β ππ₯ 2
2 2
β(π₯ 2 β πΌπ )(1 β ππ½π π₯ 2 )
= .
π β ππ₯ 2
Then
ππ (πΌπ π¦)2 β (π½π π₯)2 π₯ 2 β πΌπ2
= =β .
ππ 1 β (ππΌπ π½π π₯π¦)2 π β ππΌπ2 π₯ 2
As a result, the function (9) can be written in the equivalent form (10)
π π
π₯ π₯ 2 β ππ½π2 βπ¦ π₯ 2 β πΌπ2
π(π₯, π¦) = ( 2 β , β ),
π΄ 1 β ππ½π2 π₯ 2 π΄2 π β ππΌπ2 π₯ 2
π=1 π=1
depending on the parameters π 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 mod 8 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
5
π = β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 π = 5. .118.
Table 1
Values of the parameter (βπ
) of STEC at π = πππ, π = βπ, and π΅π¬ = πππ
25 64 121 196 50 183 4 10 87 176
24 153 11 110 48 187 120 193 27 160
213 44 2 201 61 3 206 192 80 62
(0)
For the first curve (1) πΈβ1,β25 = πΈπ,π from Table 1 we can construct 3- and 5-isogenies and find
(π) (π) (0)
chains of isogenic curves πΈβ1,ππ , π = 1,2, β¦, π such that πΈπ,π = πΈπ,π . Then the chain of mappings
(1) (0)
π (2) β π (3) β β¦ β π (π) gives dual isogeny πΈβ1,π1 β πΈβ1,π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
(π) (π) 8 5
curve, we compute π΄(π) = πΌ1 πΌ2 , π(π+1) = (π΄(π) ) (π(π) ) , π = 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
Table 1. The data of Tables 2 and 3 are used to construct the graphs of isogenies.
Table 2
Values of parameters of the chain of 3-isogenous SSCE at π = πππ, π = βπ
π 0 1 2 3 4 5
(π) 149 227 152 174 179 149
πΌ
βπ(π) 25 3 10 50 110 25
(π) 225 105 55 105 225 225
π½(π )
Table 3
Values of parameters of the chain of 5-isogenous SSCE at π = πππ, π = βπ
π 0 1 2 3 4 5 6 7
(π) (π) β95,β72 69, β53 57,β8 103, β102 107,β 118, β55 25, β18 41, β52
πΌ1 , πΌ2
34
βπ(π) 25 2 11 50 193 187 3 61
π½(π(π) ) 225 218 215 105 215 215 105 235
π 8 9 10 11 12 13 14 15
(π) (π) 103, β88 79, β91 51,108 β68, β43 13, β β103, β46 β48,β8 β93, β72
πΌ1 , πΌ2
βπ(π) 183 110 5 121 10 62 201 25
(π) 218 225 113 327 55 217 113 225
π½(π )
6
The mapping (10) of the points π = (π₯, π¦) of the curve πΈβ1,β25 with the kernel
πΊ = {(1,0), Β±π1 = (β90, Β±64)} of 3-isogeny has the form:
π₯ π₯ 2 β ππ½ 2 βπ¦ π₯ 2 β πΌ 2
π3 (π₯, π¦) = ( 2 , )=
π΄ 1 β ππ½ 2 π₯ 2 π΄2 1 + ππΌ 2 π₯ 2
π₯ π₯ 2 + 642 βπ¦ π₯ 2 β 902
=( 2 , ).
90 1 + 252 642 π₯ 2 902 1 β 252 902 π₯ 2
The point of the maximum 120th order π = (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
π₯ π₯ 2 + 282 π₯ 2 β 952 βπ¦ π₯ 2 + 1192 π₯ 2 β 722
(π₯,
π5 π¦) = ( 2 , ),
π΄ 1 + 252 642 π₯ 2 1 β 252 952 π₯ 2 π΄2 1 + 252 1192 π₯ 2 1 β 252 722 π₯ 2
π΄2 = (95 β 72)2 = 155.
th
The point of the 120 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 π = (8, β16) of the 30th order is
mapped to the point πβ² = (18, β7) of the 6th order. The point of the 5th order π = (β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.
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
parameters πβ² = ππ , πβ² = π΄8 ππ , π΄ = βπ π=1 πΌπ , and the mapping function
π
(π€ β π€π )2
π€(π) = π€ β . (11)
(1 β π€π€π )2
π=1
Proof. From the equation of the curve (1) we have πΌπ2 + ππ½π2 = 1 + ππΌπ2 ππ½π2. The factors under the
sign of the product of isogeny (10) have the form:
ππ π₯ 2 β ππ½π2 ππ π₯ 2 β πΌπ2
= , = .
ππ₯π 1 β ππ½π2 π₯ 2 ππ¦π π β ππΌπ2 π₯ 2
7
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
π¦ 2 respectively, we obtain:
ππ ππ¦ 2 = βππ ππ = ππ¦ 2 (π₯ 2 β ππ½π2 )(π₯ 2 β πΌπ2 ) = π₯ 2 π€ β π₯ 2 π¦ 2 (πΌπ2 + ππ½π2 ) + πππΌπ2 π½π2 π¦ 2 =
= π€π₯ 2 β π€(1 + π€π ) + ππ€π π¦ 2 ,
π
π π¦ = π¦ (1 β ππ½π π₯ )(π β ππΌπ2 π₯ 2 ) = ππ¦ 2 β ππ₯ 2 π¦ 2 (πΌπ2 + ππ½π2 ) + π€π€π π₯ 2 =
2 2 2 2
= ππ¦ 2 β π€(1 + π€π ) + π€π€π π₯ 2 .
Substitution in the last equations ππ¦ 2 = 1 + π€ β π₯ 2 gives:
ππ ππ¦ 2 = π€π₯ 2 β π€(1 + π€π ) + ππ€π π¦ 2 = π€π₯ 2 β π€ β π€π€π + π€π (1 + π€ β π₯ 2 ) =
= (π€ β π€π )(π₯ 2 β 1),
π
π π¦ 2 = ππ¦ 2 β π€(1 + π€π ) + π€π€π π₯ 2 = (1 + π€ β π₯ 2 ) β π€ β π€π€π + π€π€π π₯ 2 =
= (1 β π€π€π )(π₯ 2 β 1).
Then
π π π
ππ β1
π€ β π€π ππ 2 β2π
ππ 2 β2π
(π€ β π€π )2
=π , β( ) =π β( ) = π β .
π
π 1 β π€π€π ππ
π π
π (1 β π€π€π )2
π=1 π=1 π=1
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
π€(π(π)) = π βπ¦ =π΄ π π₯ π¦ π΄ β( ) =
ππ
π
π=1
π π
2 2
ππ 2 (π€ β π€π )2
= ππ₯ π¦ β ( ) = π€ β .
π
π (1 β π€π€π )2
π=1 π=1
The theorem is proved.
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 = 978 253 = 110 also
changes. For the curve πΈ25 the mapping (10) of the point of the 120th π = (20,108) is the point of the
40th order πβ² = (β16,57) on the isogenic curve πΈ110 . For point π 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
equation of the curve πΈπ (2) or (3). For STEC (1) at π β‘ 3 mod 4, we accept π = β1,
π(π=π) = βπ2 mod π, π β {2. . (π β 1)/2} and define the curve:
πΈπΆ,π· : πΆπ₯ 2 β πΆπ¦ 2 = πΆ + π·π₯ 2 π¦ 2 , π· = ππΆ, π(π) = β1. (12)
To calculate the parameter πβ² of the isogenic curve the formula [5] is used:
π
β² 8 π
π = π΄ π , π΄ = β πΌπ , π = 2π + 1. (13)
π=1
8
To express the parameter π΄ 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
πΌπ2 β ππ½π2 2πΌπ π½π
2(πΌπ , π½π ) = ( 2 2, ).
1 β ππΌπ π½π 1 + ππΌπ2 π½π2
By squaring the second coordinate, we obtain
2πΌπ π½π 2 4πβ1 π€π 2 2 2
4πΌπ2 π€π 2 (1 + π€π )2
( ) = = π½ π βΉ ππΌ π½
π π = βΉ πΌπ = .
1 + π€π (1 + π€π )2 (1 + π€π )2 4
Here we take into account that for each point of the kernel (πΌπ , π½π ) there exists the reverse point
(πΌπ , βπ½π ) = (πΌπ , π½π ) and for such a pair of points π€π = π€π . Then the formula (13) takes the form
π
π
(1 + π€π )8
πβ² = π β . (14)
44
π=1
Transition to projective coordinates (π: π) allows avoiding inversions in the formula (11), thus for
the curve (12)
π π
π = π β(πππ β ππ π) , π = π β(πππ β πππ )2 .
β² 2 β²
π=1 π=1
Here 4π π + 2π + 2π operations in the field are performed for every π (π is multiplication, π is
squaring). If we enter intermediate formulas:
π» = (π + π)(ππ β ππ ),
π½ = (π β π)(ππ + ππ ),
then
π π
β² )2
2π = π β(π»π β π½π , 2π = π β(π»π β π½π )2 .
β²
π=1 π=1
And we need only 4π π + 2π operations when calculating one isogeny (11).
For calculating the parameter πβ² = π·β²β of the isogenic curve (12) in projective coordinates
πΆβ²
according to (14) we obtain
π π
π· = π· β(ππ + ππ , πΆ = πΆ β(2ππ )8 .
β² π )8 β² π
π=1 π=1
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
well as two non- exceptional points of the 4th order Β±πΉ0 = (0, Β±1). It is easier to bypass exceptional
points in the STEC class, which makes them preferable to quadratic ones in cryptosystems.
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
9
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
[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.
10
[15] A. V. Bessalov, Calculation of parameters of cryptic curves Edwards over the fields of 5 th 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.
11