=Paper=
{{Paper
|id=Vol-3187/short10
|storemode=property
|title=Implementation of the CSIDH Algorithm Model on Supersingular Twisted and Quadratic Edwards Curves
|pdfUrl=https://ceur-ws.org/Vol-3187/short10.pdf
|volume=Vol-3187
|authors=Anatoly Bessalov,Volodymyr Sokolov,Pavlo Skladannyi,Natallia Mazur,Dmytro Ageyev
|dblpUrl=https://dblp.org/rec/conf/cpits/BessalovSSMA21
}}
==Implementation of the CSIDH Algorithm Model on Supersingular Twisted and Quadratic Edwards Curves==
https://ceur-ws.org/Vol-3187/short10.pdf
Implementation of the CSIDH Algorithm Model
on Supersingular Twisted and Quadratic Edwards Curves
Anatoly Bessalov1, Volodymyr Sokolov1, Pavlo Skladannyi1, Natallia Mazur1,
and Dmytro Ageyev1
1
Borys Grinchenko Kyiv University, 18/2 Bulvarno-Kudriavska str., Kyiv, 04053, Ukraine
Abstract
The properties of twisted and quadratic supersingular Edwards curves forming pairs of
quadratic torsion with the order p + 1 over the simple field Fp are considered. A modification
of the CSIDH algorithm using the isogenies of these curves in replacement of the extended
arithmeticβs of the isogenies of curves in the Montgomery form is presented. The isogeny
parameters of the CSIDH algorithm model are calculated and tabulated on the basis of the
theorems proved in the previous work. The example of Aliceβs and Bobβs calculations
according to the non-interactive Diffy-Hellman circuit, illustrating the separation of their
secrets, is considered. The use of the known projective (W:Z)-coordinates for the given classes
of curves provides the fastest execution of the CSIDH algorithm to-date.
Keywords1
Generalized Edwards form curve, complete Edwards curve, twisted Edwards curve, quadratic
Edwards curve, curve order, point order, isomorphism, isogeny, w-coordinates, quadratic
residue, quadratic non-residue.
1. Introduction
This article is a continuation of the previous work [1]. Problems of post-quantum cryptography
(PQC) today are successfully solved by various algorithms, among which the most promising, in
particular, are algorithms based on isogenies of supersingular elliptic curves (SEC) [2, 3]. An efficient
alternative to the SIDH [2] (Supersingular Isogeny Diffi-Hellman) protocol is the CSIDH [3]
(Commutative SIDH) algorithm with the minimum known key length. Instead of the extended field πΉπ2
in the SIDH, operations in the CSIDH are performed over a simple field Fp, which for the given Fp
halves the length of field elements and key sizes.
The implementations of the SIDH and CSIDH algorithms were mainly based on the fast arithmetic
of isogenies of curves in the Montgomery form. In [4] (2019), a new efficient method for calculating
isogenies of odd degrees for Edwards curves based on the Farashahi-Hosseini w-coordinates [5] is
proposed. This work, in turn, is based on Montgomery's method of differential addition of points and
adapts it to Edwards curves. The optimization of the arithmetic of isogenies on Edwards curves in
projective coordinates (W:Z) in [4] significantly accelerated the algorithms of their previous work [6]
and allowed the authors to obtain a 20% gain in the speed of operations compared to the implementation
of the algorithm on the Montgomery curves.
Formulas for calculating isogenies of odd degrees of Edwards curves [7] also contain components
of differential addition of points, which served as the basis for the method proposed in [4]. Calculations
in classical projective coordinates, as our analysis showed for isogeny of small degrees [8], become
much more complicated with increasing degree of isogeny and lose in cost to (W:Z)-coordinates.
Complete Edwards curves Ed with one parameter (Ο(d) = β1), defined in [9], have well-known
advantages: maximum speed of exponentiation of a point, universality of the law of addition of points,
CPITS-II-2021: Cybersecurity Providing in Information and Telecommunication Systems, October 26, 2021, Kyiv, Ukraine
EMAIL: a.bessalov@kubg.edu.ua (A. Bessalov); v.sokolov@kubg.edu.ua (V. Sokolov); p.skladannyi@kubg.edu.ua (P. Skladannyi);
n.mazur@kubg.edu.ua (N. Mazur); dmytro.aheiev@nure.ua (D. Ageyev)
ORCID: 0000-0002-6967-5001 (A. Bessalov); 0000-0002-9349-7946 (V. Sokolov); 0000-0002-7775-6039 (P. Skladannyi); 0000-0001-
7671-8287 (N. Mazur); 0000-0002-2686-3854 (D. Ageyev)
Β©οΈ 2022 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)
302
affine coordinates of a neutral element of a group of points. The introduction of the 2 nd parameter a of
the curve Ea,d in [10] expanded the class of curves in the Edwards form and gave rise, according to the
classification adopted in [11, 12], to two new classes: twisted and quadratic Edwards curves. They form
quadratic torsion pairs that are used in this article to implement the CSIDH algorithm.
The calculation of isogenies of odd degrees for complete and quadratic Edwards curves Ed is carried
out by the formulas defined by Theorems 2β4 in [7]. In our previous work [1], we generalized theorems
[7] to curves in the generalized Edwards form with two parameters a and d, which allowed us to apply
in this article twisted and quadratic Edwards curves over the field πΉπ for the implementation of the
CSIDH model.
Our analysis in this paper is based on the properties of twisted and quadratic Edwards curves
connected as pairs of quadratic torsion [13, 14]. Supersingular curves of these classes with the same
order NE = p + 1 = 2mn, m β₯ 3 (n is odd) exist only at p β‘ 3mod4. The minimum even cofactor of the
order of such curves is eight; then, for the CSIDH algorithm with odd n=βπΎ π=1 ππ , the modulus of the
field Fp should be chosen as p = 8n β 1. In order to adapt the definitions for the arithmetic of isogenies
of Edwards curves and curves in the Weierstrass form, we use a modified law of addition of points
[11,12].
Section 1 gives a brief overview of the properties of twisted and quadratic supersingular Edwards
curves [13β15]. Section 2 discusses specific aspects of the implementation of the CSIDH algorithm
model on twisted and quadratic Edwards curves, provides a modification of the algorithm [3], calculates
and tabulates the parameters of isogenous curves of the model, gives an example of Aliceβs and Bobβs
calculations in the Diffie-Hellman secret sharing scheme. Aspects of the performance of model using
(W:Z)-coordinates [4,1] are summarized.
2. Properties of Twisted and Quadratic Supersingular Edwards Curves
A number of general properties of Edwards curves were considered in the previous work [1]. Here
we turn to the specific properties of the supersingular Edwards curves (SEC) [13, 14]. The elliptic curve
in the generalized Edwards form [11] is determined by the equation
Ea , d : x 2 ο« ay 2 ο½ 1 ο« dx 2 y 2 , a, d ο Fp* , a οΉ d , d οΉ 1. (1)
With the quadratic character Ο(ad) = β1, the curve (1) is isomorphic to the complete Edwards curve
[9] with one parameter d
Ed : x 2 ο« y 2 ο½ 1 ο« dx 2 y 2 , ο£ (d ) ο½ ο1. (2)
In case of Ο(ad) = 1, Ο(a) = Ο(d) = 1 the curve (1) is isomorphic to the Edwards quadratic curve [11]
Ed : x 2 ο« y 2 ο½ 1 ο« dx 2 y 2 , ο£ (d ) ο½ 1, , d οΉ 1. (3)
Having, in contrast to (2), the parameter d, defined as the square. For both curves (2) and (3) usually
take a = 1. In the work [10] the curve (3) together with the curve (2) are called the Edwards curves. The
difference in the quadratic characters of these curves leads to their radically different properties [11,
12].
The twisted Edwards curve was defined in [11] as a special case of the curve (1) for Ο(ad) = 1,
Ο(a) = Ο(d) = β1.
We define a pair of twisted and quadratic Edwards curves [11] as a pair of quadratic torsion with
parameters Ο(ad) = 1, aΚΉ = ca, dΚΉ = cd, Ο(c) = β1. As the SEC exists only at p β‘ 3mod4 [11], then we can
accept c = β1, aΚΉ = βa =β1, dΚΉ = βd, where a and d are quadratic curve parameters and, respectively,
aΚΉ,dΚΉ-twisted curve parameters. In other words, the transition from a quadratic to a twisted torsion curve
and vice versa can be defined as Ed = E1,d β Eβ1,βd. So the equation of the twisted SEC at p β‘ 3mod4
from (1) can be written as
Eο1, ο d : x 2 ο y 2 ο½ 1 ο dx 2 y 2 , d ο Fp* , d οΉ 1., ο£ (d ) ο½ 1. (4)
The order NE of the elliptic curve over the simple field πΉπ is defined based on the trace t of the
characteristic Frobenius equation tΟ2 + tΟ + p =0 as NE = p + 1 β t. For the curve of the quadratic torsion
Et the respective order will be equal to NΚΉE = p + 1+ t. An elliptic curve is supersingular if and only if
over any extension of a simple field πΉπ the trace of Frobenius equation is t β‘ 0modp, where in π2 =
βπ, π = Β±ββπ [14,15]. In other words, in the algebraic closure πΉΜ
π a supersingular curve doesnot
303
contain the points of the order p. Over a simple field πΉπ such curve always has the order NE = p + 1, and
over any extension of this field NE β‘ 1modp.
So, twisted and quadratic SEC as a pair of quadratic torsion have the same order NE = p + 1, but a
different structure. Except two points (0,Β±1) all their points do not coincide; therefore, isogenies of the
same degrees have different kernels and are calculated independently. Both curves are non-cyclic with
respect to the points of even order (they contain three points of the 2nd order, two of which are singular
π
points. Both curves are π·1,2 = (Β±β , β) [11]). Besides, the quadratic SEC contains two singular points
π
1
of the 4th order Β±πΉ1 = (β, Β± ). The presence of three points of the 2nd order limits to eight the
βπ
minimum cofactor of the order NE = 8n (n is odd) of twisted and quadratic Edwards curves [11]. The
maximum order of the points of these curves is NE / 2. Points of even orders are not involved in the
calculations of the CSIDH algorithm.
For the curve (1) J-invariant equals [13,15]
16(a 2 ο« d 2 ο« 14ad ) 3
J ( a, d ) ο½ , ad (a ο d ) οΉ 0 (5)
ad (a ο d ) 4
This parameter distinguishes between isogenous (with different J-invariants) and isomorphic (with
equal J-invariants) curves. Since the J-invariant retains its value for all isomorphic curves and pairs of
quadratic torsion [15], it is the same for a pair of twisted and quadratic SEC (a = Β±1), therefore, in what
follows we will use J-invariant J(d). It is a useful tool both for finding supersingular curves and for
constructing graphs of isogenous chains. One of the properties of the J-invariant J(d) is
J (d ) ο½ J (d ο1 ) .
For the classes of SEC under consideration, the replacement d β dβ1 gives an isomorphism, and for
complete Edwards curvesβquadratic torsion [16].
3. Modification of the CSIDH Algorithm on Twisted and Quadratic Edwards
Curves
The PQC CSIDH (Commutative SIDH) algorithm was proposed by the authors [3] to solve the same
key exchange problem (SIDH [2]), but on the basis of isogenous mappings of elliptic curves, on the
whole, as additive Abelian groups. This mapping over a simple field Fp is defined as the class of group
action and is commutative. In comparison with the well-known original CRS scheme (Couveignes
(1997), Rostovtsev, Stolbunov (2004) on nonsupersingular curves, the use of isogenies of supersingular
curves made it possible to dramatically speed up the algorithm and obtain the smallest known key size
(512 bits in [3]).
Let the curve E of the order NE contain points of small odd orders li, i = 1,2,β¦,K. Then there is an
isogenous curve EΚΉ of the same order NE as the mapping of the degree li: E β EΚΉ = [li]*E. The repetition
π
of this operation ei times will denote [ππ π ] β πΈ. The exponents of isogenies ei β Z determine the length
of the chain of isogenies of li degree. In the work [3] an interval of exponential valuesβm β€ ei β€ m,
m = 5, K = 74 is adopted, which provides a security level of 128 bits when attacking a quantum
computer. Negative values of the exponent ei indicate a transition to a quadratic torsion curve.
The implementation of the CSIDH algorithm mainly uses Montgomeryβs fast arithmetic of elliptic
curves y2 = x3 + Cx2 + x, C β Β±2, containing two points of the 4th order and, respectively, having the
order NE = 4n (n is odd) [9]. In the work [4] the algorithm is built on complete SEC of the same order.
In this work, for the first time, we propose to use in the CSIDH algorithm twisted and quadratic SEC,
which have the same record-breaking speed performance indicators as the complete Edwards curves
[11].
This possibility arises on the basis of the theorems we proved in [1]. With a minimum cofactor of
eight, the order of twisted and quadratic SEC is NE = 8n. Thus, for these classes of SEC with the order
ππΈ = 8π = π + 1, π = βπΎ π=1 ππ the field modulus in the CSIDH algorithm should be chosen as
p β‘ β1mod8.
Diffie-Hellman non-interactive key exchange scheme includes the following stages [3]:
304
1. The choice of parameters. For small simple odd li. π = βπΎ π=1 ππ is calculated, where the value
K is determined by the safety level and the appropriate modulus of the field π = 2π βπΎ π=1 ππ β 1 , π β₯
3 and starting elliptical curve E0 are selected.
2. Calculation of public keys. Alice with her private key πΊπ΄ = (π1, , π2 , π3, , β¦ , ππΎ, ) constructs an
π π π π
isogenous function π = [π11 , π22 , π33 , β¦ , ππΎπΎ ] and calculates an isogenous curve πΈπ΄ = π β πΈ0 as her
public key. Bob, with the secret key Ξ©B and function b, performs the same calculations and gets his
public key πΈΠ = π β πΈ0 . These curves are determined by their parameters up to isomorphism.
3. Key exchange. Here the protocol is similar to item two with the replacement E0βΆEB for Alice
and E0βΆEA for Bob. Knowing Bobβs public key, Alice calculates πΈπ΅π΄ = π β πΈπ΅ = ππ β πΈ0 .
Similar actions of Bob give the result EAB = b * EA = ba * E0, which coincides with the first due to
the commutativity of the group operation. The J-invariant of the curve (EBA) is taken as the shared
secret.
Below we present a modification of Aliceβs computation algorithm according to item 2 [3] using
isogenies of twisted and quadratic SEC.
Algorithm 1: Evaluating the class-group action on twisted and quadratic SEC.
Input: dA β EA, Ο(d) = 1 and a list of integers Ξ©A = (e1,e2,β¦,eK).
Output: dB such that [l1 , l 2 ,...l K ] * E A ο½ E B , where A, B
e1 e2 eK
E : x 2 ο y 2 ο½ 1 ο d Π, Π x 2 y 2 ,
1. While some ei β 0 do
2. Sample a random x β F.
3. Set s β 1, EA: x2 β y2 = 1 β dAx2y2, if (x2 β 1)/(1 β dx2) is a square in Fp.
4. Else s β β1, EAt: x2 + y2 = 1 + dAx2y2.
5. Let S = {i | sei > 0}. If S = β
then start over to line 2 while s β βs.
6. Let π = βπβπ ππ and compute R β [(p + 1)/2k]P, P = (x,y).
7. For each i β S do
8. Compute Q β [k/li]R.
9. If Q β (1,0), compute an isogeny Ο: EA β EB with ker Ο = Q.
10. Set dA β dB, R β Ο(R), k β k/li, and finally ei β ei β s.
11. Return dA.
In comparison with Algorithm 2 in the work [3] in our algorithm 1, adapted to twisted and quadratic
SEC, modifications were made:
1. The repeated selection of a random point (Item 5) is performed until it falls after the original
curve EA into the curve (EtA) of quadratic torsion (y2 β βy2). The check of quadraticity y2 in Item 3 is
performed for the twisted Edwards curve equation (4).
2. The set S of indices of positive and negative exponentials {ei} is formed twice according to
Item 5.
3. For twisted Edwards curve order NE = 8n = p + 1 with the maximum order of the point
NE / 2 = 4n to get the point of the order n it is enough to double a random point P twice. In item 6 this
property is taken into account by decreasing one doubling in the point product. According to Item 10
for each li exactly ei of isogenies is calculated until the exponent ei is zeroed. Depending on its sign,
isogenies are calculated in the twisted class (ei > 0) or quadratic SEC class (ei < 0).
The construction of isogenies of odd simple degrees for quadratic Edwards curves is based on the
Theorem 2 [7], for the twisted Edwards curvesβon the Theorem 1 [1]. In the last work, the formulas
of mapping Ο(P) for the curve (1), depending on two parameters a and d, are presented for the first time.
They are formulated below.
Theorem 1 [1]. Let us G = {(1,0),Β±Q1,Β±Q2,β¦,Β±QS,} is subgroup of odd simple order l = 2s + 1 of
the points Β±Q1 = (Ξ±i,Β±Ξ²i) of the curve Ed over the field Fp.
We define
ο¦ xP ο«Qi xP οQi yP ο«Qi yP οQi οΆ
ο¦ ( P) ο½ ο¨ xο’, yο’ ο© ο½ ο§ ο ,ο ο·
ο§ QοG xQ xοQ QοG xQ xοQ ο·
ο¨ i i i i οΈ
Then Ο(x,y) is an l-isogeny with the kernel G from the curve Ea,d into the curve EaΚΉ,dΚΉ with parameters
aΚΉ = al, dΚΉ = A8dl, π΄ = βπ π=1 πΌπ , and the mapping function
305
ο¦ x s (ο‘ x)2 ο a 2 ( ο’i y)2 y s (ο‘ i y)2 ο ( ο’i x)2 οΆ
ο¦ ( x, y) ο½ ο§ 2 ο i ο½1 i , 2 ο i ο½1 ο· (6)
ο¨ A 1 ο ( d ο‘ ο’
i i xy ) 2
A 1 ο (dο‘i ο’i xy)2 οΈ
or
ο¦ x s x 2 ο aο’i 2 ο y s x 2 ο ai 2 οΆ
ο¦ ( x, y) ο½ ο§ 2 ο i ο½1 , ο ο· (7)
ο¨A 1 ο d ο’i x 2 A2 i ο½1 a ο dο‘ i x 2 οΈ
Its proof is given in [1].
Letβs consider a simple model for the implementation of the CSIDH algorithm on twisted and
quadratic SEC that form pairs of quadratic torsion with the same order. Such curves exist only at
pβ‘ β1mod8 and have the order NE = NtE = p + 1 = cn(n β odd), c β‘ 0mod8. Let such pair of curves
contain the kernels of the 3rd and 5th order at the minimum value n = 15, then the minimal simple is
p = 239 and the order of these curves is NE = 16n =240. The parameter d of the whole family of 118
quadratic Edwards curves can be taken as squares d = r2modp, r=2..119. Of these, 30 pairs of quadratic
and twisted SEC were found with parameters a = Β±1 and ad. Let us denote a quadratic SEC as Ed and
a twisted SEC (4) as Eβ1,βd. Table 1 shows the values of parameters for pairs of quadratic and twisted
SCEs. They are written as squares in ascending order d = r2modp, r=5..119.
Table 1
Values of parameter d of quadratic and twisted SECs (a = Β±1) at p = 239 and NE = 240
25 64 121 196 50 183 5 10 87 176
24 153 11 110 48 187 120 193 27 160
213 44 2 201 61 3 206 192 80 62
For the 1st curve Eβ1,β25 = E(0)β1,βd from Table 1 we can construct 3- and 5-isogenies and find chains
of isogenous curves E(i)β1,βd, i = 1,2,β¦,Ο, such as E(Ο)β1,βd = E(0)β1,βd. The parameter a of all isogenous
twisted SEC can be fixed as quadratic non-deduction a = β1, because, according to theorem 1,
a(i+1) = (a(i))l= β1 for all odd degrees l.
The curve Eβ1,β25 contains the point of the 3rd order Q1 = (149,64), then, according to Theorem 3 [7]
π΄ = βπ π=1 πΌπ = 149, π΄8 = 8, π(1) = π΄8 (π(0) )3 = 3. Calculated parameters d(i), J(d(i)) of the chain of
3-isogenous curves with the start value d = 25 are given in the first half of Table 2. The period of the
chain Ο = 5 divides the number of all twisted SEC, equal to 30. By setting a different start value d = 2
from Table 1, we can get another sequence of parameters d(i) β {2,61,62,193,5,2} with period 5 with
values from Table1. Parameters of the 2nd chain are given in the second half of Table 2. For 3-isogenies
it is possible to calculate 3 tables similar to Table 2 with non-overlapping values d(i) of Table 1. The
π π
data in Table 2 are used for twisted SEC when constructing the function[π11 , π22 ], π1 = 3, π1 > 0.
With negative values of exponents π1 < 0 the results of similar calculations for quadratic SEC with
other kernels Q of the 3rd order are given in Table 3. We emphasize that in comparison with Table 2,
the same values of the parameters d(i) on the period of the chain are run in reverse order here.
The kernel of the 5-isogeny on the curve Eβ1,β25 is the subgroup of points of the 5th order
Q1 = (Ξ±1,Ξ²1) = (β95,28), 2Q1 = Q2 = (Ξ±2,Ξ²2) = (β72,β119), 3Q1 = β2Q1 = (Ξ±2,βΞ²2), 4Q1 = βQ1 = (Ξ±1,βΞ²1),
5Q1 = O = (1,0). It is unequivocally determined by the coordinates Ξ±1,Ξ±2 of two points and the equation
(4). For each 5-isogenous curve we calculate A(i) = Ξ±1(i)Ξ±2(i), d(i+1) = (A(i))8(d(i))5, i = 0,1,β¦ The results of
calculating the parameters of the chain of 5-isogenic twisted SCEs are given in Table 4.The period of
this chain is Ο = 15 and we can construct one more similar table (up to cyclic shift) with the other half
of parameters of Table 1. For quadratic SEC, the results of similar calculations are summarized in
Table 5. The data from Tables 4, 5 are used for twisted , (π2 > 0) and quadratic SECs (π2 < 0) when
π π
constructing the function [π11 , π22 ], π2 = 5.
306
Table 2
Values of parameters of 2 chains of 3-isogeneous twisted SECs (a = β1) at p = 239
i 0 1 2 3 4 5 0 1 2 3 4 5
Ξ±(i) 149 227 152 174 179 149 137 177 221 129 66 137
Ξ²(i) 25 3 10 50 110 25 193 5 2 61 62 193
J(d(i)) 225 105 55 105 225 225 215 113 218 235 217 215
Table 3
Values of parameters of 2 chains of 3-isogeneous quadratic SECs (a = 1) at p = 239
i 0 1 2 3 4 5 0 1 2 3 4 5
Ξ±(i) 97 116 157 197 113 97 172 101 61 17 109 193
Ξ²(i) 25 110 50 10 3 25 193 62 61 2 5 193
(i)
J(d ) 225 225 105 55 105 225 215 217 235 218 113 215
Table 4
Values of parameters of a chain of 5-isogeneous twisted SECs (a = β1) at p = 239
i 0 1 2 3 4 5 6 7
Ξ±1 ,Ξ±2 β95,β72
(i)
69,β53 57,β8 103,β102 107,β34 118,184 25,221 41,187
βd(i) 25 2 11 50 193 187 3 61
J(d(i)) 225 218 215 105 215 215 105 235
i 8 9 10 11 12 13 14 15
Ξ±1(i),Ξ±2 103,151 79,148 51,108 171,196 13,193 136,193 191,231 144,167
βd(i) 183 110 5 121 10 62 201 25
J(d(i)) 218 225 113 327 55 217 113 225
Table 5
Values of parameters of a chain of 5-isogeneous twisted SECs (a = β1) at p = 239
i 0 1 2 3 4 5 6 7
Ξ±1 ,Ξ±2
(i)
84,204 4,236 82, 230 31,201 42,204 22,206 17,237 16,211
βd(i) 25 201 62 10 121 5 110 183
J(d(i)) 225 113 217 55 327 113 225 218
i 8 9 10 11 12 13 14 15
Ξ±1(i),Ξ±2 175,223 138,229 50,156 116,203 27,156 104,207 5,11 84,204
βd(i) 61 3 187 193 50 11 2 25
J(d(i)) 235 105 215 215 105 215 218 225
We will accept private keys of exponential isogeny {ei} of Alice and Bob Ξ©A = (1,β2), Ξ©A = (β4,3),
their isogenous functions, respectively, π = [31 , 5β2 ], π = [3β4 , 53 ]. Let`s calculate their public keys
dA,dB. As a start curve of the chain of isogenies we accept the curve E(0) = Eβ1,β25. Alice calculates the
parameters of 3-isogenous curves E(i): one 3- isogenous twisted SEC, two 5-isogenous quadratic SECs
at random.
1. Calculation from left to right. From Table 2 at the first step we immediately get
d(0) = 25 β d(1) = 3 βΉ E(1) = Eβ1,β3. For calculation of 5-isogenous curves we pass to the class of
quadratic torsionβto the quadratic curve E(1) = E1,3 = E3. According to Table 5 we get
d(1) = 3 β d(2) = 187 β d(3) = 193 βΉ E3 β E187 β E193 βΉ E(3) = E193. Returning to the class of twisted
SECs gives E(3) = Eβ1,β193. So Aliceβs public key is dA = 193. The default for the twisted SEC class is
aA = β1.
2. Calculation from right to left. For this case, at first in the class of quadratic curves, Alice
calculates two 5-isogenous quadratic curves from Table 5 E25 β E201 β E62 βΉ E(2) = E62. Then she
goes to the twisted curve Eβ1,β62 and calculates one 3-isogenous curve. From Table 2 we get the final
result E(2) = Eβ1,β62 β E(3) = Eβ1,β193 βΉ dA = 193. This example illustrates the commutability of
isogenous mappings in the CSIDH algorithm.
307
Bobβs public key is calculated in the same way. At e1 = β4 the first isogenous curve is the quadratic
curve E(4) = E3 from Table 3. Calculation of the next three 5-isogenous twisted curves (e2 = 3) in
accordance with Table 4 gives the curve E(7) = EB = Eβ1,β110 and the value of Bobβs public key
dΚΉ = d(3) = dB = 110. Calculations from right to left give the same result.
Further, in the secret sharing scheme, Alice knowing Bobβs public key calculates the isogenous
curve EBA = [31,5β2)*Eβ1,β110. From Table 2 for twisted SECs we get d(0) = 110 β d(1) = 25, then from
Table 5 for quadratic SECs is d(1) = 25 β d(2) = 201 β d(3) = 62. As a result, EBA = Eβ1,β62 βΉ dBA = 62.
Calculations of Bob in the secret sharing EAB = [3β4,53)*Eβ1,β193. From Table 3 for quadratic SEC we
get d(0) = 193 β d(1) = 62 β d(2) = 61 β d(3) = 2 β d(4) = 5, then from Table 4 for twisted SECs is
d(4) = 5 β d(5) = 121 β d(6) = 10 β d(7) = 62. As a result, EAB = EBA = Eβ1,β62 βΉ dAB = 62. Aliceβs and
Bobβs results are identical.
According to Algorithm 1, isogenous functions (7) with kernels of degrees li along with dot products
of points can be effectively used to calculate points of corresponding simple orders in chains of
isogenous curves.
The mapping (7) of the points P = (x,y) of the curve EA = Eβ1,β25 with the kernel of 3-isogeny
G = {(1,0),Β±Q = (149,Β±64)} has the form
x x 2 ο aο’ 2 y x 2 ο ο‘ 2 ο¦ x x 2 ο« 642 y x 2 ο 1492 οΆ
ο¦3 ( x, y) ο½ ο ο ο ο½ ο§ ο , ο·
A2 1 ο d ο’ 2 x 2 A2 1 ο« dο‘ 2 x 2 ο¨ 1492 1 ο« 252642 x 2 1492 1 ο 2521492 x 2 οΈ
The point of maximum odd 15th order P = (β44,β12) of the curve Eβ1,β25 is mapped to the point
PΚΉ = (221,125) of the 5thorder of the curve Eβ1,β3, the point of the 5th order P = (144,28) is mapped to the
point PΚΉ = (25,183) of the 5th order, and the point of the 3rd order P = (149,64) is mapped to the neutral
element of the groupβthe point PΚΉ = (1,0) = O. As we see, the function Ο3(x,y) reduces the orders of
points of the preimage that are multiples of three and does not change the orders of other points.
For the same curve Eβ1,β25 with the kernel of the 5th order G = {(1,0),Β±Q1 = (β95,Β±28),Β±Q2 = (β72,β
119)} of the 5th isogeny in the form (7) is written as
ο¦ x x 2 ο« 282 x 2 ο 952 y x 2 ο« 1192 x 2 ο 722 οΆ 2
ο¦5 ( x, y) ο½ ο§ 2 ο ο , ο ο 2 2 2ο·
, A ο½ (95 ο 72) 2 ο½ 155
ο¨ A 1 ο« 25 2 2 2
64 x 1 ο 25 2 2 2
95 x A 2
1 ο« 25 2
119 2 2
x 1 ο 25 72 x οΈ
The point of the 15th order P = (β44,β12) of the curve Eβ1,β25 is mapped into the point PΚΉ = (β18,7) of
the 3rd order of the curve EΚΉβ1,β2. The point of the 3rd order P = (149,64) is mapped into the point
PΚΉ = (β18,β7) of the 3rd order of isogenous curve, the point of the 5th order P = (β95,28) is mapped into
the point PΚΉ = (1,0) = O. Here the function Ο3(x,y) reduces the orders of the preimage points, which are
multiples of 5, by 5 times, without changing the orders of other points.
Calculations of the isogenies of twisted and quadratic SEC in projective Farashahi-Hosseini
coordinates [6] (W:Z) with replacement w(x,y) = dx2y2 based on the method proposed in [4] were
considered in the previous paper [1] using Theorems 1 and 2 proved there.
The results of the implementation of the Edwards-CSIDH model [4] in projective coordinates claim
that it is faster than the Montgomery-CSIDH model in coordinates (X:Z) by 20%.
We note that the Edwards-CSIDH model [4] is built on complete Edwards curves with the order
NE = p + 1 = 4n (n is odd). On the basis of Theorems 1 and 2 [1] in this paper we have shown how to
implement such a model on twisted and quadratic SEC forming pairs of quadratic torsion.
The advantage of these classes of curves over the complete Edwards curves is the absence of the
laborious inversion of the parameter d β dβ1, which is necessary in the transition to the complete curve
of quadratic torsion. This only speeds up the execution of the algorithm. However, with the same
maximum order of the point 4n, the order of these curves NE = 8n is twice as large as compared to the
complete ones, which is hardly significant.
4. Conclusions
It can be concluded that the method for calculating isogenies of odd degrees in coordinates (W:Z),
proposed in [4], using full and twisted supersingular Edwards curves, allows us to implement the fastest
computations for today when constructing the PQC CSIDH protocol and the like. The theorems proved
308
in [1] open up classes of twisted and quadratic Edwards curves for their implementation. This article is
the first to show such an implementation for a simple model of the CSIDH algorithm.
5. References
[1] Bessalov, A., Sokolov, V., Skladannyi, P., Zhyltsov, O. Computing of odd degree isogenies on
supersingular twisted edwards curves. CEUR Workshop Proceedings, 2021, 2923, pp. 1β11.
[2] D.Jao, and L. de Feo, Towards quantum-resistant cryptosystems from supersingular elliptic curve
isogenies, Post-Quantum Cryptography pp. 19β34 (2011).
[3] Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.: CSIDH: An efficient post-quantum
commutative group action. In: Peyrin, T., Galbraith, S. (eds.) Advances in Cryptology {
ASIACRYPT 2018. pp. 395β427. Springer International Publishing, Cham (2018).
[4] Suhri Kim, Kisoon Yoon, Young-Ho Park, and Seokhie Hong. Optimized Method for Computing
Odd-Degree Isogenies on Edwards Curves. Security and Communication Networks, 2019 (2019).
[5] Farashahi, R.R., Hosseini, S.G.: Differential addition on twisted Edwards curves. In: Pieprzyk, J.,
Suriadi, S. (eds.) Information Security and Privacy. pp. 366{378. Springer International
Publishing, Cham (2017).
[6] Suhri Kim, Kisoon Yoon, Jihoon Kwon, Seokhie Hong, and Young-Ho Park Efficient Isogeny
Computations on Twisted Edwards Curves Hindawi Security and Communication
NetworksVolume.
[7] Moody D, Shumow D. Analogues of Velus formulas for isogenies on alternate models of elliptic
curves. Mathematics of Computation, vol. 85, no. 300, pp. 1929β1951, 2016.
[8] A. Bessalov, V. Sokolov, P. Skladannyi. Modeling of 3- and 5-Isogenies of Supersingular Edwards
Curves // Proceedings of the 2nd International Workshop on Modern Machine Learning
Technologies and Data Science (MoMLeT&DSβ2020), June 2β3, 2020: abstracts. β No. I, vol.
2631. β Aachen : CEUR, 2020. β P. 30β39.
[9] Bernstein D.J., Lange T. Faster Addition and Doubling on Elliptic Curves // Advances in
CryptologyβASIACRYPTβ2007 (Proc. 13th Int. Conf. on the Theory and Application of
Cryptology and Information Security. Kuching, Malaysia. December 2β6, 2007. Lect. Notes
Comp. Sci. V. 4833. Berlin: Springer, 2007. P. 29β50.
[10] Bernstein Daniel J. , Birkner Peter , Joye Marc , Lange Tanja, Peters Christiane. Twisted Edwards
Curves.// IST Programme under Contract ISTβ2002β507932 ECRYPT,and in part by the National
Science Foundation under grant ITRβ0716498, 2008.
[11] Bessalov A.V. Elliptic curves in Edwards form and cryptography. Monograph. Polytechnic, Kyiv,
2017. 272p.
[12] Bessalov A.V., Tsygankova O.V. Number of curves in the generalized Edwards form with minimal
even cofactor of the curve order. Problems of Information Transmission, Volume 53, Issue 1
(2017), p. 92β101. doi:10.1134/S0032946017010082
[13] Bessalov, A.V., Kovalchuk, L.V. Supersingular Twisted Edwards Curves Over Prime Fields. I.
Supersingular Twisted Edwards Curves with j-Invariants Equal to Zero and 123. Cybernetics and
Systems Analysist, 2019, 55(3), ΡΡΡ. 347β353.
[14] Bessalov, A.V., Kovalchuk, L.V.Supersingular Twisted Edwards Curves over Prime Fields. II.
Supersingular Twisted Edwards Curves with the j-Invariant Equal to 663. Cybernetics and Systems
Analysist, 2019, 55(5), ΡΡΡ. 731β741.
[15] Washington, L.C. Elliptic Curvres. Number Theory and Cryptography. Second Edition. CRC
Press, 2008.
[16] 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.
309