SIDH
Stolbunov proposed a DiffieHellman type scheme based on the difficulty of computing isogenies between ordinary elliptic curves, with the aim of obtaining quantumresistant cryptographic protocols ^{1}. The fastest known classical probabilitic algorithm for solving this problem is an algorithm of Galbraith and Stolbunov ^{2}, which is exponential with a worstcase running time of $O(^4\sqrt{q})$. However, on a quantum computer, Childs, Jao, and Soukharev. ^{3} showed that the private keys in Stolbunov’s system can be recovered in subexponential time.
Another issue is efficieny: even if we only consider classical attacks in assessing security levels, Stolbunov’s scheme requires 229 seconds (even with precomputation) to perform a single key exchange operation at the 128bit security level on a desktop computer.
In 2011, De Feo, Jao and Plût published a paper entitled ‘Towards QuantumResistant Cryptosystems from Supersingular Elliptic Curve Isogenies’, which presented isogenybased keyexchange and encryption schemes that address both the performance and security drawbacks of Stolbunov’s system. They named their keyexchange protocol SIDH, for Supersingular Isogeny DiffieHellman.
Assumed knowledge:
Throughout this we will assume that we are working over a finite field $\mathbb{F}_q$.
Background
Supersingular vs. Ordinary
There are two types of elliptic curves that we can have are ordinary or supersingular. The precise definitions are unimportant for cryptographic purposes, however it is useful to note that supersingular curves are all defined over $\mathbb{F}_{p^2}$, so for the finite field we’re working over, we can take $q = p^2$.
If we have two elliptic curves $E_1$ and $E_2$ such that there exists an isogeny $\phi$ connecting them, then we say that $E_1$ and $E_2$ are in the same isogeny class.
FACT: Ellitpic curves in the same isogeny class are either all supersingular or all ordinary.
In SIDH we will be going from one ellitpic curve, say $E$ , to another via an isogeny (or a composition of various isogenies). The fact above tells us that if we start with a supersingular curve, we will end up at another supersingular curve. This is a highly desirable property as it means we don’t have to make any restrictions on the isogenies we choose from $E$ to ensure we end up at a supersingular curve.
NonCommutative
The main technical difficulty is that, in the supersingular case, the endomorphism ring is noncommutative, whereas DiffieHellman type protocols require commutativity. In the paper, they propose overcoming this obstacle by providing the outputs of the isogeny on certain points as auxiliary input to the protocols. Provided this auxiliary input does not make the problem of finding isogenies any easier, the added difficulty arising from the anticommutativity actually makes the protocol stronger.
Before analysing the security of the scheme in greater detail, we describe how to get various types of protocols using supersingular elliptic curves.
Schemes using Supersingular Elliptic Curves
In this section we present a keyexchange protocol and a publicley cryptosystem using supersingular elliptic curves.
Setup
We first discuss the choice of prime $p$ in ^{4}. Fix the finite field $\mathbb{F}_{p^2}$, where
\[p = l_A^{e_A}l_B^{e_B}\cdot f \pm 1\]In the original SIDH paper $(l_A, l_B) = (2,3)$, to exploit efficient isogeny computations. To provide the same security level for both Alice and Bob we set $2^{e_A} \approx 3^{e_B}$. An integer $f$ is then chosen so $p$ is prime. This choice of $p$ ensures isogeny computations can be done over $\mathbb{F}_{p^2}$.
We also fix supersingular curve $E_0$ and bases {$P_A, Q_A$} and {$P_B, Q_B$} which generate $E_0[l_A^{e_A}]$ and $E_0[l_B^{e_B}]$ respectively. Such bases can be found as
\[E_0[l_i^{e_i}] \cong \mathbb{Z}/l_i^{e_i}\mathbb{Z} \times \mathbb{Z}/l_i^{e_i}\mathbb{Z}\]KeyExchange Protocol
Step 1: Alice chooses random elements $m_A, n_A \in \mathbb{Z}/l_A^{e_A}\mathbb{Z}$, not both divisible by $l_A$ and computes $\phi_A: E_0 \rightarrow E_A$ with kernel $K_A := \langle [m_A]P_A + [n_A]Q_A \rangle$. Bob similarly computes $\phi_B$ with kernel $K_B$.
Alice then computes $\phi_A(P_B), \phi_A(Q_B) \in E_A$ and sends them to Bob. Bob proceeds analogously. This step was proposed by Jao and De Feo to overcome the fact that $\phi_A$ and $\phi_B$ cannot be composed due to mismatching domains and codomains.
Step 2: Alice computes $\phi$’$_A: E_B \rightarrow E_{BA}$ with kernel $\langle [m_A]\phi_B(P_A) + [n_A]\phi_B(Q_A) \rangle$. Similarly, Bob computes $\phi$’$_B: E_A \rightarrow E_{AB}$. Noting $E_{AB} = E_{BA}$, Alice and Bob use the common $j$invariant of $E_{AB}$ as the secret shared key.
Public Key Encryption
Jao, De Feo and Plût adapted the keyexchange protocol above to give a PKE scheme, in a similar vein to constructing ElGamal Encryption from DiffieHellman. In the setup we also need a family of hash functions $\mathcal{H}$ = {$H_k$}$_{k \in K}$, where $K$ is a finite set and each $H_k$ is a function from $\mathbb{F}_{p^2}$ to the message space.
Key Generation: Let $m_A, n_A, E_A, \phi_A(P_B), \phi_A(Q_B)$ be as above and choose a random element $k \in K$. The public key and secret key are
\[\texttt{pk} = (E_A, \phi_A(P_B), \phi_A(Q_B), k) \text{, } \texttt{sk} = (m_A, n_A, k)\]Encryption: Given $\texttt{pk}$ and message $m$, choose $m_B, n_B$ as above and compute $j$invariant $j(E_{AB})$. Set
\[h = H_k(j(E_{AB})) \text{, } c = h \oplus m\]The ciphertext is $\texttt{ct} = (E_B, \phi_B(P_A), \phi_B(Q_A), c)$.
Decryption: Given $\texttt{ct}$ and $\texttt{sk}$, compute $j(E_{AB})$ and set
\[h = H_k(j(E_AB)) \text{, } m = h \oplus c\]The plaintext is $m$.
Security
Using the same notation, we define computational problems these schemes are based on.
Supersingular Computational DiffieHellman (SSCDH) Problem: Given the curves $E_A, E_B$ and the points $\phi_A(P_B), \phi_A(Q_B), \phi_B(P_A), \phi_B(Q_B)$, find the $j$invariant of $E_0/\langle [m_A]P_A + [n_A]Q_A, [m_B]P_B + [n_B]Q_B \rangle$.
Supersingular Decision DiffieHellman (SSDDH) Problem: Given a tuple sampled with probability $\frac{1}{2}$ from one of the following two distributions:

