For the PQC CSIDH and CSIKE algorithms, the advantages of two classes of quadratic and twisted supersingular Edwards curves over complete Edwards curves are justified. These classes form pairs of quadratic twist curves with order p + 1 ≡ 0mod8 over the prime field Fp and double the space of all curves in the algorithms. The randomized algorithms CSIDH and CSIKE are presented. An analysis of the degrees lk isogenies distribution is given, and an optimal distribution within the given conditions is proposed with the degree lmax = 397 instead of lmax = 587 while maintaining the number K = 74 of all degrees. A probabilistic analysis of random odd order points R was carried out, probability estimates are obtained, and it is recommended to avoid isogenies with small values of the degrees lk in algorithms. The features of the CSIKE algorithm with one public key of Bob in the problem of encapsulation by Alice of the secret key κ, which Bob calculates at the stage of decapsulation with his secret key, are considered. A CSIKE-ENC scheme for combined encryption of the key κ and message M based on two asymmetric algorithms CSIDH and CSIKE with Alice's authentication and the wellknown symmetric message encryption standard is proposed. The security aspects of the scheme are discussed.
One of the most promising PQC algorithms, which has generated a wide stream of scientific articles, is the CSIDH algorithm [1]. It solves the problem of non-interactive Diffie-Hellman secret sharing based on the construction of chains of isogenic supersingular elliptic curves with the set { } of K small odd prime degrees isogenies over the prime field . The binary length log p of the modulus p of the field determines the length of the key in the algorithm and the (log p)/2 security levels for attacks on a classical computer and (log p)/4 on a quantum computer (the notation “log” refers to the base-2 logarithm). The CSIDH algorithm has the smallest key length among known PQC algorithms.
This paper continues and develops the results of the previous one [2] in the problem of CSIKE key encapsulation with authentication and combined encryption by asymmetric and symmetric algorithms.
The first implementations of CSIDH were
based on fast supersingular curves in the
Montgomery form [1], but soon in [3–5] using the
W: Z-coordinates of curves in the Edwards form,
it was possible to obtain a gain of 20% in
comparison with [1] in the computation speed.
Further, generalizing the formulas for calculating
isogenies for Edwards curves [
In most works related to the CSIDH algorithm,
various variants of “constant time CSIDH” are
proposed to counteract the
well-known side
channel attack [
As is known, one of the candidates for the
NIST standardization process of PQC algorithms
is SIKE [
CSIKE
algorithm [2] is much simpler and more efficient
than the CSIDH-KEM schemes [
ElGamal-like public key encryption algorithms. In this paper, we analyze and optimize the important parameters of the CSIDH and the maximum degree of isogenies is This drastically simplifies and speeds up the
Probabilistic analysis of random points of maximum odd order n is given, and recommendations are given on the rational distribution of degrees isogenies in a dense set
of size K. Section 4 proposes an original messages encryption with Alice’s authentication, security aspects are discussed, in addition to examples 1 and 2 [2], an example of calculations by Alice and Bob of simulated inserts according to the CSIDH algorithm is given.
The elliptic curve , generalized
For the first time, such a curve was proposed
in [
If the quadratic character χ(ad) = −1, curve (1)
is isomorphic to the complete Edwards curve [
The existence condition of SEC of this class is ≡ 3
Another case χ(ad) = 1 generates 2 classes of
non-cyclic curves: quadratic and twisted Edwards
curves. In particular, if χ(a) = χ(d) = 1, curve (1)
is isomorphic to the quadratic Edwards curve [
Here, in contrast to (2), the parameter d is a square. For both curves (2) and (3) usually take
The twisted Edwards curve is defined in [
In [
Theorem 2 [
Its proof is given in [
= , , ( ) = −1. Each of the 3 classes contains equal sets (p−3)/2 curves (d ≠ 0, ±1). Then the replacement of the class of complete
We define a quadratic and twisted Edwards curve as a pair of quadratic twists with parameters (
) = 1, ̅ = , ̅= , ( ) = −1. Since SEC exist only for ≡ 3
4 [
= 1, are the quadratic curve (3) parameters, respectively, ̅, ̅are twisted curve parameters. In other words, the transition from quadratic to twisted curve and vice versa can be defined as = 1,
↔ −1,− . Then the twisted SEC equation from (1) can be written as −1,− :
2 − 2 = 1 − 2 2, ∈ ∗, ≠ 1, ( ) = 1. (4)
The order of quadratic (3) and twisted (4) SEC = p+1 0mod8, then p −1 that equation (4), like equation (3), has a fixed parameter = −1, after which all curves (4) are determined by one parameter (− ). Quadratic residues = 1
of the curve (3) become quadratic non-residues = −1 (− ) of the curve (4). This simplifies the illustration of how 8 [2]. Note the CSIDH algorithm works.
Quadratic and twisted SEC as a pair of
quadratic twists have the same order + 1, but a
different structure. Except for the two points
(0, ±1), all their points are different, so isogenies
of the same degree have different kernels and are
calculated independently. Both curves are
noncyclic concerning points of even order (contain 3
points of the 2nd order each, two of which are
singular
points
1,2 = (±√
, ∞)
[
Quadratic SEC, in addition, contains 2 singular points of the 4th order ± 1 = (∞, ± 1 ). The presence of 3 points of the 2nd order limits the number 8 to the minimum even cofactor of the √ order
= 8 (n-odd) of twisted and quadratic
Edwards curves [
The choice of 2 classes of non-cyclic SEС for
the CSIDH algorithm in our works [
The number of all quadratic and twisted Edwards curves ( − 3) is twice the number of complete corresponding proportion is also valid for the number of isogenic SEC and, as a result, for the security of CSIDH.
The transition to the quadratic twist curve ↔ −1,−
does not require the laborious inversion of the parameter ↔ −1 required for a complete SEC.
Among isogenic curves (with
different
J-invariants) there are also isomorphic curves
with equal J-invariants [
3 ( − )4 This
parameter, in particular, recognizes
isomorphic
consider its randomized modification [
The PQC CSIDH algorithm was proposed by the authors of [1]. It is based on the CGA (classgroup action) function over a prime field . The CGA function defines an isogenic mapping of a supersingular elliptic curve E of order = + 1 into a curve ′ = ∗ of the same in [1] specifies the least isogeny degrees ,k = 1, = ( 1, 2, . . . ). ≤ ≤ ], = 5. = , where order of the form = [ 1 1, 2 2, . . , are odd prime degrees of isogenies and are exponents (number of isogenic transitions). This mapping is commutative.
The implementation of the CSIDH algorithm 2,..., K, K = 74, = 587, as well as an interval of 11 exponent
values [− Negative exponents mean the transition to a quadratic twist curve. Such parameters lead to a key length in CSIDH of 512 bits and a security level of 128 bits for quantum computer attacks.
of
supersingular
curves
in
the
Montgomery form [1] and complete Edwards
curves [3], in [
∏ =1 , while the 1. , 1, 2.
Choice of parameters. For odd primes compute =
∏ =1 , appropriate field modulus = 2 select the
∏ =1 − ≥ 3 and start the elliptic curve .
Public keys Calculation. Alice and Bob use secret keys in the form of vectors ,В = ( 1, 2, . . , ) construct isogenic maps ,В = [ 1 1, 2 2, . . , ] and calculate the isogenic curves ,В = ,В ∗ 0as their public keys. These curves are determined by their parameters up to isomorphism.
Key exchange. Here the protocol is similar to item 2 with the replacement of 0 → for Alice and 0 → Knowing Bob’s public key, Alice calculates for Bob. = ∗ = ∗ 0.
Similar actions Bob gives the result = ∗ = ∗ ∗ 0, which coincides with the first one due to the commutativity of the group operation.
The
J-invariant of the curve В ( ВА). is taken as a shared secret.
For each function Θ there is a multiplicatively inverse , such that ∗ = , where = [1, 1, 1, , . . . , 1] is the neutral element of CGA (K-dimensional vector of units). The our key encapsulation algorithm. mapping is constructed by inverting the signs of all exponents of the mapping . It is used in
Below we present a randomized modification
of Alice’s calculation algorithm according to
Section 2 of [
Randomized algorithm 1: Evaluating CGA function on quadratic and twisted SEC.
Input: ∈ , ( ) = 1 and a list of integers Output:
such that [ 1 1, 2 2, . . . ] ∗ , : 2 + 2 = 1 + А,В 2 2, 0 = ∏ ∈ 0 ,
1 = ∏ ∈ 1 , 2. While some ≠ 0 do 1. Let 0 = { | > 0} , 1 = { | < 0}, 3. Sample a random ∈ , 4. Sеt ← 1, ← 0, : 2 + 2 = 1 + 2 2 If (( 2 − 1)/( 2 − 1) = 1, 5. Else a −1, 1 : 2 − 2 = 1 − 2 2, 6. Compute = ( , ) ∈ , 7. Compute 9. Compute 10. If 8. Sample a random | ∈ , ← [( + 1)/2 ] , ← [ / ] ,
-coordinate of the point ≠ (1,0) computes kernel of - isogeny : → , 11. Else start over to line 3, 12. Compute of ←
− , 13. Skip If = 0, 14. Return А.
curve , ← , in and set ← ( / )
This algorithm has important differences from the original algorithm 2 [1], which are discussed in [2]. In addition to modifications related to the randomization method of the CSIDH algorithm, here we refuse the redundant isogenic function φ(R) of a random point R, which radically speeds up the algorithm.
At the beginning of Algorithm 1, two subsets together with two factors 0 , λ = 0,1, with degree numbers , are formed, 1 of the number = 0 1 (the index λ = 0 ( > 0) corresponds to the choice of a quadratic SEC, and λ = 1–to the choice twisted SEC ( < 0)). Since the order of the curve is p+1 = 8n, then in step 7 of the algorithm for the curve R = 4 1 of odd order 0, is calculated, and for the curve −1,− the point = 4 0 of odd order 1 is calculated. This minimizes the cost of the following scalar multiplication, which determines the point Q of the isogeny kernel of the degree (Step 9). Further, in step 10 of the algorithm, by the point doubling the points, = ( − 1)/2 of xcoordinates of the kernel <Q> points are calculated.
In step 7 of Algorithm 1, double doubling the
random point P immediately allows you to get rid
of points of even order (including singular points
of the 2nd and 4th order) and then the calculation of
scalar multiplications in subgroups of odd order
points are performed. Their task is to find ( −1) of
x-coordinates of the kernel <Q> points of prime
order . As a result, according to the formula [
model with classical and randomized implementation. In
Example 2 [2], we will illustrate Alice’s and Bob’s calculations to authenticate Alice. (6)
′ = 8, = ∏ =1 , s = (
− 1)/2 intensive redundant. the parameter ′ of the -isogenic quadratic SEC is calculated. Twisted SEC parameters (4) а′ = −1, ′→ − ′. We emphasize that the concept of CSIDH is the construction of chains of isogenic curves as
groups, and not isogenic functions φ(R) of a random point R. The laborcalculations of the latter [1] are
In our previous work [2], we proposed the original CSIKE algorithm as a modification of CSIDH. It is an algorithm for encapsulating the key κ as a shared secret between Alice and Bob (Commutative
1. 2.
Key κ generation
Alice generates random exponents integers and
finds = ( 1, 2, . . , ),, function [-m…m] of small the builds secret the ] vector CGA and whose parameter is taken as calculates the isogenic curve = ∗ 0,
Key encapsulation. This is the procedure for Alice to encrypt the key with Bob’s public key To do this, Alice calculates the isogenic this curve is sent to Bob. curve ∗ = . The parameter of 3.
Key decapsulation. Bob’s decryption of the curve
with his secret key (− ) reduces to his calculation of the isogenic curve inverse secret key: → (− ). inverse function is using Bob’s additively So Alice and Bob have a shared secret κ instead of a shared secret В in CSIDH. Usually, these parameters are replaced by the J-invariant (5), which is the same for isomorphic curves. Alice’s private and public keys do not yet
Below, we analyze and optimize the distributions of isogeny degrees { } and perform a statistical analysis of a good choice of a random point. with value We found that 74 degrees { } isogenies in [1] = 587 runs through only a fraction of all primes from 3 to 587, the total number of which is 106. In other words, 32 values of primes are not included in the list of degrees { } in the model [1], which means gaps in the set of all primes { }. Such gaps reduce the product of all , and form a reserve for its increase.
Let us pose the problem of analyzing possible distributions of sets of primes { } options for optimizing this distribution. According to the table of primes up to 587, the complete of size K to find = {3, 5, 7, …, 587}contains N = 106 set = { } of all primes.
Any segment of length K of the complete set of primes ordered in ascending order gives the product ∏ =1 = М( 1, ). Removing one of the extreme elements 1 or reduces the value of M and
− 1, but retains the segment density property (without gaps). Removing the element from the middle of the segment (1<k<K) also reduces the value of M and − 1, but violates the density property (with a gap). Let us call an ascending set of primes { } optimal if for known = 1 and K this set is dense. The optimal set the following property: product has
∏ =1 = М( 1, ) = .
Comment. In the product , we take the removed element 1. It is clear that such a replacement reduces the product by a factor with the same K. In this sense, we write down the above maximization property. When removing the extreme elements of the segment, the property is preserved for the shortened segment { 2,.., } −1 or { 1 ,…, −1} −1. our the set = { }106 = {3, 5, 7, … , 587}106is optimal by definition. Removing 32 numbers from it in the middle gives the set { } =74, which is far from optimal. The concept of optimality is associated maximizing the product of exclusively
with elements of a set.
Let = { } us divide the Lh = { } ℎ, ℎ = 1. .6, including prime numbers in hundreds of natural numbers with numbers h. For the first hundred numbers, for example, we have the optimal subset 1 = {3, 5, 7, . . , 97} 1, where 1 = 24. For all 6 optimal subsets Lh, these numbers ℎ are given in the second row of Distribution of quantities ℎ of primes and their products ℎ within hundreds of natural numbers with numbers h (rounded to whole bits) 1 24 95 2 21 45 3 16 23 4 16 92 119.7 bits (log to base 2). For all products of numbers { } in subsets, we calculate the bit length ℎ = ∑ ∈ ℎ ( ), 4 ∑ℎ=1 ℎ the values of which are given in the 3rd row of conclusions. Firstly, the sum of all bits of the 3rd row
6 ∑ℎ=0 ℎ = 792.772 = 793 determines the product of all 106 prime numbers {3,…,587}, has a redundancy of 283 bits compared to the minimum lower threshold of 510 bits (4n>2512, n>2510) [1] security requirements. Secondly, the prime numbers in the 5th and 6th hundred (L5 and L6) can be removed, since bits), which = 533.855 = 534 bits = 533.855 = 534 bits, which satisfies the requirement n > 2510 with a margin of 24 bits. Ignoring the last 2 columns of product n of all of the optimal set Lopt is estimated to be a binary number of length 528 bits. By adding 2 bits, we get the estimated log p = 530 bits. For the Lopt distribution, Table 1 can be corrected: in column h = 1 of the table, the values 1 = 21, 1 = 113.081 should be put, and the last 2 columns of the table should be deleted. Then 4 4 ∑ℎ=1 ℎ = 74, ∑ℎ=1 ℎ = 527.141 = 528 bits, = 530бит. Such an optimal distribution of the isogenies
degrees { } ensures that the minimal threshold log removing the 2 maximum isogeny degrees 397 and 389 for a total cost of 18 bits and taking = 383. However, this requires reducing the length K
− 2 of the secret key by 2.
The main advantage of the set of isogeny degrees Lopt proposed here over that used in [1] is a
significant = 587 to (1.5 times) reduction
of with such a radical decrease in the value of this only increases the security level of the algorithm and the value of . For example, let’s take
= 101, then the 24 degrees of the first hundred numbers must be replaced by 17 primes of the 5th hundred and the minimum 7 degrees of the 6th hundred ( the optimal set { }74 = {101, 107, . . , 557}.. The total sum log(
) of this set is 627.161, which, with 2 bits added, gives the estimated log p = 630 bits. Compared to the first distribution discussed above, the length log p of the key has increased by 100 bits. Here you can also exchange these 100 bits for a decrease in significantly reduce the value of K (by an estimate , but this will = 557). We get of 11).
Let’s move on to estimating the probability of a successful choice of a random point P at the start of each step of calculating the isogenic curve. In step → 7 = of
Algorithm 1, we replace ∏ =1 , then multiplication by 4 of a random point P gives a point R of maximum odd order ord(R) = n with probability =1
Pr(R) = ( )
= =1 ( − 1)/ = ∏(1 − −1) .
(7) set { } obvious that the smallest values of , the decrease in probability (7) is more significant than for large ones. Already from this, we can conclude that to increase the probability (7) it is advisable to avoid very small values of .
For a comparative estimate of probabilities (7), we consider two extreme options: 1. Filling in the of size K from below; 2. Filling the set Option 1 is hypothetical since it immediately violates the given constraints. In the
Lopt distribution, he requires replacing the removal of 3 lower degrees with the removal of higher ones:
= {3, 5, 7, … , 379}. However, these 3 high numbers add up to about 26 bits, which exceeds the maximum reserve of 24 bits concerning the minimum lower threshold the overall probability estimate (7) for the optimal set {3, 5, 7, … , 379}74 equal to Pr(R) = 0.194. Only for 24 degrees of isogenies of the first hundred numbers, this probability is equal 0.241. The greatest contribution to the reduction of this probability is made by the smallest degrees of 3 . The probability estimate of and 5: 2
∙ 4 = 8 3 5
15 satisfactory. 0.194
for option 1 cannot be considered Option 2 corresponds to the Lopt distribution proposed above exactly 74 primes lie densely in the set {11, 13, … , 397}74. The probability estimate (7) for this set { } the number n is missing in the order of a random point R is equal to −1. Hence it follows that the most probable failures are in the search for subgroups of the curve of very small orders. For example, for the second optimal distribution {101, 103, 107, … , 557}74 considered above, the probability of an unsuccessful selection of a random point with an order that does not contain the factor does not exceed 1%. Here one can expect with great confidence a smooth process of calculating isogenic curves.
We do not know the elements of the set { } in the model from [1]. Random selection is difficult to justify. It is only known that the set of these degrees is determined by the security level and the fulfillment of the = + 1 ≅ 2512. Although the first distribution of Lopt degrees is much better than [1], its further improvement may involve resources that have not yet been used in the size K of the set and the values of the exponents isogenies. Any algorithm has rich resources for modification.
An important conclusion of the probabilistic analysis of a successful choice of a random point is the recommendation to avoid using the lowest degrees of isogenies. They contribute the least to the security of the algorithm and the most to the problem of finding isogeny kernels.
The disadvantage of the CSIKE algorithm proposed in [2] is the lack of sender authentication. At the same time, the information available to Bob—Alice’s public key А—can be used by him to solve this problem using CSIDH. In addition, the extension and modification of the algorithm make it possible to perform the target function in one package—symmetric encryption of the message M of the sender. Such an extended algorithm can be called
combined asymmetricsymmetric algorithm. Classical ECC protocols, it is similar to ECIES (one of the standards is ISO/IEC 1803-2-2009).
Let us introduce the notation:
Со is the result of encrypting the secret key κ with Bob’s public key (Со < p);
M—message. =
symmetric encryption key κ. message M with the key κ.
( ) is the result of decrypting the
(М)—message M cipher with , —imitation inserts of Alice and
Alice and Bob, based on their public keys , and the non-interactive CSIDH algorithm, compute shared secrets
, intended as imitation insets for
Alice: (11)
(7) (5) 2. During encapsulation, encrypts the key κ with Bob’s public key and calculates the encrypted key = С о < . 3. Expands the
message M in the form ̃ = (
, ). 4. Using the standard known to the parties encrypts the message ̃ with the key κ of the symmetric cryptosystem: = ( ̃). 5. Sends to Bob a packet with two ciphers
DP = (Со, ).
Bob: 1. Using its additive inverse key (− ) decrypts the first cipher С о (Со < ) and calculates the key κ (key decapsulation). 2. Decrypts the second cipher with the key : ̃ =
( ) = ( 3. Checks for equality , ). without a digital signature performs two of its functions—authentication and message integrity check (including transmission errors).
In the previous work [2], 2 examples of the implementation of the CSIKE model with input parameters
p = 9239,
= (4, −3, −3,2), = (3, −2,2, −3), using 2 secret keys , , without Alice’s key . To authenticate
in the above-combined encryption protocol, it is proposed to use this 3rd key to calculate the tags of Alice and Bob according to the CSIDH secret-sharing algorithm. They serve as an imitation insert that Bob checks for validity. In continuation of example 2 [2], below
we illustrate an example of calculating randomized isogenic chains to determine the computes her public key = ∗ 0 with one of 220 possible isogeny chains of length 10 [2]:
It is clear that, due to the commutativity of CSIDH, = = 2384 = .
results are obtained by Alice and Bob at the precomputation stage of the CSIKE-ENC scheme. Essentially, this step means inserting the CSIDH into the CSIKE-ENC.
The question may arise: if with the help of CSIDH the task of secrets sharing is solved easier 4900 −1 3466 1 7327 −1 (11)
(7) → undoubted advantage of the latter is the increase in security. CSIDH includes 3 secret keys А, while CSIKE-ENC includes 5 secret keys , , . The main argument of our assertion is that the attack on on the known public keys in CSIDH relies and of Alice and Bob, while in
CSIKE-ENC the analyst for attacking the key κ has no information at all. Only Alice has the key generating κ. The above arguments complicate the task of cracking the key κ. Different versions of the replacement κ←H(κ) proposed above to increase the entropy of the key and the security level. The question raised requires detailed analysis and quantitative assessments. be received.
A good modification of CSIDH and CSIKEENC is to make the parameter 0 secret of the original Е0 .This requires swapping Alice’s and Bob’s public keys but adds another private key and makes the analyst’s task almost hopeless. When retransmitting an encrypted message based on CSIKE-ENC, for example, 0 ← can security.
It should be noted that the security level of СSIDH is estimated by the size of the set of all SECs close to √ [1]. Then for a module p with a length of 512 bits, as in [1], it is equal to 256 bits for a classical computer and 128 bits for a quantum one. We believe that hashing the key will achieve the maximum level of
The paper presents an original CSIKE-ENC scheme for combined encryption of key κ and message ̃
with sender authentication. The asymmetric algorithms CSIKE and CSIDH solve the problems of key encapsulation κ and Alice’s authentication using imitation inserts, while the symmetric algorithm encrypts the message along with the secret imitation insert. The proposed scheme differs from the known KEM schemes in simplicity and efficiency. The security level in relation to the quantum computer of this scheme is estimated as (log p)/4. The increase in security in the key κ encapsulation scheme in comparison with Diffie–Hellman secret sharing is substantiated. A further increase in circuit security can be ( ̃) with the key κ achieved by:
Classification of the starting curve 0.
the scheme is achieved: and (W: Z) coordinates.
Increased efficiency of the implementation of Using fast quadratic and twisted SEСs Rejection of redundant calculations of isogenic functions φ(R) of the point R.
Randomization of CSIKE and CSIDH
Optimization of scalar multiplication of point R in (W: Z) coordinates.
distribution Lopt isogeny degrees and a significant (1.5 times) decrease in the maximum degree to =397.
By avoiding small values of degrees in the set { } . the
model standardization.
and
In future work, we plan to continue the analysis of CSIKE modifications with the improvement of the prospect of further [1]
W. Castryck, et al., CSIDH: An Efficient
Systems, vol. 3288 (2022) 1–10. S. Kim, et al.,
R. R. Farashahi, S.G. Hosseini, Differential Addition on Twisted Edwards Curves, Inf.
Computations on Twisted Edwards Curves,
Velus Formulas for Isogenies on Alternate Models of Elliptic Curves, Mathematics of Computation, 85(300) (2016) 1929–1951. doi:10.1090/mcom/3036 A. Bessalov, et al., Computing of Odd Degree Isogenies on Supersingular Twisted