Speeding up CSIDH using parallel computation of isogeny
Ganma Kato, Koutarou Suzuki · 2020
Isogeny-based cryptography is a promising candidate for post-quantum cryptography. CSIDH is a Diffie-Hellman key exchange protocol based on isogeny with a small public key size and is secure against a quantum computer. However, one of the problems is that it takes a long time to compute the group action corresponding to the secret key. Several efficiency improvements have already been studied, such as the SIMBA technique by Meyer, Campos, and Reith, and the two-point method by Onuki, Aikawa, Yamazaki, and Takagi. In this paper, we propose parallel computation method for the isogeny in CSIDH, which speeds up the computation of the isogeny from O(d) to O(logd), where d = (ℓ-1)/2 and ℓ is the degree of the isogeny.