RANDOMIZATION OF CSIDH ALGORITHM ON QUADRATIC AND TWISTED EDWARDS CURVES
DOI:
https://doi.org/10.28925/2663-4023.2022.17.128144Keywords:
curve in generalized Edwards form, complete Edwards curve, twisted Edwards curve, quadratic Edwards curve, curve order, point order, isomorphism, isogeny, randomization, w-coordinates, square, non-square.Abstract
The properties of quadratic and twisted supersingular Edwards curves that form pairs of quadratic twist with order over a prime field are considered. A modification of the CSIDH algorithm based on odd degree isogenies of these curves is considered. A simple model for the implementation of the CSIDH algorithm in 3 minimal odd isogeny degrees 3, 5, 7, with the prime field modulus and the order of supersingular curves is constructed. At the precipitation stage, the parameters of isogenic chains of all degrees for these two classes of supersingular Edwards curves are calculated and tabulated. An example of 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. A new randomized CSIDH algorithm with a random equiprobable choice of one of the curves of these two classes at each step of the isogeny chain is proposed. The choice of the degree of each isogeny is randomized. The operation of the randomized algorithm by an example is illustrated. This algorithm as a possible alternative to "CSIDH with constant time" is considered. A combination of the two approaches is possible to counter side channel attacks. Estimates of the probability of a successful side-channel attack in a randomized algorithm are given. It is noted that all calculations in the CSIDH algorithm necessary to calculate the shared secret are reduced only to calculating the parameter of the isogenic curve and are performed by field and group operations, in particular, scalar point multiplications and doubling points of the isogeny kernel. In the new algorithm we propose to abandon the calculation of the isogenic function of random point , which significantly speeds up the algorithm.
Downloads
References
Bessalov, A., Sokolov, V., Skladannyi, P., Zhyltsov, O. (2021). Computing of odd degree isogenies on supersingular twisted Edwards curves. CEUR Workshop Proceedings, 2923, 1–11.
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 (pp. 395–427). Springer International Publishing. https://doi.org/10.1007/978-3-030-03332-3_15
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 (pp. 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 (pp. 366–378). Springer International Publishing. https://doi.org/10.1007/978-3-319-59870-3_21.
Kim, S., Yoon, K., Kwon, J., Hong, S., Park, Y.-H. (2018). Efficient Isogeny Computations on Twisted Edwards Curves. Security and Communication Networks, 2018, 1–11. https://doi.org/10.1155/2018/5747642
Moody, D., Shumow, D. (2016). Analogues of Velus formulas for isogenies on alternate models of elliptic curves. Mathematics of Computation, 85(300), 1929–1951.
Bessalov, A.V., Tsyhankova, O.V. Abramov, S.V. (2021). Otsenka vychyslytelnoi slozhnosty alhorytma CSIDH na supersynhuliarnykh skruchennykh y kvadratychnykh kryvykh Edvardsa. Radyotekhnyka, 207, 40-51.
Bernstein, D. J., Lange, T. (2007). Faster Addition and Doubling on Elliptic Curves. In Advances in Cryptology – ASIACRYPT 2007 (pp. 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. (2008). Twisted Edwards Curves. In Progress in Cryptology – AFRICACRYPT 2008 (pp. 389–405). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-68164-9_26
Bessalov, A.V. (2017). Ellyptycheskye kryvye v forme Edvardsa y kryptohrafyia. Monohrafyia. «Polytekhnyka».
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.
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 Analysist, 55(3), 347–353.
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 Analysist, 55(5), 731–741.
Washington, L.C. (2008). Elliptic Curvres. Number Theory and Cryptography. Second Edition. CRC Press.
Onuki, H., Aikawa, Y., Yamazaki, T., Takagi, T. (2020). A Faster Constant-time Algorithm of CSIDH keeping Two Points. ASIACRYPT.
Jalali, A., Azarderakhsh, R., Kermani, M. M., Jao, D. (2019). Towards Optimized and Constant-Time CSIDH on Embedded Devices. У Constructive Side-Channel Analysis and Secure Design (с. 215–231). Springer International Publishing. https://doi.org/10.1007/978-3-030-16350-1_12
