HOW TO CONSTRUCT CSIDH ON QUADRATIC AND TWISTED EDWARDS CURVES
DOI:
https://doi.org/10.28925/2663-4023.2022.15.148163Keywords:
curve in generalized Edwards form, complete Edwards curve, twisted Edwards curve, quadratic Edwards curve, curve order, point order, isomorphism, isogeny, w-coordinates, square.Abstract
In one of the famous works, an incorrect formulation and an incorrect solution of the implementation problem of the CSIDH algorithm on Edwards curves is discovered. A detailed critique of this work with a proof of the fallacy of its concept is given. Specific properties of three non-isomorphic classes of supersingular curves in the generalized Edwards form is considered: complete, quadratic, and twisted Edwards curves. Conditions for the existence of curves of all classes with the order p+1 of curves over a prime field are determined. The implementation of the CSIDH algorithm on isogenies of odd prime degrees based on the use of quadratic twist pairs of elliptic curves. To this end, the CSIDH algorithm can be construct both on complete Edwards curves with quadratic twist within this class, and on quadratic and twisted Edwards curves forming pairs of quadratic twist. In contrast to this, the authors of a well-known work are trying to prove theorems with statement about existing a solution within one class of curves with a parameter that is a square. The critical analysis of theorems, lemmas, and erroneous statements in this work is given. Theorem 2 on quadratic twist in classes of Edwards curves is proved. A modification of the CSIDH algorithm based on isogenies of quadratic and twisted Edwards curves is presented. To illustrate the correct solution of the problem, an example of Alice and Bob calculations in the secret sharing scheme according to the CSIDH algorithm is considered.
Downloads
References
Moriya, T., Onuki, H., Takagi, T. (2020). How to Construct CSIDH on Edwards Curves. In У Topics in Cryptology – CT-RSA 2020 (p. 512–537). Springer International Publishing. https://doi.org/10.1007/978-3-030-40186-3_22.
Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J. (2018). CSIDH: An Efficient Post-Quantum Commutative Group Action. In Lecture Notes in Computer Science (p. 395–427). Springer International Publishing. https://doi.org/10.1007/978-3-030-03332-3_15.
Bernstein, D. J., Lange, T. (2007). Faster Addition and Doubling on Elliptic Curves. In Advances in Cryptology – ASIACRYPT 2007 (p. 29–50). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-76900-2_3.
Bernstein, D. J., Birkner, P., Joye, M., Lange, T., Peters, C. (б. д.). Twisted Edwards Curves. In Progress in Cryptology – AFRICACRYPT 2008 (p. 389–405). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-68164-9_26
Kim, S., Yoon, K., Park, Y.-H., Hong, S. (2019). Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves. In Lecture Notes in Computer Science (p. 273–292). Springer International Publishing. https://doi.org/10.1007/978-3-030-34621-8_10
Farashahi, R. R., Hosseini, S. G. (2017). Differential Addition on Twisted Edwards Curves. In Information Security and Privacy (p. 366–378). Springer International Publishing. https://doi.org/10.1007/978-3-319-59870-3_21
Moody, D., Shumow, D. (2015). Analogues of Vélu’s formulas for isogenies on alternate models of elliptic curves. Mathematics of Computation, 85(300), 1929–1951. https://doi.org/10.1090/mcom/3036
Bessalov, A., Sokolov, V., Skladannyi, P., Zhyltsov, O. (2021). Computing of odd degree isogenies on supersingular twisted Edwards curves. In CEUR Workshop Proceedings, 2923 (p. 1-11).
Bessalov, A.V., Tsygankova, O.V. Abramov, S.V. (2021). Otsenka vychislitel'noy slozhnosti algoritma CSIDH na supersingulyarnykh skruchennykh i kvadratichnykh krivykh Edvardsa. Radiotekhnika, (207), 40-51.
Bessalov, A., Sokolov, V., Skladannyi, P. (2020). Modeling of 3- and 5-Isogenies of Supersingular Edwards Curves. In Proceedings of the 2nd International Workshop on Modern Machine Learning Technologies and Data Science (MoMLeT&DS’2020) (p. 30–39). CEUR.
Bessalov, A.V. (2017). Ellipticheskiye krivyye v forme Edvardsa i kriptografiya. Monografiya. «Politekhnika».
Bessalov, A. V., Tsygankova, O. V. (2017). Number of curves in the generalized Edwards form with minimal even cofactor of the curve order. Problems of Information Transmission, 53(1), 92–101. https://doi.org/10.1134/s0032946017010082
Bessalov, A. V., Kovalchuk, L. V. (2019). Supersingular Twisted Edwards Curves Over Prime Fields. I. Supersingular Twisted Edwards Curves with j-Invariants Equal to Zero and 123. Cybernetics and Systems Analysis, 55(3), 347–353. https://doi.org/10.1007/s10559-019-00140-9.
Bessalov, A. V., Kovalchuk, L. V. (2019). Supersingular Twisted Edwards Curves over Prime Fields.* II. Supersingular Twisted Edwards Curves with the j-Invariant Equal to 663. Cybernetics and Systems Analysis, 55(5), 731–741. https://doi.org/10.1007/s10559-019-00183-y.
Washington, L. C. (2008). Elliptic curves: Number theory and cryptography (2nd view). Chapman & Hall/CRC.
Jalali, A., Azarderakhsh, R., Kermani, M. M., Jao, D. (2019). Towards Optimized and Constant-Time CSIDH on Embedded Devices. In Constructive Side-Channel Analysis and Secure Design (p. 215–231). Springer International Publishing. https://doi.org/10.1007/978-3-030-16350-1_12
