Some properties of isogenies of non-cyclic supersingular Edwards curves, which are used in the implementation of the CSIDH algorithm, are considered. This article continues the consideration of properties using the example of these classes of supersingular Edwards curves from previous work. All isogeny calculations are performed using one parameter of the curve equation d. Isogeny properties are modeled on an isogeny graph and are considered graph properties. Recommendations are given for selecting some cryptosystem parameters. It is shown which parameters d are prohibited for use in CSIDH algorithms and that the transition from one isogeny to another is not always possible.
The works [1] present a modification of the
CSIDH algorithm, built on isogenies of
noncyclic Supersingular Edwards Curves (SEC) [
This article presents new results of studying isogenies of non-cyclic supersingular Edwards curves using graphs that were also previously used in articles [7–9].
At one of the stages of the algorithm, group
operations are performed on lk -isogeny
cycles. The number of steps in operation [ lk ek ]
corresponds to the secret exponent of the
vector Ωκ = (e1, e2, …, eK, …). Work [
The article models the choice of a vector of exponents of a secret key by an isogeny graph [9]. The study of the parameters of isogenic curves continued using the example of 840 order curves.
The work [1] considers an example of
constructing isogenies for non-cyclic SEC with
parameters (a = 1) , p = 839 , N E = 840
(66 curves). There are values of 66 parameters
d for all 66 curves and provides calculations
of isogenies of degrees 3, 5, and 7 for 33 curves
in that work. It is shown that the choice of some
curves is unsuccessful (curve with d=733).
This article shows which other d parameters
are prohibited. In addition, it is shown that the
transition from one isogeny to another is not
always possible.
2. Theoretical Foundation
The PQC CSIDH (Commutative SIDH)
algorithm was proposed by the authors of [9]
to solve the key exchange problem
(SIDHSupersingular Isogeny Diffie-Hellman [
Let the curve E order NE contains points of small odd orders lk , k = 1,2,..., K. Then there is an isogenic curve E same order NE .
In the algorithm, repeating this operation ek times denoted by [lk ek ]* E . Isogeny exponent values ek Z determine the length of the chain of isogenies of degree lk . In [12], the range of exponent values was adopted [−m ek m], m = 5, K = 74, which provides a 128-bit security level against quantum computer attacks. Negative values of the exponent mean a transition to a supersingular quadratic torsion curve [1].
Non-interactive Diffie-Hellman key exchange involves three stages [9]. The second stage is the Calculation of public keys. Each participant using his secret key A = (e1, e2 ,.., eK ) builds an isogenic mapping A = [l1e1 , l2e2 ,..,lK eK ] and calculates the curve EA = A * E0 . For each li is calculated exactly ei isogeny.
In [11] the mapping formulas (P) are given for SEC, depending on two parameters a and d. It shows that (x, y) is l -isogeny from the curve Ea,d into a curve Ea,d with parameters: a = a l , d = d l A8 ,
s , A = i=1 i (1)
The parameter d uniquely defines the curve. We will use (1) to calculate the parameters of the chain of isogenies.
In [1] the implementation of the CSIDH algorithm on quadratic and twisted (SECs), forming quadratic torsion pairs with the same order is considered. Such curves exist only when and have order N E = N Et = p + 1= cn (n − odd ), c 0 mod 8. Let such a pair of curves contain kernels of the 3rd, 5th, and 7th orders with the value n = 105, then the minimum prime p = 8т −1 = 839 and the order of these curves N E = 8n = 840 . The parameter d of the entire family made 418 quadratic Edwards curves. This parameter is equal squares d = r 2 mod p,r = 2.419. From these 66 pairs of quadratic and twisted SECs with parameters [1] a = 1 и (ad ) = 1 were found.
For the first curve Ed (0) = E144 in [1], 3-, 5and 7-isogenies were constructed and the parameters d (i) of isogenic chains of curves Ed (i) ,i = 0,1,2,...,Т were found. Curve E144 gives rise to a chain of isogenies of degree 3 with a period of 33. It includes half of all curves of order 840. Let’s call them the first segment of curves. Chains 5 and 7 of isogenies also consist of these same curves.
Fig. 1 shows the graph of these isogenies of the first segment. The graph shows one chain of 3isogenies, where the values of the parameter d of the isogenic curves are shown inside the yellow, green, and gray rectangles. The chain starts from curve d=144 and the next calculated isogeny is located clockwise.
Isogenies of degrees 5 and 7 form two chains of each degree (two pairs). In Fig. 1, chains of isogenies of degree 5 are indicated by solid arrows and degrees 7 by dotted arrows. The first chain of each pair contains identical curves from 1/3 of all curves, i.e. have a period of 11 (in Fig. 1a they are indicated in yellow). The second of each pair of chains contains curves from the second one-third of all curves (indicated in green in Fig. 1b). And one-third does not have isogenies 5 and 7 degrees (empty points of the graph are indicated in gray).
In addition to the above, this work also presents isogeny graphs containing the second half of 66 curves of order 840 (second segment) Fig. 2. They also form a chain of 3isogenies with a period of 33 and a pair of chains of 5 and 7 isogenies with a period of 11. The first curves are marked in yellow. The second curve is marked in green. In the chain of 3-isogenies, the starting point was the point d = 784 from Table 1 [1] (Fig. 2).
The structure of all isogenies of Edwards supersingular curves is presented in Fig. 3. All curves form two non-intersecting segments of 33 curves in every. The curves of each segment form one chain of isogenies of degree 3 (period 33) and a pair of chains of degrees 5 and 7. A total of 2 chains of 3-isogenies, 4 chains of 11 order isogenies of degree 5, and 4 chains of 11 order isogenies of degree 7.
Table 1 shows some of the points of each segment and which chains of isogenies of degrees 5 and 7 these points are included in. First chains b 0 59 First chains 76 3 chain of 3-isogeny SEC (1st segment of
33 curves) 02 0 28 0 59 7 7 0 2 52 73 15 4 52 5
7 42 7-isogeny 3 6 5 Make a transition between chains of isogenies of degrees 5 and 7 (in both directions) only if their numbers in the pair match (i.e. within the same color of yellow or green in Fig. 1 and Fig. 2). You can also switch to the chain of 3isogenies at any step, and from the chain of 3isogenies you can get to the chains of 5 and 7 isogenies only at 11 points of the chain of 3isogenies. In the first segment, you can go to the first chain of 5 and 7 isogenies only from yellow points 144, 76,258, 293, 243, 2, 788, 636, 112, 182, 752, and to the second chain from green points. And accordingly for the second segment.
The graph shows that the exponent in the vector Ωκ = (e1, e2, …, eK) corresponding to isogeny l3 3 degrees must be a multiple of 3. Only after every 3 steps, you can get to points coinciding with the graph of 5 or 7 isogenies. 66 SEC order 840
Chain 3-isogenic period 33 11 curves 11 curves 11 curves 1st chain
2nd chain 5-isogeny period 11 1st chain
2nd chain
period 11
Chain 3-isogenic period 33 11 curves 11 curves 11 curves 1st chain
2nd chain 5-isogeny period 11 1st chain
2nd chain
Fig. 4 shows examples of graph transitions for group operations a) Е144 *[l33 l53 l72] = Е243 and b) Е289*[l36 l52 l72] = Е433.
Transitions are carried out between isogenies with parameters: d = 144->243 and d = 144->243.
6 93 Е144 *[l33 l53 l72] = Е243 88 0 05
4 6 72 1 12 1 38 0 66 The figure shows that the number of steps along the chain of 3-isogenies is always a multiple of 3. Otherwise, it is impossible to get to the chains of isogenies of degrees 5 and 7. The figure shows steps 3 and 6 along the chain of 3-isogenies. half, and this must be taken into account when implementing the CSIDH algorithm. It should be noted that given the huge number of isogenies in real systems, these restrictions have virtually no effect on the security of the cryptosystem.
The graph (Fig. 1 and 2) is not fully connected and therefore not all paths between vertices are accessible.
It is not possible to move from a chain of 3isogenies to the rest at an arbitrary point in the graph. You need to choose steps in the 3isogeny chain not arbitrarily, but so as not to end up in empty points of the graph.
The first and second (yellow and green) chains of each pair do not have common curves (common points of the graph), so a direct transition between them is not possible. This transition can be made by returning to the 3rd order chain and passing along several steps so as not to end up in an empty (gray) point. The transition between segments is generally impossible because the corresponding graphs do not have common points.
Such properties of the isogeny graph somewhat limit the freedom of wandering around the graph and the number of paths between curves is reduced by approximately