Exploring 3- and 5-Isogenies in Supersingular Edwards Curves 🔍

Anatoly Bessalov, Volodymyr Sokolov, Pavlo Skladannyi

Borys Grinchenko Kyiv University, Kyiv, Ukraine

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 en-capsulation 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 pre-serves the horizontal symmetry of the curve’s return points. Examples of the cal-culation 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 ex-istence 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 de-termined during the implementation of the SIDH algorithm at the quantum securi-ty level of 128 bits.