Supersingular elliptic curve isogeny Diffie-Hellman 101

For those interested in an approachable high-level view on post quantum crypto DJB and Tanja Lange gave a talk about it at 32C3[1].

[1] https://media.ccc.de/v/32c3-7210-pqchacks

For conventional DH, given prime p and generator g:

Alice generates random secret a, sends public A=g^a%p. Bob does same with b, B. B^a%p == A^b%p, so we've agreed on a secret.

For elliptic curve DH, given prime p, curve E, base BP:

Alice generates random secret a, sends public A=BP.scalarmult(a). Bob does same with b, B. B.scalarmult(a) == A.scalarmult(b), so we've agreed on a secret.

For isogeny DH, given prime p, special curve E, bases (Pa, Qa, Pb, Qb), deep breath:

Alice generates random secret scalars m, n and uses them to scale and combine Pa, Qa into a random secret point Ra. Ra can be used to define an isogeny between special curve E and a new curve, which we'll call phi. Perhaps think of an isogeny as an OOP object:

    class isogeny { 
      new(p point, domain curve) isogeny
      map(p point) point   // map points from domain to codomain 

      codomain curve

    private:
      rational_map tuple[]
    } 

Alice's secret key, the equivalent of her "a" in the conventional DH case, is the tuple [m, n, phi]. Alice's public key is [phi.codomain, phi.map(Pb), phi.map(Qb)]. Notice how Alice has generated an isogeny from Pa, Qa, but then applied it to the unrelated points Pb, Qb. Notice also how she's revealing phi's codomain curve, but not phi itself.

Bob does the same, except swapping the roles for Pa, Qa and Pb, Qb. Alice and Bob exchange public keys.

Now the crazy thing happens: Alice and Bob create new isogenies by combining their secret m, n --- with which they generated their original isogenies --- but using the isogeny-mapped points their counterparty sent instead of the original points they used. We'll call their new isogenies psi.

Their respective psi.codomain curves won't be the same, but they will be isomorphic, and so they'll share a j-invariant --- the j-invariant being sort of like a discriminant that can survive transformation through isogenies. It's just a large number related through a straightforward formula to the coefficients of the generated curves.

The j-invariant is the agreed-upon secret.

At a very high level, the distinction between ECDH and curve isogeny DH is that ECDH works based on curve points, but SIDH works on entire curves.

LVH's blog post does a better job than I could ever hope to at explaining what's special about the curve used in SIDH (interestingly: SIDH relies on a kind of curve that for ECDH would be insecure --- but notice, unlike ECDH, SIDH doesn't depend on the security elliptic curve discrete log problem), and about why the problem of finding an isogeny given its codomain is thought to be quantum-hard.

Probably the most important thing to understand about this is that nobody is going to be using it any time soon. It took CFRG years just to debate whether Curve25519 should be added to the TLS standard curves (spoiler: of course). SIDH is a cryptosystem that randomly generates new curves on the fly and hops back and forth between them. It'll be awhile before we know the contours of the security of isogeny DH, both in a theoretical sense and in terms of how to implement it safely.

But it's neat!

I don't think the author actually described how a point defines an isogeny...