$(E_A, E_B, \phi_A(P_B), \phi_A(Q_B), \phi_B(P_A), \phi_B(Q_A), E_{AB})$, where
\[E_{AB} \cong E_0/\langle [m_A]P_A + [n_A]Q_A, [m_B]P_B + [n_B]QB \rangle\] 
$(E_A, E_B, \phi_A(P_B), \phi_A(Q_B), \phi_B(P_A), \phi_B(Q_A), E_C)$, where
\[E_C \cong E_0/\langle [m'\_A]P_A + [n'\_A]Q_A, [m'\_B]P_B + [n'\_B]Q_B \rangle\]where $m’_A, n’_A$ are chosen at random from $\mathbb{Z}/l_A^{e_A}\mathbb{Z}$ and not both divisible by $l_A$, and similarly for $m’_B, n’_B$,
determine from which distribution the tuple is sampled.
We first note that given an SSCDH solver, we can solve SSDDH. Jao, De Feo and Plût proved that given the SSDDH assumption holds, for a particular class of hash function families $\mathcal{H}$ (namely, they must be entropysmoothing), the PKE scheme is INDCPA. The proof is routine and an easy adaptation from the corresponding proofs given by Stolbunov for ordinary elliptic curves ^{1}. We therefore omit it and ask an interested reader to refer to pg. 19, ^{4}.
Active Attacks on SIDH
Galbraith, Petit, Shani, and Ti gave a polynomialtime active attack against SIDH with static keys ^{5} using the additional torsionpoint information revealed during the protocol. To mitigate the affects of this attack, the authors proposed applying a transformation to SIDH to generate a INDCCA secure scheme called Supersingular Isogeny Key Encapsulation, or SIKE. Details of how this is done can be found in the SIKE proposal for NIST’s postquantum standardization effort ^{6}. Essentially, a key encapsulation mechanism (KEM) uses the public key to create a ciphertext containing a randomly chosen symmetric key, called encapsulation.
In July 2020, Round 3 finalists for NISTs postquantum cryptography standardization effort were announced and included SIKE as an alternative candidate. Compared to other candidates, the main practical advantage of SIKE is its relatively small key sizes. However, although SIKE can be seen to be practical enough for many applications, it is still at least an order of magnitude slower than lattice and codebased round 3 candidates.
Passive Attacks on SIDH
When constructing the isogenies of degree $l_A^{e_A}$, we take kernels of a special form. This means that there are only around $\sqrt{p}$ possible choices for the ending curve $E_A$, whereas there are around $\frac{p}{12}$ supersingular $j$invariants over $\mathbb{F}_{p^2}$. Using this, Jao, De Feo and Plût determined the best classical and quantum attacks had complexity $\tilde{O}(p^{1/4})$ and $\tilde{O}(p^{1/6})$ respectively for a generic curve pair ^{4}. However, these attacks do not use the extra torsion point information.
In 2017, Petit analysed the impact of providing extra points in the hardness of the underlying assumptions ^{7}. He proposed a classical algorithm that, for certain choices of parameters, solves the following problem in polynomialtime: For a large prime $p$, smooth coprime integers $A$ and $B$, given two supersingular elliptic curves $E_0$ and $E$ over $\mathbb{F}_{p^2}$ connected by a degree$A$ isogeny $\phi: E_0 \rightarrow E$, and given the action of $\phi$ on the $B$torsion of $E_0$ recover $\phi$.
Petit’s attack only works for nonstandard variants of SIDH satisfying $B > A^4 > p^4$. For efficiency, Jao and Feo proposed taking $A, B \approx \sqrt{p}$, so this passive polynomialattack does not apply to SIDH/SIKE parameters.
In 2020, Kutas, Martindale, Panny, Petit, and Stange improved on this, providing polynomialtime attacks with more relaxed the conditions on $A, B$ ^{8}. They also demonstrate how choosing an insecure starting curve $E_0$ can lead to polynomialtime attacks for certain $A$ and $B$. Another attack recently proposed in ANTSXIV 2020 by Kutas, Merz, Petit, and Weitkämper consists of a hidden shift quantum attack when $A$ and $B$ are unbalanced ^{9}. Currently it is not better than previous attacks but is fundamentally different and disproves the claim in the original SIDH paper that the hidden shift attack could not be adapted to an attack on SIDH. The restrictions on $A$ and $B$ mean both these results still do not affect the security of SIKE, but in anticipation of future cryptanalysis progress it is desirable to design variants of SIDH that rely on the original general isogeny problem.

