SIDH

Stolbunov proposed a Diffie-Hellman type scheme based on the difficulty of computing isogenies between ordinary elliptic curves, with the aim of obtaining quantum-resistant cryptographic protocols ¹. The fastest known classical probabilitic algorithm for solving this problem is an algorithm of Galbraith and Stolbunov ², which is exponential with a worst-case running time of $O(^4\sqrt{q})$. However, on a quantum computer, Childs, Jao, and Soukharev. ³ 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 128-bit security level on a desktop computer.

In 2011, De Feo, Jao and Plût published a paper entitled ‘Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies’, which presented isogeny-based key-exchange and encryption schemes that address both the performance and security drawbacks of Stolbunov’s system. They named their key-exchange protocol SIDH, for Supersingular Isogeny Diffie-Hellman.

Assumed knowledge:

• Isogenies for Cryptography

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.

Non-Commutative

The main technical difficulty is that, in the supersingular case, the endomorphism ring is noncommutative, whereas Diffie-Hellman 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 key-exchange protocol and a public-ley cryptosystem using supersingular elliptic curves.

Setup

We first discuss the choice of prime $p$ in ⁴. 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}\]

Key-Exchange 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 key-exchange protocol above to give a PKE scheme, in a similar vein to constructing ElGamal Encryption from Diffie-Hellman. 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 Diffie-Hellman (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 Diffie-Hellman (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 entropy-smoothing), the PKE scheme is IND-CPA. The proof is routine and an easy adaptation from the corresponding proofs given by Stolbunov for ordinary elliptic curves ¹. We therefore omit it and ask an interested reader to refer to pg. 19, ⁴.

Active Attacks on SIDH

Galbraith, Petit, Shani, and Ti gave a polynomial-time active attack against SIDH with static keys ⁵ using the additional torsion-point information revealed during the protocol. To mitigate the affects of this attack, the authors proposed applying a transformation to SIDH to generate a IND-CCA 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 post-quantum standardization effort ⁶. 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 post-quantum 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 code-based 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 ⁴. 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 ⁷. He proposed a classical algorithm that, for certain choices of parameters, solves the following problem in polynomial-time: 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 non-standard variants of SIDH satisfying $B > A^4 > p^4$. For efficiency, Jao and Feo proposed taking $A, B \approx \sqrt{p}$, so this passive polynomial-attack does not apply to SIDH/SIKE parameters.

In 2020, Kutas, Martindale, Panny, Petit, and Stange improved on this, providing polynomial-time attacks with more relaxed the conditions on $A, B$ ⁸. They also demonstrate how choosing an insecure starting curve $E_0$ can lead to polynomial-time attacks for certain $A$ and $B$. Another attack recently proposed in ANTS-XIV 2020 by Kutas, Merz, Petit, and Weitkämper consists of a hidden shift quantum attack when $A$ and $B$ are unbalanced ⁹. 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.