An analysis is made of the properties and conditions for the existence of 3- and 5-isogenies of complete and quadratic supersingular Edwards curves. For the encapsulation of keys based on the SIDH algorithm, it is proposed to use isogeny of minimal odd 3 and 5 degrees, which allows bypassing the problem of singular points of the 2nd and 4th orders, characteristic of 2-isogenies. A review of the main properties of the classes of complete, quadratic and twisted Edwards curves over a simple field is given. Formulas for the isogeny of odd degrees are reduced to a form adapted to curves in Weierstrass form. To do this, the modified law of addition of curve points in the generalized Edwards form is used, which preserves the horizontal symmetry of the curve's return points. Examples of the calculation of 3- and 5-isogenies of complete Edwards supersingular curves over small simple fields are given, and the properties of the isogeny composition for computing isogenies with large-order kernels are discussed. Formulas of upper bounds for the complexity of computing isogeny of odd degrees 3 and 5 in the classes of complete and quadratic Edwards curves in projective coordinates are obtained. Algorithms for calculating 3- and 5-isogenies of Edwards curves with complexity and 12M+5S, respectively, are constructed. The conditions for the existence of supersingular complete and quadratic Edwards curves of the order 4·3m·5n and 8·3m·5n are found. Some parameters of the cryptosystem were determined during the implementation of the SIDH algorithm at the quantum security level of 128 bits.
One of the well-known prospects of post-quantum cryptography (PQC) is the algorithms based on the isogeny of supersingular elliptic curves with as many subgroups of their points as possible (in particular, the SIDH algorithm [1]). The problem of the discrete logarithm of classical elliptic cryptography is replaced by the problem of finding one of the isogenous sets of subgroups of such a non-cyclic curve that is sufficiently resistant to the attacks of a quantum computer. To date, the growing interest in isogeny is associated with the shortest key length in the proposed algorithms in comparison with other well-known candidates for post-quantum cryptography at a given level of strength.
This paper deals with the properties of 3- and 5-isogenies of two classes of these curves, in particular the conditions of their existence. Section 2 provides a brief review of the literature on this topic. In Sect. 3, we touch upon the issue of how to solve the problem of singular points that occurs when programming the SIDH algorithm on Edwards curves using 2-isogenies. Instead of 2- and 3-isogenies, it is proposed to construct an algorithm on 3- and 5-isogenies of points of odd orders, which allows circumventing singular points. Sect. 4 gives a brief overview of the properties of three classes of Edwards curves according to the new classification. In Sect. 5, we prove a formula for the isogeny of odd degrees expressed by rational functions of one variable and give examples. In Sect. 6, the conditions for the existence of 3- and 5-isogenies and the requirements for the curve parameters for the SIDH algorithm are defined [1]. Algorithms for 3- and 5-isogenous Edwards curves are presented in Sect. 7 and the results of mathematical modeling are presented in Sect. 8. 2
The properties of isogeny for curves in the form of Weierstrass are sufficiently studied. Effective construction methods and isogeny properties of promising classes of curves in the Edwards form are less known.
Edwards curves with one parameter, defined in [2], have very attractive advantages for cryptography: maximum point exponentiation speed, completeness, and universality of the point addition law, affine coordinates of a neutral element of a group of points, increased security against side-channel attacks. The programming of group operations becomes more efficient and accelerates due to the absence of a singular point at infinity as the zero of an abelian group of points. The introduction of the second parameter of the curve in [3] expanded the class of curves in the Edwards form and generated curves with new properties that are interesting for cryptographic applications.
Along with the properties noted above, curves in the Edwards form proved to be the fastest technology in calculating isogeny. In [4], experimental estimates of the rate of calculation of isogeny on Edwards curves are presented, more than three times higher than the indices for curves in the Weierstrass form. Since the procedure for finding an isogenic point usually includes the scalar product of the point, the complex gain in the speed of the algorithms on the Edwards curves becomes significant. 3
Well-known implementations of the SIDH algorithm mainly use curves in the forms of Weierstrass and Montgomery. Our attempt to programmatically implement the SIDH algorithm using 2- and 3-isogenies of curves in the Edwards form encountered the problem of the presence of 4 singular points at infinity of the 2nd and 4th orders in the class of quadratic Edwards curves, to which all Edwards curves are mapped over the field 2 set over the field . These points exist in all subgroups of even orders, the number of which exceeds half of all subgroups of the curve. The appearance of any singular point in the calculation of isogeny significantly slows down the software implementation of the SIDH algorithm on Edwards curves. To get around this problem, we propose using isogenies of minimal odd degrees 3 and 5 for points of odd order of the curve. Although the transition from 2- to 5-isogeny complicates the calculation algorithm, such a smooth implementation of the algorithm is faster.
Among the numerous works on this problem, we single out articles [4, 5], in which isogeny formulas for curves in the Edwards form were first obtained. Our analysis in this paper is based on their results using the properties of supersingular curves [6]. To adapt the definitions for the arithmetic of isogeny of Edwards curves and curves in the Weierstrass form, we use the modified law of addition of points [7]. 4
Classes of Curves in the Generalized Edwards Form The elliptic curve in the generalized Edwards form [3, 8] is determined by the equation , : 2 + 2 = 1 + 2 2, , ∈ ∗, ≠ 1, ≠ , ≠ 2.
In contrast to the equation of this curve in [3], here we multiply the parameter a by 2
instead of 2. If it is quadratic ( ) = −1, the curve (
This parameter is basic in the structure of graphs of isogenic curves, the vertices of which define classes of isomorphic curves.
In our article [7], we proposed interchanging the coordinates x and y in the form of
the Edwards curve. Then the modified universal law of addition of points of the curve
(
( , ) =
16( 2+( −2+1)44 ).
In case ( ) = 1 and ( ) = ( ) = 1, then there is an isomorphism of the curve
(
: 2 + 2 = 1 + 2 2, ( ) = 1, ≠ 0,1,
having, in contrast to (
Curves with different values d are isomorphic if they have the same j-invariant equal
to the curve (
Using the modified laws (
= ( 1, − 1) we obtain, according to (
= ( 1, 1) + ( 1, − 1) = (
In addition to the neutral element O, the axis X also always contains the second-order
point 0 = (−1,0), for which, in accordance with (
Depending on the properties of the parameters a and d, you can get two more singular points of the 2nd order and two or more points of the 4th order.
As follows from (
From equation (
√
They arise in cases ( ) = 1 and ( ) = 1 respectively. This, for example, is always
performed in the extension of the field 2. According to the rules of terminal transition
and the doubling law (
Depending on the properties of the parameters a and d, the curves in the generalized
Edwards form (
der singular points ± 11 = (∞; ± √1 ).
3. Twisted Edwards curves contain only two second-order singular points 1,2 = ; ∞), and Edwards quadratic curves, in addition to them,—two other fourth-or4. Edwards twisted and quadratic curves form quadratic torsion pairs based on a parameter transformation ̃ = , ̃ = , ( ) = −1.
5. In the classes of twisted and quadratic Edwards curves, the replacement ↔ gives the isomorphism , ~ , .
6. Complete and quadratic Edwards curves are isomorphic to the curves with
parameter = 1: , ~ 1, / .The introduction of the new parameter into the equation of
curve (
7. The twisted Edwards curves for ≡ 1mod4 do not have the 4th order points.
We emphasize that in the extension of the simple field 2 all 3 classes of Edwards
curves defined over a simple field acquire the properties of quadratic curves (
Isogenies of Odd Degrees of Edwards Curves The isogeny of the elliptic curve ( ) over the field into the curve ′( ) is the homomorphism : ( ̅) → ′( ̅), defined by rational functions. That means that for all ( + ) = ( ) + ( ) there exists the rational function [9] ( , ) = ( ( ) , ( ) ( ) ( )) = ( ′, ′),
(
⊆ , the points of which are reflected by the function ( , ) into the neutral element О of the group ′. The degree of separable isogeny is equal to the order of its kernel. Isogeny compresses the curve points times (curve points are displayed in one point of the curve ′). At = isogeny becomes the isomorphism with the degree 1.
The basis of the construction of isogeny of odd simple degrees for Edwards curves
is based on Theorem 2 [4]. Let’s formulate it taking into account the modification (
Theorem 2 [4]. Let’s
= {(
)2 , 2 ∏ =1 1−( ( )2−( )22), ) Its proof is given in [4]. An important consequence of this is that isogenic curves lie in the same classes as curves (i. e., complete Edwards curves are mapped to complete and quadratic curves—to quadratic). This significantly distinguishes the isogeny of odd degrees from the 2-isogeny (for them, the complete Edwards curves are mapped into quadratic ones).
The formula (11) for the function ( , ) directly follows the definition ( ) in the
statement of the theorem, the law (
− + − = 1 ( )2−( )2 , +
− = 1 ( )2−( )2. 2 1−( )2 − 2 1−( )2 The multipliers x and y before the products in the coordinates of the function ( , ) take into account the neutral element
= (1 , 0) of the kernel of isogeny.
From (11) the property (
The mapping (11) can be reduced to the form (
= 2) 2− 2− 2 4 2− 2− ( 2 4− 2
2 2) 1− 2 = ( 2− 2)(1− 2 2).
1− 2 Similarly, we transform the denominator of the first coordinate (11) 1 − ( )2 = 1 − 2 2 2 2 1− 2 1− 2 = 1− 2− 2 2 2 2+ 2 2
2 4 1− 2 = = 1− ( 2+ 2) 2+ 2 2
2 4 1− 2 = (1− 2 2)(1− 2 2).
1− 2 After reducing the common factors, we obtain 1−( )2 = 2− 2 . ( )2−( )2 1− 2 2 Similar calculations can be carried out with the second coordinate (11). As a result, the function (11) can be written in the equivalent form
( , ) = ( 2 ∏ =1 1− 2 2− 2 , − 2
2 ∏
=1 1− 2
2− 22),
corresponding to the classical form (
Requirements for Cryptosystem Parameters The search for a suitable value of the characteristic of the field p in the SIDH problem using 3- and 5-isogeny of Edwards curves must meet some necessary conditions.
Statement 1. 3- and 5-isogenies exist for supersingular complete and quadratic Edwards curves , respectively, at ≡ −1mod60 and ≡ −1mod120.
Proof. Points of the 3rd and 5th orders exist on the complete supersingular Edwards curve of the + 1 = 4 ∙ 3 ∙ 5 order under the conditions that ≡ −1mod4, ≡ −1mod3, and ≡ −1mod5, and which come down to one condition ≡ −1mod60.
The minimum even cofactor of the order of the quadratic Edwards curve is the number 8, at the same time at + 1 = 8 ∙ 3 ∙ 5 the condition ≡ −1mod120 is true.
Statement 2. For odd = 2 + 1 of l-isogeny of P points of odd order of the curve, there are points of odd order.
Proof. The Edwards curve of the order = 2 ∙ , ≥ 2, contains the points P of the odd order = ∙ . Thus, l-isogeny and isogenous curve ′ of the same order exist. l-isogeny is a homomorphism that compresses times the points < > into a subgroup of points of odd order of the curve ′. This subgroup does not contain any points of even order. At = 1 n-isogeny maps all points < > into neutral element O of the order 1.
Statement 3. At ≡ 1mod4 supersingular Edwards curves do not exist.
Proof. At ≡ 1mod4 the order of supersingular curve is + 1 ≡ 2mod4, at the same time for any Edwards curve the number 4 divides the order of the curve.
The value of module p is determined by the security requirements. In the product 3 ∙ 5 both factors have the same order at 3 ≈ 5 , then ≈ 1.465 . This balances the number of corresponding cyclic subgroups.
128-bit quantum security with complexity estimate 6√ (instead of 4√ for a regular computer) is provided with the length of module log2 = 6 ∙ 128 = 768 bit. In the field 2 each coordinate of the point has the length 2 log2 = 1536 bit. The key length estimate in the SIDH system is 6 log2 = 4608 bit. 256-bit quantum security level doubles all of these estimates. 7
Algorithms for 3- and 5-Isogenous Edwards Curves
The calculation of the 3- and 5-isogenes of the Edwards curves (
These algorithms are distinguished by the greatest simplicity and low cost of computing among the known ones. In contrast to the 3-isogeny calculation algorithm given in [9] and instead of (11) we use the simpler expression (16) for the function ( , ) together with the simpler equation for the parameter ′ = 8 ∙ .
In fact, when calculating 3-isogeny, we use an algorithm close to that proposed in [9], with the same effectiveness 6M + 5S. Our algorithm for computing 5-isogeny is almost three times slower than for 3-isogeny, and probably has reserves to increase efficiency. ′ ′ ′.
Implementation of the SIDH Algorithm Below are three field module values of the field p found by brute force with a length of about 768 bits for the implementation of the SIDH algorithm on the 3- and 5-isogeny of complete Edwards curves (see Table 1). Thus, the use of 3- and 5-isogeny of Edwards curves for points of odd order with a fixed resistance to attacks by a quantum computer will allow bypassing the problems of singular points inherent to 2-isogenies of these curves. Estimates of the complexity of computing the 3- and 5-isogeny of Edwards curves, comparable to w the complexity of group operations, allow us to implement the fastest post-quantum cryptography algorithms. Experimental estimates of the computational efficiency of these isogenies in the implementation of the SIDH algorithm are planned to be considered in the next paper.