RANDOMIZATION OF CSIDH ALGORITHM ON QUADRATIC AND TWISTED EDWARDS CURVES
Open Access
- 29 September 2022
- journal article
- Published by Borys Grinchenko Kyiv University in Cybersecurity: Education, Science, Technique
- Vol. 1 (17), 128-144
- https://doi.org/10.28925/2663-4023.2022.17.128144
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.Keywords
This publication has 14 references indexed in Scilit:
- Supersingular Twisted Edwards Curves over Prime Fields.* II. Supersingular Twisted Edwards Curves with the j-Invariant Equal to 663Cybernetics and Systems Analysis, 2019
- Supersingular Twisted Edwards Curves Over Prime Fields. I. Supersingular Twisted Edwards Curves with j-Invariants Equal to Zero and 123Cybernetics and Systems Analysis, 2019
- Towards Optimized and Constant-Time CSIDH on Embedded DevicesPublished by Springer Science and Business Media LLC ,2019
- CSIDH: An Efficient Post-Quantum Commutative Group ActionPublished by Springer Science and Business Media LLC ,2018
- Efficient Isogeny Computations on Twisted Edwards CurvesSecurity and Communication Networks, 2018
- Differential Addition on Twisted Edwards CurvesLecture Notes in Computer Science, 2017
- Number of curves in the generalized Edwards form with minimal even cofactor of the curve orderProblems of Information Transmission, 2017
- Analogues of Vélu’s formulas for isogenies on alternate models of elliptic curvesMathematics of Computation, 2015
- Twisted Edwards CurvesPublished by Springer Science and Business Media LLC ,2008
- Faster Addition and Doubling on Elliptic CurvesPublished by Springer Science and Business Media LLC ,2007