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 $p_{751}$ implementation as a baseline, a parallel eSIDH $p_{765}$ instantiation yields an acceleration factor of $1.05, 1.30$ and $1.41,$ when implemented on $k = \{1, 2, 3\}$-core processors. In addition, eSIDH $p_{765}$ yields an acceleration factor of $1.050, 1.160$ and $1.162.$ when both protocols are implemented on $k = \{1, 2, 3\}$-core processors. To our knowledge, this work reports the first multi-core implementation of SIDH.