Supersingular elliptic curve isogeny Diffie-Hellman 101(lvh.io)
lvh.io
Supersingular elliptic curve isogeny Diffie-Hellman 101
https://www.lvh.io/posts/supersingular-isogeny-diffie-hellman-101.html
10 comments
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:
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!
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!
> That random point defines Alice's secret isogeny through the isogeny formulas I talked about above.
I don't think the author actually described how a point defines an isogeny...
I don't think the author actually described how a point defines an isogeny...
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.
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.
[deleted]
Awesome overview! Incidentally, Craig Costello is giving a talk at Radboud University today about the paper (4 May 15:30, room HG00.062).
Thank you. I took a introductory course on elliptic curve crypto two years ago at university and this was almost entirely comprehensible.
In case everyone isn't familiar... This is theorized to be resilient against quantum computing
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