Modeling CSIKE Algorithm on Non-Cyclic Edwards Curves

Abstract

An original key encapsulation scheme is proposed as a modification of the CSIDH algorithm built on the isogenies of non-cyclic Edwards curves. The corresponding CSIKE algorithm uses only one public key of the recipient. A brief review of the properties of non-cyclic quadratic and twisted supersingular Edwards curves is given. We use a new scheme for modeling the CSIKE algorithm on isogenies of 4 degrees 3, 5, 7, 11 for p = 9239. In contrast to the CSIDH models of previous works, this scheme does not use precomputations and tabulation of the parameters of isogenic chains, but uses one known supersingular starting curve Ed with the parameter d = 2. Examples of calculations of isogenic chains by Alice and Bob at three stages of CSIKE operation using a randomized algorithm are given. It also proposes to abandon the calculation of the isogenic function ϕ(R) of a random point R, which significantly speeds up the algorithm.

Keywords

• 1 Curve in generalized Edwards form
• complete Edwards curve
• twisted Edwards curve
• quadratic Edwards curve
• curve order
• point order
• isomorphism
• isogeny
• randomization
• w-coordinates

1. Introduction

The post-quantum cryptography (PQC) algorithm CSIDH [ 1 ] has a well-known advantage over others—the minimum key length, close to the modulus of the prime field Fp, on which group operations are performed. The main criticism of CSIDH relates to its vulnerability to a side channel attack built on measuring the time it takes to compute a chain of isogenies of each prime degree lk proportional to lk and the secret exponent ek of the key. In a large number of papers [ 2, 3 ], the solution to this problem is proposed by increasing the exponents ek by fictitious ones up to a known maximum (Constant time CSIDH). In this paper, we use CSIDH and CSIKE algorithm randomization as an alternative approach to counter this attack. Note that in the key exchange problem today preference is given to key encapsulation schemes. The main goal of this work is to present the original CSIKE (Commutative Supersingular Isogeny Key Encapsulation) algorithm with an illustration of how its model works on the minimum 4 degrees of isogeny. Instead of two public keys in CSIDH, the CSIKE algorithm uses one recipient’s public key.

In [ 4,5 ], the solution of such a problem is proposed on the basis of the well-known KEM (Key Encapsulation Mechanism) scheme, built on the ElGamal encryption algorithm. Its implementation is complex and time-consuming. We propose a simpler, faster and more efficient CSIKE encryption algorithm with one public key as a modification of CSIDH with inversion of the recipient’s private key [ 6–8 ].

As the most efficient technology of the algorithm, classes of non-cyclic quadratic and twisted supersingular Edwards curves (SEC) forming the quadratic twist pairs are proposed [ 9– 11 ]. In comparison with the known implementations of CSIDH on complete Edwards curves [ 12 ], this technology doubles the space of curves used and, moreover, does not require laborious inversion of the curve parameter d in the transition to quadratic twist.

Computing odd degree isogenies on complete and quadratic Edwards curves is carried out according to the formulas of Theorems 2–4 of [ 13 ]. In the fundamental papers [ 14, 15 ], some classes of Edwards curves, in our opinion, received unfortunate terms, which leads to ambiguous classification interpretations.

We use the of curves in the generalized Edwards form with two parameters a and d [ 16, 17 ] with their division into three non-intersecting generalized the theorems of [ 12 ] to curves in the generalized possible in [ 9–11 ] to apply quadratic and twisted Edwards curves over a field Fp to implement the simplest models of the CSIDH algorithm. To illustrate their work, we used pre-computation and tabulation of the parameters of isogenic chains, which is possible in a limited volume of the article with the number of isogeny degrees not more than three. For a real cryptosystem, this makes no sense. In this article, without pre-computations, we give examples of the CSIKE algorithm work with the construction of random isogenic SEC chains and a starting curve Ed with a parameter d = 2 known from [19]. Such modeling is much closer to the operation of a real algorithm with a large number of isogeny degrees.

An analysis of the properties of quadratic and twisted

Edwards curves that form

pairs of quadratic twist is given in [ 18, 19 ]. Supersingular curves of these classes with the same order NE = p + 1 = 2mn, m ≥ 3 (n is odd) exist only for p ≡ 3mod4. The minimum even cofactor of the order of such curves is 8; then, for the CSIDH and CSIKE algorithms with an odd = ∏ =1 the field

