Paper 2020/021

eSIDH: the revenge of the SIDH

Daniel Cervantes-Vázquez, Eduardo Ochoa-Jiménez, and Francisco Rodríguez-Henríquez

Abstract

The Supersingular Isogeny-based Diffie-Hellman key exchange protocol (SIDH) was introduced by Jao an De Feo in 2011. SIDH operates on supersingular elliptic curves defined over quadratic extension fields of the form GF($p^2$), where $p$ is a large prime number of the form $p=4^{e_A}{3}^{e_B}-1,$ where $e_A,e_B$ are positive integers such that $4^{e_A}\approx 3^{e_B}.$ In this paper, a variant of the SIDH protocol that we dubbed extended SIDH (eSIDH) is presented. The eSIDH variant makes use of primes of the form, $p=4^{e_A}{\ell }_B^{e_B}{\ell }_C^{e_C}f-1.$ Here ${\ell }_B,{\ell }_C$ are two small prime numbers; $f$ is a cofactor; and $e_A,e_B$ and $e_C$ are positive integers such that $4^{e_A}\approx {\ell }_B^{e_B}{\ell }_C^{e_C}.$ We show that for many relevant instantiations of the SIDH protocol, this new family of primes enjoys a faster field arithmetic than the one associated to traditional SIDH primes. Furthermore, the proposed eSIDH protocol preserves the length and format of SIDH private/public keys, and its richer opportunities for parallelism yields a noticeable speedup factor when implemented on multi-core platforms. Using a single-core SIDH $$ implementation as a baseline, a parallel eSIDH $$ instantiation yields an acceleration factor of $$ and $$ when implemented on $$-core processors. In addition, eSIDH $$ yields an acceleration factor of $$ and $$ when both protocols are implemented on $$-core processors. To our knowledge, this work reports the first multi-core implementation of SIDH.