We present novel strategies and concrete algorithms for the parallel computation of the Supersingular Isogeny-based Diffie-Hellman key exchange (SIDH) protocol when executed on multi-core platforms. The most relevant design idea exploited by our approach is that of concurrently computing scalar multiplication operations along with a parallelized version of the strategies required for constructing and evaluating large smooth degree isogenies. We report experimental results showing that a three-core implementation of our parallel approach achieves an acceleration factor of 1.45 compared against a sequential implementation of the Supersingular Isogeny Key Encapsulation (SIKE) protocol instantiated with the prime p751

Abstract The supersingular isogeny Diffie–Hellman key exchange protocol (SIDH) was introduced by Jao and De Feo in 2011. SIDH operates on supersingular elliptic curves defined over , where p is a large prime number of the form and e A and e B are positive integers such that . A variant of the SIDH protocol, dubbed extended SIDH (eSIDH), is presented. The eSIDH makes use of primes of the form . Here ℓ B and ℓ C are two small prime numbers; f is a cofactor; and e A , e B , and e C are positive integers such that . It is shown that for many relevant instantiations of the SIDH protocol, this new family of primes enjoys faster field arithmetic than the one associated with traditional SIDH primes. Furthermore, its richer opportunities for parallelism yield a noticeable speed‐up factor when implemented on multicore platforms. A supersingular isogeny key encapsulation (SIKE) instantiation using the prime eSIDH‐ p 765 yields an acceleration factor of 1.06, 1.15 and 1.14 over a SIKE instantiation with the prime SIKE‐ p 757 when implemented on k = {1, 2, 3}‐core processors. To the authors’ knowledge, this work reports the first multicore implementation of SIDH and SIKE.

Since its introduction by Jao and De Feo in 2011, the supersingular isogeny Diffie-Hellman (SIDH) key exchange protocol has positioned itself as a promising candidate for post-quantum cryptography. One salient feature of the SIDH protocol is that it requires exceptionally short key sizes. However, the latency associated to SIDH is higher than the ones reported for other post-quantum cryptosystem proposals. Aiming to accelerate the SIDH runtime performance, we present in this work several algorithmic optimizations targeting both elliptic-curve and field arithmetic operations. We introduce in the context of the SIDH protocol a more efficient approach for calculating the elliptic curve operation$P+[k]Q$. Our strategy achieves a factor 1.4 speedup compared with the popular variable-three-point ladder algorithm regularly used in the SIDH shared secret phase. Moreover, profiting from pre-computation techniques our algorithm yields a factor 1.7 acceleration for the computation of this operation in the SIDH key generation phase. We also present an optimized evaluation of the point tripling formula, and discuss several algorithmic and implementation techniques that lead to faster field arithmetic computations. A software implementation of the above improvements on an Intel Skylake Core i7-6700 processor gives a factor 1.33 speedup against the state-of-the-art software implementation of the SIDH protocol reported by Costello-Longa-Naehrig in CRYPTO 2016.