Fp modulus, it should be chosen as p = 8n – 1. In order to adapt the definitions for the arithmetic of the isogenies of Edwards curves and curves in the Weierstrass form, we use a modified point addition law [ 16 ].

Section 2 gives a brief overview of the properties of noncyclic twisted and quadratic supersingular Edwards curves (SEC) [ 18, 19 ]. Section 3 gives a description of the CSIDH [ 1 ] algorithm with its adaptation to classes of noncyclic SEC, and a theorem [ 8 ] on the isogenies of such curves. In Section 4, we present the original CSIKE scheme and give an example of Alice’s calculations at the first stage of her work on a model with isogeny degrees 3, 5, 7, 11 over a prime field Fp at p = 9239. In Section 5, the rationale for the randomization method of the CSIDH algorithm is given, a new randomized CSIKE suggests curve in the algorithm. Examples of calculations by Alice and Bob at three stages of the model of the randomized CSIKE algorithm are given.

2. Brief Review of the Properties of

Non-Cyclic Supersingular Edwards

Curves

We define an elliptic curve in the generalized Edwards form [ 16, 17 ] by the equation , : 2 + 2 = 1 + 2 2, , ∈ ∗, ≠ , ≠ 1.

If the quadratic character is χ(ad) = –1, curve (1) is isomorphic to the complete Edwards curve [ 14, 15 ] with one parameter d : 2 + 2 = 1 + 2 2, ( ) = −1. (2)

Otherwise χ(ad) = 1, χ(a) = χ(d) = 1, the curve (1) is isomorphic with the quadratic Edwards curve [ 16 ] ( ) = 1, ≠ 1, : 2 + 2 = 1 + 2 2, (1) (3) having, in contrast to (2), the parameter d defined as a square. For both curves (2) and (3) one usually takes a = 1. In [ 15 ], curve (3) together with curve (2) are called Edwards curves. At the same time, the difference in the quadratic characters of these curves leads to radically different properties [ 16, 17 ]. In particular, the order of cyclic SKE (2) NE ≡ 0mod4, and noncyclic SEС (3) NE ≡ 0mod8.

The twisted Edwards curve is defined in [ 16 ] as a special case of curve (1) for χ(ad) = 1, χ(a) = χ(d) = –1. Only this class of Edwards curves requires the second parameter a in equation (1). In [ 15 ], all curves in the form (1) are called twisted.

Let us define a pair of quadratic and twisted Edwards curves [ 16, 17 ] as a pair of quadratic twist with parameters χ(ad) = 1, aʹ = ca, dʹ = cd, χ(c) = –1. Since SEC exist only for p ≡ 3mod4 [ 18 ], we can take c = –1, aʹ = –a = –1, dʹ = –d where a and d are the parameters of a quadratic curve, respectively aʹ and dʹ, of a twisted curve. 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. Accordingly, the twisted SEC equation for p ≡ 3mod4 from (1) can be written as −1,− : 2 − 2 = 1 − 2 2, ∈ ∗, ≠ 1, ( ) = 1. (4)

Over a prime field Fp, a supersingular curve always has order NE = p + 1.

So, quadratic and twisted SEC as a pair of quadratic twist have the same order NE = p + 1 but different structure. All their points are different (except two points (0,±1)), so isogenies of the same degree have different kernels. Both curves are non-cyclic with respect to points of the 2nd order (contain 3 points of the 2nd order each, two of which are exceptional points 1,2 = (±√ , ∞) [ 15, 16 ]). Quadratic SEС (3), in addition, contains two exceptional points of the 4th order ± 1 = (∞, ± 1 √

) The presence of a noncyclic subgroup of the 4th order containing 3 points of the 2nd order limits the number 8 to the minimum even cofactor of the order NE = 8n (n is odd) of quadratic and twisted Edwards curves [ 16 ]. In general, their order is NE = 2mn, m ≥ 3. The maximum order of points of these curves is NE/2 = 4n. It is important that points of even orders are not involved in the calculations of the CSIDH algorithm (after the first multiplication of a random point P of maximum order by 4, we have a point of odd order n).

3. CSIDH Algorithm on Quadratic and Twisted Edwards Curves

