Cryptology ePrint Archive: Report 2019/843

How to Construct CSIDH on Edwards Curves

Tomoki Moriya and Hiroshi Onuki and Tsuyoshi Takagi

Abstract: CSIDH is an isogeny-based key exchange protocol proposed by Castryck, Lange, Martindale, Panny, and Renes in 2018. CSIDH is based on the ideal class group action on $\mathbb{F}_p$-isomorphic classes of Montgomery curves. In order to calculate the class group action, we need to take points defined over $\mathbb{F}_{p^2}$. The original CSIDH algorithm requires a calculation over $\mathbb{F}_p$ by representing points as $x$-coordinate over Montgomery curves. Meyer and Reith proposed a faster CSIDH algorithm in 2018 which calculates isogenies on Edwards curves by using a birational map between a Montgomery curve and an Edwards curve. If we try to calculate the class group action on Edwards curves in a similar way on Montgomery curves, we have to consider points defined over $\mathbb{F}_{p^4}$. Therefore, it is not a trivial task to calculate the class group action on Edwards curves over $\mathbb{F}_p$.

In this paper, we prove a number of theorems on the properties of Edwards curves. By using these theorems, we devise a new CSIDH algorithm that uses only Edwards curves while calculating over $\mathbb{F}_p$. This algorithm is as fast as (or a little bit faster than) the algorithm proposed by Meyer and Reith.

Category / Keywords: public-key cryptography / Isogeny-based cryptography, Montgomery curves, Edwards curves, CSIDH, Post-quantum cryptography

Date: received 19 Jul 2019

Contact author: tomoki_moriya at mist i u-tokyo ac jp

Available format(s): PDF | BibTeX Citation

Version: 20190719:135020 (All versions of this report)

Short URL: ia.cr/2019/843


[ Cryptology ePrint archive ]