Complexity of Calculation of 3- and 5-Isogenes of Supersingular Curves of Edwards

DOI: 10.31673/2409-7292.2019.046369

Abstract

An analysis of the properties of 3- and 5-isogenies of complete and quadratic supersingular Edwards curves is given. It is proposed to use isogeny of small odd degrees 3 and 5 for the SIDH key encapsulation algorithm. Formulas for calculating isogeny and upper bounds for the complexity of computing 3- and 5-isogenies in projective coordinates are obtained.

Keywords: curve in a generalized Edwards form, complete Edwards curve, twisted Edwards curve, quadratic Edwards curve, point order, isomorphism, isogeny, degree of isogeny, quadratic residue, quadratic non-residue.

References
1 .D.Jao, and L. de Feo, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, Post-Quantum Cryptography pp. 19-34 (2011).
2. Bernstein D.J., Lange T. Faster Addition and Doubling on Elliptic Curves // Advances in Cryptology—ASIACRYPT’2007 Lect. Notes Comp. Sci. V. 4833. Berlin: Springer, 2007. P. 29–50.
3. 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.
4. Moody D., Shumow D. Analogues of Velus formulas for isogenies on alternate models of elliptic curves. Mathematics of Computation, vol. 85, no. 300, pp. 1929–1951, 2016.
5. O. Ahmadi O., and Granger R On isogeny classes of Edwards curves over finite fields, J. Number Theory, 132 (6), pp. 1337-1358, (2012).
6. Бессалов А.В., Ковальчук Л.В. Суперсингулярные скрученные кривые Эдвардса над простым полем. Кибернетика и системный анализ, №5, 2019.– С.35-46.
7. Бессалов А.В. Эллиптические кривые в форме Эдвардса и криптография. Монография. «Политехника», Киев, 2017. - 272с. ISBN 978-966-622-808-9.
8. WashingtonL,C.. Elliptic Curvres. Number Theory and Cryptography. Second Edition. CRC Press, 2008.
9. Suhri Kim, Kisoon Yoon, Jihoon Kwon, Seokhie Hong , and Young-Ho Park Efficient Isogeny Computations on Twisted Edwards Curves Hindawi Security and Communication Networks Volume 2018, Article ID 5747642, 11 pages https://doi.org/10.1155/2018/5747642.