The

PQC

CSIDH (Commutative Supersingular isogeny Diffie-Hellman) algorithm proposed by the authors of [ 1 ] for solving the key exchange problem based on isogenic mappings of supersingular elliptic curves as additive Abelian groups. Such a commutative mapping over a prime field Fp as the class group action is defined [ 1 ]. It provides the smallest known key size (512 bits in [ 1 ]).

Let the curve E of order NE = p + 1 contain points of small odd orders lk, k = 1, 2, …, K. Then there is an isogenic curve Eʹ of the same order as a lk-degree map: E → Eʹ = [lk]*E. The repetition of this operation ek times we denote [ values of the isogeny exponents ek ∈ Z determine the length |ek| of the chain of isogenies of degree ]*E. The lk. In [ 1 ], an interval of exponential values [–m ≤ ei ≤ m] is accepted m = 5, which provides a security level of 128 bits for a quantum computer attack. Negative values of the exponent mean a transition to a quadratic twist supersingular curve.

The implementation of the CSIDH algorithm in [ 1 ] uses fast arithmetic of Montgomery elliptic curves y2 = x3 + Cx2 + x, C ≠ ±2 containing two points of the 4th order and, accordingly, having an order NE = p + 1 = 4n (n is odd) [ 14 ]. In [ 12 ] the CSIDH algorithm implemented on complete SEC of the same order. In [ 9–11 ] and this paper, we use quadratic and twisted

SECs in the

algorithm, which have the same

CSIDH

speed performance as complete Edwards curves [ 12 ]. In [ 8 ] we proved two theorems for implementation such possibility. With a minimum cofactor of 8, the order of twisted and quadratic SEC is NE = 8n.

Thus, for

these

SEC

1. Choice of parameters. For small odd primes li, compute = ∏ =1 , where the value K is starting elliptic curve E0. determined by the security level (in [ 1 ] K = 74, l74 = 587), and modulus = 2 choose an appropriate field

∏ =1 − 1, m ≥ 3 and a 2. Calculation of public keys. Alice uses her private key ΩA = (e1, e2,

…, eK) to build an isogenic mapping ΘA = [ 11, 22, …, ] (class group action [ 1 ]) and calculates the isogenic curve EA = ΘA*E0 as her public key. Based on the secret key ΩB and function ΘB, Bob performs the same calculations and obtain his public key EB = ΘB*E0.

These curves are defined their parameters dA,dB up to isomorphism, which are accepted as public keys known to both parties.

3. Sharing secrets. Here the protocol is similar to item 2 with replacements E0 → EB for Alice and E0 → EA for Bob. Knowing Bob’s public key, Alice calculates EBA = ΘA*EB = ΘAΘB*E0. Similar actions of Bob give a result

EAB = ΘB*EA = ΘBΘA*E0 that coincides with the first one due to the commutatively of the group operation. The Jinvariant of the curve EAB(EBA) is accepted the shared secret.

Below we present a modification of Alice’s computational algorithm according to item 2 [ 1 ] using isogenies of quadratic and twisted SEС.

Algorithm 1: Evaluating the class-group action on twisted and quadratic SEC. 1. While some ek ≠ 0 do

2. Sample a random x ∈ Fp,

Input: dA ∈ EA, χ(d) = 1 and a list of integers ΩA = (e1, e2, …, eK). 7. For each k ∈ S do 3. Sеt a ← 1, EA: x2 + y2 = 1 + dAx2y2 if (x2 – 1)(dy2 – 1) is a square in Fp, 4. Else a ← –1, EA: x2 – y2 = 1 – dAx2y2, 5. Let S = {k | aek > 0}. If S = ∅ then start over to line 2 while a ← –a, , and compute R ← [(p + 1)/2n]P, P ← P(x,y),

8. Compute Q ← [n/lk]R

9. If Q ≠ (1,0), compute an isogeny ϕ: EA → EB with ker ϕ = Q, 10. Set dA ← dB, R ← ϕ(R), ek ← ek – a, 11. Skip k in S and n ← n/lk if ek = 0, 12. Return dA.