Anton Stolbunov. Reductionist security arguments for publickey cryptographic schemes based on group actions. Norsk informasjonssikkerhetskonferanse (NISK), pages 97109, 2009. ↩ ↩^{2}

Steven D Galbraith and Anton Stolbunov. Improved algorithm for the isogeny problem for ordinary elliptic curves. Applicable Algebra in Engineering, Communication and Computing 24(2), pages 107131, 2013. ↩

Andrew Childs, David Jao, and Vladimir Soukharev. Constructing elliptic curve isogenies in quantum subexponential time. Journal of Mathematical Cryptology, 8(1), pages 129, 2014. ↩

David Jao, Luca De Feo and Jérôme Plût. Towards quantumresistant cryptosystems from supersingular elliptic curve isogenies. In Springer, editor, International Workshop on PostQuantum Cryptography, pages 1934, 2011. ↩ ↩^{2} ↩^{3}

Steven D Galbraith, Christophe Petit, Barak Shani, and Yan Bo Ti. On the security of supersingular isogeny cryptosystems. In Springer, editor, International Conference on the Theory and Application of Cryptology and Information Security, pages 6391, 2016. ↩

David Jao et al. Supersingular isogeny key encapsulation October 1, 2020. NIST Round 3, 2020. ↩

Christophe Petit. Faster algorithms for isogeny problems using torsion point images. In Springer, editor, International Conference on the Theory and Application of Cryptology and Information Security, pages 330353, 2017. ↩

Péter Kutas, Chloe Martindale, Lorenz Panny, Christophe Petit, and Katherine E Stange. Weak instances of SIDH variants under improved torsionpoint attacks. arXiv preprint arXiv:2005.14681, 2020. ↩

Péter Kutas, SimonPhilipp Merz, Christophe Petit, and Charlotte Weitkämper. A hidden shift quantum attack on unbalanced SIDH. Rump session, ANTSXIV, July 2020. ↩