Estimation of the computational cost of the CSIDH algorithm on supersingular twisted and quadratic Edwards curves

Authors

  • A.V. Bessalov Киевский университет имени Бориса Гринченко, Ukraine https://orcid.org/0000-0002-6967-5001
  • O.V. Tsygankova Національний технічний університет України «Київський Політехнічний Інститут», Ukraine
  • S.V. Abramov Киевский университет имени Бориса Гринченко, Ukraine https://orcid.org/0000-0002-5145-2782

DOI:

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

Keywords:

curve in generalized Edwards form, complete Edwards curve, twisted Edwards curve, quadratic Edwards curve, curve order, point order, isomorphism, isogeny, w-coordinates, quadratic residue, quadratic non residue

Abstract

The properties of twisted and quadratic supersingular Edwards curves that form pairs of quadratic torsion with order p+1  over a prime field Fp are considered. A modification of the CSIDH algorithm based on the isogenies of these curves instead of the traditional arithmetic of curves in the Montgomery form is presented. The parameters of these two classes of supersingular Edwards curves for p=239 are calculated and tabulated. An example of the isogenies of these curves in the implementation of the CSIDH algorithm as a non-interactive secret sharing scheme based on the secret and public keys of Alice and Bob is given. It is shown that the sequences of parameters ±d(i) of isogeny chains for quadratic and twisted supersingular Edwards curves, respectively, have a reverse nature on the period of the sequence. A recurrent algorithm for calculating the coordinates of points that form the kernels of isogenies of odd degrees is proposed, and its implementation in various coordinate systems is considered. A comparative analysis of the cost of calculating the parameter d´ of the isogenic curve E´ using the Farashakhi-Hosseini (W : Z) - coordinates and classical projective coordinates (X : Y : Z) is given. It is noted that all calculations in the CSIDH algorithm necessary to calculate the shared secret dAB are reduced only to the calculation of the isogenic curve E´ parameter d´ and are performed by field operations and the scalar multiplication of the point. The controversial issue of refusal to calculate the isogenic function ϕ(R) of a curve point R in the CSIDH algorithm is discussed.

References

Bessalov A., Sokolov V., Skladannyi P., Zhyltsov O. Computing of odd degree isogenies on supersingular twisted Edwards curves // CEUR Workshop Proceedings. 2021. 2923, pp. 1–11. (2021).

Jao and L. de Feo. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies // Post-Quantum Cryptography, pp. 19-34 (2011).

Castryck W., Lange T., Martindale C., Panny L., Renes J. CSIDH: An efficient post-quantum commutative group action // Peyrin, T., Galbraith, S. (eds.) Advances in Cryptology {ASIACRYPT 2018. pp. 395{427. Springer International Publishing, Cham (2018).

Suhri Kim, Kisoon Yoon, Young-Ho Park, and Seokhie Hong. Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves. Security and Communication Networks, 2019.

Farashahi R.R., Hosseini S.G. Differential addition on twisted Edwards curves. In: Pieprzyk, J., Suriadi, S. (eds.) Information Security and Privacy. pp. 366{378. Springer International Publishing, Cham (2017).

Suhri Kim, Kisoon Yoon, Jihoon Kwon, Seokhie Hong , and Young-Ho Park Efficient Isogeny Computations on Twisted Edwards Curves Hindawi Security and Communication NetworksVolume.

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).

A. Bessalov V. Sokolov P. Skladannyi. Modeling of 3- and 5-Isogenies of Supersingular Edwards Curves // Proceedings of the 2nd International Workshop on Modern Machine Learning Technologies and Data Science (MoMLeT&DS’2020), June 2–3, 2020: abstracts. No. I, vol. 2631. Aachen : CEUR, 2020. P. 30–39.

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-1.

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

Bessalov A.V., Tsygankova O.V. Number of curves in the generalized Edwards form with minimal even cofactor of the curve order // Problems of Information Transmission. Vol. 53, Is. 1 (2017). P. 92-101. doi:10.1134/S0032946017010082.

Bessalov A.V., Kovalchuk L.V. Supersingular Twisted Edwards Curves Over Prime Fields. I. Supersingular Twisted Edwards Curves with j-Invariants Equal to Zero and 123 // Cybernetics and Systems Analysist. 2019. 55(3). Р. 347–353.

Bessalov A.V., Kovalchuk, L.V.Supersingular Twisted Edwards Curves over Prime Fields.* II. Supersingular Twisted Edwards Curves with the j-Invariant Equal to 663 // Cybernetics and Systems Analysist. 2019. 55(5). Р. 731–741.

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

H. Onuki, Y. Aikawa, T. Yamazaki, T. Takagi. A Faster Constant-time Algorithm of CSIDH keeping Two Points. ASIACRYPT, 2020.

A. Jalali, R. Azarderakhsh, M. M. Kermani, D. Jao. Towards optimized and constant-time CSIDH on em-bedded devices // IACR Cryptology ePrint Archive 2019/297; https://eprint.iacr.org/2019/297. (to apper at COSADE 2019).

Published

2021-12-24

How to Cite

Bessalov, A. ., Tsygankova, O. ., & Abramov, S. . (2021). Estimation of the computational cost of the CSIDH algorithm on supersingular twisted and quadratic Edwards curves. Radiotekhnika, 4(207), 40–51. https://doi.org/10.30837/rt.2021.4.207.03

Issue

Section

Articles