In comparison with Algorithm 2 in [ 1 ], our Isogeny: Key Encapsulation (CSIKE) algorithm, Algorithm 1, adapted to twisted and quadratic which, like [ 4, 5 ], includes three stages: 1. Checking the square in line 3 use the number generator, finds a secret vector Ωκ = (e1,

SEC, has some modifications:

equation of the quadratic Edwards curve (3).

2. Lite 10 has been corrected (you cannot reset the index k before zeroing ek in line 10).

3. Updating the number n ← n/lk and reset k in line 11 we perform after zeroing ek.

According to line 10, exactly |ek| isogenies we calculate for each lk until the exponent ek is set to zero.

Depending

on its sign, isogenies are calculated in the class of quadratic (ek > 0) or twisted SEC (ek < 0).

The construction of isogenies of odd prime degrees for quadratic Edwards curves based on

Theorem

2 [ 13 ], and for twisted

Edwards curves—Theorem 1 [8]. In the last work, for the first time, mapping ϕ(P) formulas for the curve (1) are given, depending on two parameters a and d.

4. CSIDH Algorithm on Quadratic and Twisted Edwards Curves

The classic non-interactive

Diffie-Hellman algorithm is based on the use of two public keys. The same task of forming a shared secret can be solved in a protocol with one transmission session and one public key of the recipient, which is more secure. To do this, Alice generates a shared secret, encrypts it with Bob’s public key, and sends him the encrypted key (the encapsulation key). Bob decrypts it with his private key. This protocol is called key encapsulation.

Based

on

CSIDH, we propose its modification—the Commutative Supersingular e2, …, eK), builds an isogenic map Θκ = [ …, ] and calculates an isogenic curve Eκ = Θκ*E0 whose parameter d is taken as d = κ.

2. Key encapsulation. This is the procedure for Alice to encrypt a key with Bob’s public key EB. To do this, Alice computes an isogenic curve Θκ*EB = EκB. The parameter dκB of this curve as an encrypted key is sent to Bob.

3. Key decapsulation. Bob’s decryption of the curve EκB with his secret key ΩB is reduced to his calculation of the isogenic curve ̅Θ̅̅̅*EκB = Eκ , where the inverse function ̅Θ̅̅̅ is constructed by inverting all signs of the exponent of Bob’s secret 11, 22, key: ΩB → (–ΩB).

Consider a simple implementation model of the CSIKE algorithm on quadratic and twisted SEC that form pairs of quadratic twist with the same order p + 1. Such curves exist only for p ≡ –1mod8 and have order NE = NEt = p + 1 = cn (n is odd), c ≡ 0mod8.

Let such a pair of curves contain points of prime order 3, 5, 7, 11, then n = 1155, the minimum prime p = 8n – 1 = 9239 and the order of these curves NE = 8n =9240. The number of supersingular curves at a rough estimate 2√ in this

model is close to 200; therefore, the parameters of all such curves and their exact number are assumed to be unknown. Unlike previous models [ 9–11 ], which use precomputation and tabulation of the parameters of isogenic chains on a period, in this paper we proceed only from the known starting curve E0 and Algorithm 1, which brings the model closer to a real cryptosystem. As a starting curve E0, we can take the Edwards curve (3) for d = 2 which is supersingular with J-invariant J = 663 [ 18 ]. Let us pose the problem of calculating isogeny chains at stage 1 of the CSIKE algorithm.

Let’s take the secret key vector Ωκ = (4,–3, –3,2), then the group action class function, respectively Θκ = [34,5–3,7–3,112)]. According to this function, Alice calculates the secret key κ. For the starting curve, we take

Ed(0) = E2, then Eκ = E2*Θκ. In our example, the length of the chain of isogenies, equal to the sum of the absolute values of the exponents, is 12. At each step, you can choose any of the 4 degrees of isogenies, then there are 224 paths leading to one result. A result can be considered reliable if it is found in at least two ways.

If the calculations are carried out according to the function Θκ and algorithm 1 from left to right, first for curves Ed(i) (ek > 0), then for curves E–1,– d (i) (ek < 0), it is possible to construct two chains of length 6 each.

Example 1. The starting curve is the SEC Ed(0), d = 2. Let us consider Alice’s calculations at the first step according to Algorithm 1. For isogenies of degrees 3 and 11, we first need to find a random point R33 of the curve E2 of order n0 =3·11=33.

According to

