Optimizations of Isogeny-based Key Exchange

Supersingular Isogeny Diffie-Hellman (SIDH) is a key exchange scheme that is believed to
be quantum-resistant. It is based on the difficulty of finding a certain isogeny between given
elliptic curves. Over the last nine years, optimizations have been proposed that significantly
increased the performance of its implementations. Today, SIDH is a promising candidate in
the US National Institute for Standards and Technology’s (NIST’s) post-quantum cryptography
standardization process.
This work is a self-contained introduction to the active research on SIDH from a high-level,
algorithmic lens. After an introduction to elliptic curves and SIDH itself, we describe the
mathematical and algorithmic building blocks of the fastest known implementations.
Regarding elliptic curves, we describe which algorithms, data structures and trade-offs regard-
ing elliptic curve arithmetic and isogeny computations exist and quantify their runtime cost in
field operations. These findings are then tailored to the situation of SIDH. As a result, we give
efficient algorithms for the performance-critical parts of the protocol.