It's not clear from the title but what makes the described cryptosystem special is that it is considered to remain secure even if the attacker has access to a large quantum computer.
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].
If you already sort of grok ECDH, here's a quick cheat sheet:
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[]
}
The isogeny's codomain curve is not necessarily the same as the curve on which Ra was computed --- in fact, here, it's arranged so that it never is.
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.
As far as I can find out you do it by forcing the point you find to be in the kernel of the isogeny, apparently this is enough information to construct the codomain.
So basically if you've constructed point R you then simply require:
phi(P + R) = phi(P)
and see what kind of space you end up with. Apparently it'll still be an elliptic curve.
Yep! In this case, I think you end up constructing, slightly more specifically, the isogeny whose kernel is exactly the cyclic subgroup generated by the point R (i.e., phi(S) is 0 iff S is a power of R). There are explicit formulas ("Vélu's formulas") that let you compute an isogeny from its kernel. Looks like the paper goes into some depth about how to do that computation efficiently, and how to ensure that you choose a cryptographically suitable point R.
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