Algorithm 1, we determine a order. The kernel of the 3-isogeny is the point Q3 = 11R33 = (–6153,3016) of the 3rd order. Finally, using formula (6), we determine the parameter of the isogenic curve d(1) = 5861.

In

order to simplify the notation in the algorithm for calculating an isogenic curve Eκ = E2*Θκ, we will use only the parameters d(i), which completely

determine the curves (ek > 0) and E–1,–d(i) (ek < 0) as pairs of quadratic twist. For the first chain of length 6 curves Ed(i) Ed(i) (ek > 0), Alice’s calculations can be written as (0) = 2 1 (1) = 5861 1 7935 1 (3) →

(3) → conditionally set the degree of isogeny, and above the arrow, the value a of parameter of the curve Ed or E–1,–d.

Continuation of calculations for isogenic curves of degrees 5 and 7 gives the results degrees of isogenies from the highest to the lowest (in the same class of curves), we obtain the second path of the chain with the results and d(6) = 4637, coincide on the first and second calculation paths. The last result is explained by the fact that it completes a chain of length 6 for all curves Ed(i) (ek > 0) and is the same when the degrees of 3- and 11-isogenies are interchanged. However, such a collision event reduces the security of the CSIDH and CSIKE algorithms. We propose an approach free from this shortcoming [ 11 ].

5. Randomization of the CSIKE

Algorithm

The CSIDH algorithm proposed by the authors of [ 1 ] (Algorithm 1 in Section 3) is constructed in such a way that the calculations of isogenic chains = [ 11, 22, … , ] are according to functions Θ , performed in two stages: first, a set S with key exponents ek of one sign is formed, then another.

At each stage, the kernels and parameters of exactly |ek| isogenic curves of isogenies of degrees lk constructed on curves of the same class (Ed or E–1,–d) are successively calculated. This obviously gives rise to the threat of a side channel attack based on the measurement of the time of these calculations, proportional to the length |ek| and degree lk of each chain. In this regard, in a large number of articles on this topic, various variants of “constant time CSIDH” are considered, in which the secret exponents ek are increased to the upper bound m by fictitious chains of isogenies. It is clear that such protection is achieved by significant redundancy and algorithm slowdown.

In [ 11 ], we proposed an alternative approach to solving the problem—randomization of the path of isogenic chains. Along with counteracting side channel attacks, this

method possible to practically avoid the makes it collisions described in the final part of Section 4. The idea is that any random coordinate x of an elliptic curve always generates a random point P = (x,y) of one of the two curves Ed or E–1,–d a pair of quadratic twist. Then one can avoid fruitless attempts to find a point of a curve of a given class and immediately determine the class of the curve and the ycoordinate of a point P = (x,y) of this class.

Further, in this class, the first isogenic curve E(1) = [lk]*E(0) of the degree l

k of isogeny corresponding to the sign of the exponent ek is calculated. The choice lk is randomized, and the value |ek| is reduced by 1. At the next step, with a new parameter d(1) value, a random point P = (x,y) of one of the curves Ed or E–1,–d is determined again, the isogeny kernel of a randomly chosen degree lk is determined, and the parameter d(2) is calculated. The process continues until zeroing all ek.

Some estimates calculates the secret exponents ek of isogenic chains of degree lk are given in [ 11 ]. Below we provide Randomized algorithm 2: Evaluating the class-group action on quadratic and twisted SEC. Input: dA ∈ EA, χ(d) = 1 and a list of integers ΩA = (e1, e2, …, eK).

