Algorithms and complexity evaluation of 3- and 5-isogeny calculation of super singular Edwards curves

Authors

  • А.В. Бессалов

DOI:

https://doi.org/10.30837/rt.2020.1.200.04

Keywords:

кривая в обобщенной форме Эдвардса, полная кривая Эдвардса, скрученная кривая Эдвардса, квадратичная кривая Эдвардса, порядок кривой, порядок точки, изоморфизм, изогения, степень изогении, ядро изогении, квадратичный вычет, квадратичный невычет

Abstract

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.

References

Jao D., L. de Feo, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies // Post-Quantum Cryptography. 2011. Р. 19-34.

Bernstein D.J., Lange T. Faster Addition and Doubling on Elliptic Curves // Advances in Cryptology – ASIACRYPT’2007 (Proc. 13th Int. Conf. on the Theory and Application of Cryptology and Information Security. Kuching, Malaysia. December 2–6, 2007). Lect. Notes Comp. Sci. V. 4833. Berlin : Springer, 2007. P. 29–50.

Bernstein Daniel J., Birkner Peter , Joye Marc , Lange Tanja, Peters Christiane. Twisted Edwards Curves // IST Programme under Contract IST–2002–507932 ECRYPT,and in part by the National Science Foundation under grant ITR–0716498, 2008. Р. 1-17.

Moody D., Shumow D. Analogues of Velus formulas for isogenies on alternate models of elliptic curves. Mathematics of Computation. 2016. Vol. 85. No. 300. Р. 1929–1951.

Ahmadi O., Granger R. On isogeny classes of Edwards curves over finite fields // J. Number Theory. 2012. 132 (6). Р. 1337-1358.

Suhri Kim, Kisoon Yoon, Jihoon Kwon, Seokhie Hong , and Young-Ho Park Efficient Isogeny Computations on Twisted Edwards Curves Hindawi Security and Communication NetworksVolume 2018, Article ID 5747642, 11 pages https://doi.org/10.1155/2018/5747642.

Бессалов А.В., Ковальчук Л.В. Суперсингулярные скрученные кривые Эдвардса над простым полем. І. Суперсингулярные скрученные кривые Эдвардса с j-инвариантами, равными нулю и // Кибернетика и системный анализ. 2019. Т. 55. №3. С.3 – 10.

Бессалов А.В., Ковальчук Л.В. Суперсингулярные скрученные кривые Эдвардса над простым полем. ІІ. Суперсингулярные скрученные кривые Эдвардса с j-инвариантом, равным // Кибернетика и системный анализ. 2019. Т. 55. №5. С. 35–46.

Бессалов А.В. Эллиптические кривые в форме Эдвардса и криптография. Киев : Политехника, 2017. 272с.

Бессалов А.В., Цыганкова О.В. Число кривых в обобщенной форме Эдвардса с минимальным четным кофактором порядка кривой // Проблемы передачи информации. 2017. Т. 53 (1). C.101-111. doi:10.1134/S0032946017010082.

Washington L.C. Elliptic Curvres. Number Theory and Cryptography. Second Edition. CRC Press, 2008.

Downloads

How to Cite

Бессалов, А. (2020). Algorithms and complexity evaluation of 3- and 5-isogeny calculation of super singular Edwards curves. Radiotekhnika, 1(200), 37–50. https://doi.org/10.30837/rt.2020.1.200.04

Issue

No. 200 (2020): Radiotekhnika

Section

Articles

License

Authors who publish with this journal agree to the following terms:

1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).