2
$\begingroup$

In SIDH both parties agree on the key in following way:

  1. Alice calculates a kernel $R = mPB + nQB$
  2. Thanks to Velu formulas (and further improvements), she can now compute isogeny $\phi_a$
  3. She uses $\phi_a$ to start hers random walk and ends up with trio $(E_a, \phi_a(PB),\phi_a(PB))$
  4. Now she sends this trio to Bob (I know, she actually sends 3 points)
  5. Bob does the same, let say his secret isogeny is $\phi_b$. Upon receipt of corresponding trio from Bob $(E_b, \phi_b(PA), \phi_b(QA))$ Alice uses $m, n$ to compute new kernel $R' = m*\phi_b(PA) + n*\phi_b(QA)$ and new isogeny
  6. Then she starts from $E_b$ and does the random walk again ending on $E_{ab}$
  7. Bob proceeds mutatis mutandis and ends up on a probably different curve $E_{ba}$, but surely in same isomorphism class as Alice. Thanks to j-invariant then can agree on a shared secret $j(E_{ab}) == j(E_{ba})$

Now, I've to say point 6. and 7. are a bit black magic to me. I understand that we have this equality here:

$R' =m*\phi_b(PA) + n*\phi_b(QA) = \phi_b(m*PA + n*QA)$

But still, why exactly they will end up in the same isomorphism class? What is a mathematical base, for those two isogenies to converge to the same class. I'm wondering how would a proof look like for this.

$\endgroup$
  • $\begingroup$ You seem to be confusing "isogeny class" and "isomorphism class". That two isogenous curves are in the same isogeny class is a tautology. Your question is about why E_ab and E_ba are in the same isomorphism class. $\endgroup$ – Luca De Feo Jun 16 at 17:42
  • $\begingroup$ Argh, obviously it should say isomorphism class. Fixed now $\endgroup$ – Henry Dorsett Case Jun 16 at 21:59
4
$\begingroup$

I invented SIDH and can surely answer any technical questions about it. Proofs of $E_{ab} \cong E_{ba}$ are given in several places, though rarely in official Theorem / Proof form, because this result is just an application of well-established theory on elliptic curves rather than any sort of new mathematical result that merits formal statement as a theorem. See for example the original paper (Section 3.2, in particular the (unique) displayed equation in that section), or De Feo's survey article (page 34), or Martindale and Panny's cryptanalysis summary (page 4, paragraph "Key exchange").

If you have a more specific question, please ask away.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.