Cryptology ePrint Archive: Report 2021/1320

Faster Key Generation of Supersingular Isogeny Diffie-Hellman

Kaizhan Lin and Fangguo Zhang and Chang-An Zhao

Abstract: Supersingular isogeny Diffie-Hellman (SIDH) is attractive for small public key size, but it is still unsatisfactory due to its efficiency, compared to other post-quantum proposals. In this paper, we focus on the performance of SIDH when the starting curve is $E_6:y^2=x^3+6x^2+x$, which is fixed in Round-3 SIKE implementation. We present several tricks to accelerate key generation of SIDH by precomputing few elements in the base field. We also point out that the main ideas of Costello et al. and Faz-Hernández et al. to improve the ladder performance of SIDH, of which the starting curve is $E_0:y^2=x^3+x$, could be still utilized for the current SIDH protocol.

Category / Keywords: public-key cryptography / SIDH, isogeny-based cryptography, post-quantum cryptography, Montgomery ladder, key generation