SSDDH ⇒ KE

Standard model · JDF11

Statement

If the SSDDH problem, the decisional variant of SIDH, is hard, the SIDH protocol is a key exchange whose session key is indistinguishable from random in the authenticated-links model of Canetti and Krawczyk — JDF11. Over a supersingular $E/{\mathbb{F}}_{p^2}$ with $p={\ell }_A^{e_A}{\ell }_B^{e_B}f\pm 1$, each party computes a secret isogeny with kernel $⟨[m]P+[n]Q⟩$ for a basis $\{P,Q\}$ of its own ${\ell }^e$-torsion, publishes the image curve together with the images of the other party’s torsion basis, and both derive $j(E_{AB})$.

Sketch

Given ${\varphi }_A(P_B),{\varphi }_A(Q_B)$, Bob computes $E_A/⟨[m_B]{\varphi }_A(P_B)+[n_B]{\varphi }_A(Q_B)⟩$, and Alice symmetrically; both curves are $E/⟨R_A,R_B⟩$ up to isomorphism, where $R_X=[m_X]P_X+[n_X]Q_X$, so the $j$-invariants agree. Distinguishing $j(E_{AB})$ from the $j$-invariant of an independently generated $E_{A^{\prime }{B}^{\prime }}$ given the transcript is SSDDH by definition.

Notes

• SSDDH does not hold: the published torsion-point images make the secret isogeny, hence $E_{AB}$, computable in classical polynomial time — CD22.