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

Downloads

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

No. 207 (2021): 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).