Output: dB such that [

3. Sample a random x ∈ Fp, 1. Let S0 = {k | ek > 0}, S1 = {k | ek < 0}, 0 = ∏ 0 , 1 = ∏ 1 , 4. Sеt a ← 1, λ ← 0, EA: x2 + y2 = 1 + dAx2y2 if χ((x2 – 1)/(dx2 – 1)) = 1, 5. Else a ← –1, λ ← 1, EA: x2 – y2 = 1 – dAx2y2, 6. Compute y-coordinate of the point P = (x,y) ∈ EA 7. Compute R ← [(p + 1)/2nλ]P, 8. Sample a random lk | k ∈ Sλ,

9. Compute Q ← [nλ/lk]R

10. If Q ≠ (1,0) compute kernel G of lk-isogeny ϕ: EA → EB, 11. Else start over to line 3, 12. Compute dB of curve EB, dA ← dB, ek ← ek – a, 13. Skip k in Sλ and set nλ ← nλ/lk if ek = 0, 14. Return dA.

This algorithm has two important differences from Algorithm 1. Firstly, we do not divide the calculation of isogenies into two stages with curves of one class, then another (a ← –a), but build a random sequence {λ} with

an equiprobable choice of curves Ed or E–1,–d, at each step. Together with the twofold acceleration of the procedure for selecting curves, this deprives the analyst of the possibility of orderly construction of two subsets S0,S1 of isogeny degrees. In addition, for each component [ Θ, the chain of isogenies of length |ek| is divided into fragments of the general chain, which are ] of the function inserted complicates at random times.

This

inevitably the task of

measuring computation time according to the function [ A rough lower bound for the number of paths of isogenic chains for the data of [ 1 ] is 21300.

the ].

Secondly, as in [ 11 ], in Algorithm 2 (section 12) we refuse to calculate the isogenic function ϕ(R), which significantly speeds up the algorithm.

The ultimate goal of the CSIDH secret sharing algorithm is to find the common parameter dAB of curve EAB. For each step in the chain of isogenies E → Eʹ, it is only necessary to calculate the parameter dʹ = ψ(d,Q) based on the parameter d and the kernel <Q> of the domain E. This calculation involves two scalar multiplications SM of odd-order nλ random points R and (lk – 1)/2 recurrent doublings of points from <Q>. Thus, the construction and calculation of a sufficiently complex function ϕ(R) is not necessary for the implementation

At the beginning of Algorithm 2, two subsets isogenic curves (i = 1..6), and in the lower half for Sλ,λ = 0,1 are formed with degree numbers lk, the rest (i = 7..12). together with two factors n0 and n1 of number The first line of the table specifies the number n = n0n1. Since the order of the curve is p + 1 =8n, i of the isogenic curve, then given the coordinates then in step 7 of the algorithm, a point R = 4n1P of a random point P, a point R of odd order, its of odd order n0 is calculated for the curve Ed, and order, the degree l of isogeny, the coordinates of a point R = 4n0P of odd order n1 is calculated for the point Ql of the kernel, the parameters α1, α2, the curve E–1,–d. As in Algorithm 1, this minimizes …, αs of the kernel points and, finally, the the cost of the next scalar multiplication that parameter d(i) calculated by the formula (6). determines the degree lk isogeny kernel point Q We note right away that in this example we (Item 9). Further, in step 10 of the algorithm, the practically do not change the x-coordinates of the (lk – 1)/2 coordinates of the points of the kernel point P, and the choice of the curve Ed or E–1,–d at <Q> are calculated by doubling the points. each step is due to a change in the flow parameter

Example 2. To illustrate the randomization d(i). For i = 8 and x =100, the order of the point R method based on the data of Example 1, let’s give turned out to be 11, and this degree of isogeny has an example of Alice calculating the secret key κ, been exhausted by previous calculations. We took as well as its encapsulation with Bob’s public key x = 101 and continued the calculations until the and Bob’s decapsulation of the encrypted key in final step i = 12. Here, the curve E–1,–d with 5the randomized CSIKE algorithm (Algorithm 2). isogeny is found at x = 104. The number of

In order for the reader to be able to check the degrees of freedom at the end of the calculations calculations of the first stage, we have naturally decreases. Random points R with small summarized their key results in Table 1. In its probabilities Lk/n may not have the maximum upper half we write the results for the first six order n, which sometimes leads to a return to the beginning of the cycle. (100,8575) (100,1188) (100,6058) (100,36) (100,8756) (100,6475) (2355,3000) (7437,8394) (1314,6857) (1999,6221) (5518,5326) (6757,8503) 3*7*11 5*7*11 5*11 3*5*7*11 3*5*7*11 3*5*7*11 7 11 11 3 5 3 (3765,1727) (79,5609) (3770,1401) (6068,2793) (8212,2432) (–500,8513) 3765 79 3770 –3171 8212 –500 4218 2380 –1364 — 2592 — 4670 387 8468 — — — — –7876 –7225 — — — — –33 –8620 — — — 5135 8326 35 2590 8588 3466 (100,8968) (101,8248) (1283,6372) (6731,5854) 3*5*7*11 3*5*7*11

3 7 (1442,6713) (407,556) 1442 407 — –2358 — –398 7327 8326

This secret key κ = 443 is the same as the result of the previous section and Table 1. Randomizing the choice of curves essentially randomly splits the key exponents Ωκ and introduces significant uncertainty into the side channel attack problem.

Consider next the stages of encapsulation and decapsulation. Let Bob’s secret key be ΩB = (3,–2,2,–3), and the class group action, respectively, be ΘB = [33,5–2,72,11–3]. Then he calculates his public key of one of the possible isogeny chains of length 10

According to the results of calculations in Table 1, Alice determines the secret key κ = 443.

With a random choice of the x-coordinate of the point P, another chain of isogenies was defined with parameters d(i)

This key dκB = 5154 is sent to Bob. To decapsulate dκB, Bob uses his reverse secret key ̅Θ̅̅̅ = [ 3–3,52,7–2,113 ]. He calculates ̅Θ̅̅̅*EκB and obtain

As a result, both parties have a common secret key κ = 443 to work in a symmetric cryptosystem.

The security level of the algorithm is evaluated similarly to CSIDH [ 1 ], but under the conditions of an attack with a known one public key instead of two.

Let us now turn to some properties of the curves Ed and E–1,–d, which are useful in choosing a random point of one of them. For curves of order, NE = 8n there are 8 times more points of maximum order 4n than points of odd order n. For the latter, in turn, the choice of a point of order that divides n is unlikely.

Equations (3) and (4) will be rewritten as

Excluding points of small even orders, and singular points ((xy ≠ 0), (dx2 ≠ 1), (dy2 ≠ –1)), the choice of a random element x ∈ Fd generates a random point P(x,y) ∈ Fd or P(x,y) ∈ E–1,–d. In the first case χ((dx2 – 1)(x2 – 1)) = 1, in the second case, χ((dx2 – 1)(x2 – 1)) = –1 is performed.

According to the above formulas, the y-coordinate of the point P = (x,y) is calculated.

The results of the implementation of the Edwards-CSIDH model [ 12 ] in projective coordinates (W:Z) state that it is faster than the Montgomery-CSIDH model in coordinates (X:Z) by 20%. Note that this model in [ 12 ] is built on complete Edwards curves with order NE = p + 1(n is odd). Based on theorems [ 8 ] and the randomization method [ 11 ], in this paper we have shown how to implement a simple CSIKE model on non-cyclic quadratic and twisted SKEs that form quadratic twist pairs. The advantage of these classes of Edwards curves over the complete ones

Bob thus has a public key dB = 2504. Knowing it, Alice encrypts it at the encapsulation step using the secret function of the group action class. Θκ = [34,5–3,7–3,112]. To do this, she calculates an isogenic curve Θκ*EB = EκB. Her calculations yield an encrypted encapsulation key (3) (7) (5) −1 6250−1 1787 1 667 −1 → → → → 9033 = (6), (7) (11) (3) (6) = 9033 1 833 1 894 −1

→ → → (11) (3) (5) −1 6661 1 6163−1 5881 1 → → → → 5154 = (12).

(3) (5)

(3) at fixed p is the doubling of the number of curves in the algorithm with a corresponding increase in security. In addition, the time-consuming inversion of the parameter d → d–1 is not required when going to the quadratic twist complete curve.

6. Conclusions

The paper presents the original PQC CSIKE algorithm, which implements a scheme for encrypting a shared secret with a single public key of the recipient. The algorithm, in contrast to the well-known KEM scheme [ 2, 3 ], does not use the ElGamal encryption scheme, but is built as a modification of CSIDH using the recipient’s reverse secret key. Such an implementation is undoubtedly much faster than the KEM scheme. An illustration of CSIKE operation on a model with isogenies of degrees 3, 5, 7, and 11 at and order NE = 9240 of SEC is given. In the absence of precalculation of the SEC parameters d (they were used in previous works [ 9–11 ]), all isogenic curves were calculated from the starting curve Ed with the parameter [19].

7. References

Cybernetics and Systems Analysist, vol. 55, no. 3, 2019, pp. 347–353. [19] A. Bessalov, L. Kovalchuk, Supersingular Twisted Edwards Curves over Prime Fields, II. Supersingular Twisted Edwards Curves with the j-Invariant Equal to 663, Cybernetics and Systems Analysist, vol. 55, no. 5, 2019, pp. 731–741. [20] L. C. Washington, Elliptic Curves. Number Theory and Cryptography, 2nd ed., CRC Press, 2008.

References

1. Key generation. Alice, using a random

[1] W. Castryck , et al., CSIDH: An efficient Post-Quantum Commutative Group Action. in Advances in Cryptology, ASIACRYPT , 2018 .

[2] H. Onuki , et al., A Faster Constant-time Algorithm of CSIDH keeping Two Points . ASIACRYPT, 2020 .

[3] A. Jalali , et al., Towards Optimized and Constant-Time CSIDH on Embedded Devices, IACR Cryptology ePrint Archive 2019 /297.

[4] M. Qi , An Efficient Post-Quantum KEM from CSIDH , Journal of Mathematical Cryptology , 16 , 2022 , pp. 103 - 113 . doi: 10 .1515/jmc-2022-0007.

[5] K. Yoneyama , Post-Quantum Variants of ISO/IEC Standards: Compact Chosen Ciphertext Secure Key Encapsulation Mechanism From Isogeny , in 5th ACM Workshop on Security Standardisation Research Workshop , 2019 , p. 13 - 21 .

[6] A. Bessalov , V. Sokolov , P. Skladannyi , Modeling of 3- and 5-Isogenies of Supersingular Edwards Curves , in 2nd International Workshop on Modern Machine Learning Technologies and Data Science, no. I , vol. 2631 , 2020 , pp. 30 - 39 .

[7] A. Bessalov , et al., Analysis of 2-Isogeny Properties of Generalized Form Edwards Curves, in Workshop on Cyberse-curity Providing in Information and Telecommunication Systems , vol. 2746 , 2020 , pp. 1 - 13 .

[8] A. Bessalov , et al., Computing of Odd Degree Isogenies on Supersingular Twisted Edwards Curves, CEUR Workshop Proceedings , vol. 2923 , 2021 , pp. 1 - 11 .

[9] A. Bessalov , et al., Implementation of the CSIDH Algorithm Model on Supersingular Twisted and Quadratic Edwards Curves . CEUR Workshop Proceeding , vol. 3187 , 2021 , pp. 302 - 309 .

[10] A. Bessalov V . How to Construct CSIDH on Quadratic and Twisted Edwards Curves . Cybersecurity: Education, Science, Technique, vol. 3 , no. 15 , 2022 , pp. 148 - 163 .

[11] A. Bessalov , L. Kovalchuk , S. Abramov , Randomization of CSIDH Algorithm on Quadratic and Twisted Edwards Curves , Cybersecurity: Education, Science, Technique, vol. 1 , no. 17 , 2022 , pp. 128 - 144 .

[12] S. Kim , et al., Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves. Security and Communication Networks , 2019 .

[13] D. Moody , D. Shumow, Analogues of Velus formulas for isogenies on alternate models of elliptic curves . Mathematics of Computation , vol. 85 , no. 300 , 2016 , pp. 1929 - 1951 .

[14] D. J. Bernstein , T. Lange , Faster Addition and Doubling on Elliptic Curves , in Advances in Cryptology-ASIACRYPT, Lect. Notes Comp. Sci. , vol. 4833 , 2007 , pp. 29 - 50 .

[15] D. J. Bernstein , et al., Twisted Edwards curves , in: AFRICACRYPT , vol. 5023 , 2008 , pp. 389 - 405 .

[16] A. V. Bessalov , Elliptic Curves in Edwards form and Cryptography, Monograph, Kyiv, 2017 .

[17] A. Bessalov , O. Tsygankova , Number of Curves in the Generalized Edwards form with Minimal even Cofactor of the Curve Order, Problems of Information Transmission , vol. 53 , iss . 1, 2017 , pp. 92 - 101 . doi: 10 .1134/S003294601701008213.

[18] A. Bessalov , L. Kovalchuk, Supersingular Twisted Edwards Curves Over Prime Fields, I. Supersingular Twisted Edwards Curves with j-Invariants Equal to Zero and 123,