Algorithms and complexity evaluation of 3- and 5-isogeny calculation of super singular Edwards curves - Бессалов, А.В. (Radiotekhnika, 2020)
The properties and existence conditions of 3- and 5-isogenies for complete and quadratic super singular Edwards curves over the fields of p>3 odd characteristic are analyzed. It is proposed to use the minimum odd degrees 3- and 5-isogenies for the task of keys encapsulation based on the SIDH algorithm of post quantum cryptography, which allows bypassing the problem of special points of the 2nd and 4th orders. These points always arise on 2-isogenies for the classes of noncyclic Edwards curves. A review of the main properties of the Edwards curve classes is given. An analysis of the properties of isogenies of odd degrees of Edwards curves with one parameter d in affine coordinates and examples of their calculation are given The known formulas of 3- and 5-isogeny in affine coordinates are transformed into projective coordinates. To increase the rate of isogeny calculation, only the x-coordinate of the affine point of the curve is used. Formulas for the coordinates and complexity evaluation for 3-isogeny calculations in the classes of complete and quadratic Edwards curves in projective coordinates are obtained. The parameter d of the curve was expressed in terms of the x-coordinates of the points of the nucleus for the 5th order nucleus, which allowed us to obtain formulas independent of d for the coordinates of 5-isogenies. A comparative analysis of the complexity of 4 algorithms for calculating the coordinates of 5 isogenies is carried out. Algorithms for computing 3- and 5-isogenies in the classes of complete and quadratic super singular Edwards curves are constructed. Some requirements for the parameters of the cryptosystem are considered.