Supersingular Isogeny Diffie-Hellman

The Supersingular Isogeny Diffie-Hellman (SIDH) assumption underlies a family of post-quantum key exchange protocols based on the conjectured hardness of computing isogenies between supersingular elliptic curves. SIDH was introduced by Jao and De Feo as a candidate post-quantum key exchange — JDF11. In 2022, a classical polynomial-time attack was discovered that completely breaks SIDH — CD22.

Assumption

Let $p$ be a prime and $E$ a supersingular elliptic curve over ${\mathbb{F}}_{p^2}$. An isogeny $\varphi :E\to E^{\prime }$ is a non-trivial rational map that preserves the group structure (a group homomorphism).

The SIDH problem, for distinct small primes ${\ell }_A,{\ell }_B$ and bases $\{P_A,Q_A\}$ of $E[{\ell }_A^{e_A}]$ and $\{P_B,Q_B\}$ of $E[{\ell }_B^{e_B}]$ (both defined over ${\mathbb{F}}_{p^2}$): given $E$, the image curve $E^{\prime }=E/⟨R⟩$ for a random point $R\in E[{\ell }_A^{e_A}]$ of order ${\ell }_A^{e_A}$, and the images $\varphi (P_B),\varphi (Q_B)$ under the isogeny $\varphi :E\to E^{\prime }$ with kernel $⟨R⟩$, find a generator of $⟨R⟩$ — JDF11.

The SIDH key exchange of JDF11 works as follows:

1. Both parties fix supersingular $E/{\mathbb{F}}_{p^2}$ with $\#E({\mathbb{F}}_{p^2})=(p+1{)}^2$, chosen so that $p+1=2^{e_A}{3}^{e_B}$
2. Alice chooses a secret isogeny ${\varphi }_A:E\to E_A$ with cyclic kernel of order $2^{e_A}$; Bob chooses ${\varphi }_B:E\to E_B$ with cyclic kernel of order $3^{e_B}$
3. They exchange $E_A$, $E_B$ and images of each other’s torsion points
4. Shared key: $j(E_{AB})$, the $j$-invariant of the common image curve $E_{AB}=E_B/⟨{\varphi }_B(\ker {\varphi }_A)⟩\cong E_A/⟨{\varphi }_A(\ker {\varphi }_B)⟩$; Alice computes the first from Bob’s torsion-point images, Bob the second

Decisional variant (SSDDH)

The supersingular decision Diffie-Hellman (SSDDH) problem is to distinguish the shared curve $E_{AB}$ from the quotient of $E$ by an independent pair of kernel points, given the SIDH transcript — JDF11. Fix public parameters $\mathsf{pp}=(p,E,P_A,Q_A,P_B,Q_B)$ as in the SIDH problem.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{ssddh}}_{\pp,\calA}(\secpar)$}
\begin{algorithmic}
\State $b \getsr \bits$
\State $R_A, R'_A \getsr \{R \in E[\ell_A^{e_A}] : \mathrm{ord}(R) = \ell_A^{e_A}\}$
\State $R_B, R'_B \getsr \{R \in E[\ell_B^{e_B}] : \mathrm{ord}(R) = \ell_B^{e_B}\}$
\State $\phi_A : E \to E_A := E/\langle R_A \rangle$ ; $\phi_B : E \to E_B := E/\langle R_B \rangle$
\State $E_0 := E/\langle R_A, R_B \rangle$ \Comment{$E_0 \cong E_{AB}$, the shared curve}
\State $E_1 := E/\langle R'_A, R'_B \rangle$
\State $b' \gets \calA(\pp, E_A, E_B, \phi_A(P_B), \phi_A(Q_B), \phi_B(P_A), \phi_B(Q_A), E_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

SSDDH is hard for $\mathsf{pp}$ if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{pp},\mathcal{A}}^{\mathrm{ssddh}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{pp},\mathcal{A}}^{\mathrm{ssddh}}(\lambda )=1\right]-1\right|$$

is negligible.

Known Results

• SIDH was conjectured to be hard for quantum computers (unlike discrete log or factoring assumptions) — JDF11; the conjecture is false: SIDH is broken classically — CD22
• SIDH was selected as a NIST post-quantum cryptography candidate (SIKE) before being broken
• A classical polynomial-time attack on SIDH, using Kani’s theorem and the auxiliary torsion-point information — CD22
• The attack breaks SIDH completely; SIKE was withdrawn from the NIST competition in 2022

Variations

CSIDH

Commutative SIDH (CSIDH) uses a commutative group action on supersingular curves over ${\mathbb{F}}_p$ (rather than ${\mathbb{F}}_{p^2}$). Unlike SIDH, CSIDH does not reveal auxiliary torsion-point information, and it has not been broken by the CD22 attack. It is believed to remain a plausible post-quantum assumption, though quantum sub-exponential attacks exist.

SQISign

A post-quantum digital signature scheme based on isogenies, using a different isogeny graph (Deuring correspondence) and not relying on the broken SIDH assumption.

Attacks

• CD22 classical polynomial-time attack: Exploits the auxiliary torsion-point images in SIDH to recover the secret isogeny efficiently via abelian surface arguments (Kani’s theorem) — CD22
• Quantum sub-exponential attack on CSIDH: Kuperberg’s algorithm for the hidden-shift problem recovers the secret key in quantum subexponential time; a classical meet-in-the-middle attack takes time $\tilde{O}(p^{1/4})$ — Castryck–Lange–Martindale–Panny–Renes (ASIACRYPT 2018)
• The original SIDH assumption (without auxiliary torsion points) may still be hard — this is the basis for exploring modifications

Participates in

Builds on Supersingular Isogeny Diffie-Hellman

• SSDDH ⇒ KE (via Decisional variant (SSDDH))