C&SA | Contents

Volume 59 >>> № 6 NOVEMBER — DECEMBER 2023

-->

UDC 621.391.15:519.7

A.V. Bessalov¹, S.V. Abramov²

¹ Borys Grinchenko Kyiv University, Kyiv, Ukraine

bessalov@ukr.net

² Borys Grinchenko Kyiv University and Institute of Physics and Technology, Kyiv, Ukraine

s.abramov.asp@kubd.edu.ua

PQC CSIKE ALGORITHM IN NON-CYCLIC EDWARDS CURVES

Abstract. The original post-quantum cryptography algorithm CSIKE is proposed as a modification of CSIDH but with one public key instead of two. The conditions for its implementation on two classes of non-cyclic Edwards curves are substantiated. The properties of quadratic and twisted supersingular Edwards curves that form pairs of quadratic twist of order p +1 ≡ 0 mod 8 over a prime field F_p are considered. A modification of the CSIDH algorithm and the CSIKE algorithm are presented, which are generated on the isogenies of these curves instead of the traditional arithmetic of curves in the Montgomery form. For isogenies of degrees 3, 5, and 7, the parameters of isogenic chains of non-cyclic supersingular Edwards curves are calculated and tabulated for p = 839. The implementation of the key encapsulation scheme with its encryption by Alice with Bob’s public key is considered. A new randomized CSIKE algorithm with random equiprobable selection of a curve from two classes at each step of the isogeny chain is proposed. An estimate of the probability of a successful side-channel attack in a randomized algorithm is given. It is proposed to abandon the calculation of the isogenic function φ( R) of a random point R, which significantly speeds up the algorithm.

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

full text

REFERENCES

Castryck W., Lange T., Martindale C., Panny L., Renes J. CSIDH: An efficient post-quantum commutative group action. In: Advances in Cryptology — ASIACRYPT 2018. Peyrin T., Galbraith S. (Eds.). Lecture Notes in Computer Science. Cham: Springer, 2018. Vol. 11274. P. 395–427. https://doi.org/10.1007/ 978-3-319-59870-3_21.

Kim S., Yoon K., Kwon J., Hong S., Park Y.-H. Efficient isogeny computations on twisted Edwards curves. Security and Communication Networks. 2018. Vol. 2018. Article ID 5747642. https://doi.org/10.1155/2018/5747642.

Moody D., Shumow D. Analogues of VБlu’s formulas for isogenies on alternate models of elliptic curves. Mathematics of Computation. 2016. Vol. 85, N 300. P. 1929–1951.

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

Moriya T., Onuki H., Takagi T. How to construct CSIDH on Edwards curves. In: Topics in Cryptology — CT-RSA 2020. Jarecki S. (Ed.). Lecture Notes in Computer Science. Cham: Springer, 2020. Vol. 12006. P. 512–537. https://doi.org/10.1007/978-3-030-40186-3_22 .

Bessalov A.V. On correctness of implementation conditions CSIDH algorithm on Edwards curves. Radiotekhnika. 2022. Iss. 208. P. 16–27.

Bernstein D.J., Lange T. Faster addition and doubling on elliptic curves. In: Advances in Cryptology — ASIACRYPT 2007. Kurosawa K. (Eds.). Lecture Notes in Computer Science. Berlin; Heidelberg: Springer, 2007. Vol. 4833. P. 29–50. 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. Vaudenay S. (Eds.). Lecture Notes in Computer Science. Berlin; Heidelberg: Springer, 2008. Vol. 5023. P. 389–405. https://doi.org/10.1007/ 978-3-540-68164-9_26.

Bessalov A.V. Elliptic curves in Edwards form and cryptography [in Russian]. Kyiv: Polytechnica, 2017. 272 p.

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. 2017. Vol. 53, N 1. P. 92–101. https://doi.org/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 . Cybernetics and Systems Analysis. 2019. Vol. 55, No. 3. P. 347–353. https://doi.org/10.1007/s10559-019-00140-9.

Bessalov A.V., Kovalchuk L.V. Supersingular twisted Edwards curves over prime fields. II. Supersingular twisted Edwards curves with the j-invariant equal to . Cybernetics and Systems Analysis. 2019. Vol. 55, N 5. P. 731–741. https://doi.org/10.1007/s10559-019-00183-y .

Azarderakhsh R., Campagna M., Costello C., Feo L.D., Hess B., Jalali A., Jao D., Koziel B., LaMacchia B., Longa P., Naehrig M., Renes J., Soukharev V., and Urbanik D. Supersingular isogeny key encapsulation — Submission to the NIST’s post-quantum cryptography standardization process. 2017. URL: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum -Cryptography .

Washington L.C. Elliptic curves. Number theory and cryptography. 2nd ed. CRC Press, 2008. 513 p.

Onuki, H., Aikawa, Y., Yamazaki, T., Takagi, T. (2019). (Short paper) A faster constant-time algorithm of CSIDH keeping two points. In: Attrapadung, N., Yagi, T. (eds) Advances in Information and Computer Security. IWSEC 2019. Lecture Notes in Computer Science, vol 11689. P. 23–33. Springer, Cham. https://doi.org/10.1007/978-3-030-26834-3_2.

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