Supersingular Isogeny Diffie-Hellman (SIDH) for Post Quantum Computer Key Generation
Supersingular Isogeny Diffie-Hellman (SIDH) for Post Quantum Computer Key Generation
A simpler explanation of isogenies is here.
Introduction
Okay. Strap yourself in, and, it might take a while to fully understand the basic procedure here, but, if you’re interested in a future quantum robust world, it may be worth it. Before we start, you might want to read up on RSA methods here, elliptic curve methods here, and for Diffie-Hellman methods here.
Our public key methods are typically used to sign data/provide identity and for shared key generation. The methods include the Diffie-Hellman method (for key exchange), Elliptic Curve Diffie-Hellman (for key exchange), Elliptic Curve DSA (for signing), and RSA (for signing). The RSA method generates a value of N from the multiplication of two prime numbers (P and Q). Unfortunately quantum computers will be able to factorize N into P and Q, within a reasonable cost. Elliptic Curve methods use elliptic curves where we take a point on an elliptic curve (P) and then generate another point (Q) by using a gradient value (n), and where Q=nP. Again quantum computers will crack this method for a reasonable cost. For Diffie-Hellman, we use discrete logarithms, where we calculate a value of G^x mod p, and where G is a generator value and p is a prime number. Again quantum computers can crack this method with a reasonable cost.
So what’s the alterative? Well Supersingular Isogeny Diffie-Hellman (SIDH) is one of the first to be actually integrated into TLS 1.3, and can provide a direct replacement for key exchange.
Supersingular Isogeny Diffie-Hellman
SIDH is a quantum robust key-exchange method. It has a similar methodology to the Diffie-Hellman method, but is quantum robust. It is based on [2], and an enhanced version was created by Craig Costello, Patrick Longa, and Michael Naehrig at Microsoft [paper][3]. The method has one of the smallest key sizes for quantum robust cryptography methods (where 2,688 bits is equivalent to 128-bit public key security levels). It also supports perfect forward secrecy (PFS) and which stops the long-term key from being compromised, on the cracking of a single key (neither NTRU [here] nor Ring-LWS [here] are setup for PFS). Optimised code has shown the key parameters can be generated with 200 milliseconds, and the code has even been ported to ARM processors.
In the following, Medium does not fully support maths notation , so click here if you want to see the correct notation.
The basics
If we have two elliptic curves (E1 and E2), we can create a function that maps point (P) on E1 to a point Q on E2. This function is known as an isogeny. If we can map this function, every point on E1 can then be mapped to E2. Our secret key is then the isogeny, and the public key is the elliptic curve that we are using. For key exchange, Bob and Alice mix their isogeny and the other side’s curve to generate a secret curve.
With isogeneous elliptic curves we thus do not deal with a single elliptic curve but a family of them [paper]. An isogeny is then a map ϕ : E1 -> E2 and where the points on the source curve E1map to the target curve E2. It turns out that for every isogeny ϕ: E1 -> E2, there’s a dual isogeny ϕ: E2-> E1, so we can say that two curves are isogenous if they’re linked by an isogeny.
So Bob meet Alice
Let’s take an example of Bob and Alice generating the same shared key (as we do with the Diffie-Hellman methods). First Alice has a starting curve of E0, and four points on that curve: PA, QA, PB, QB.
Alice then select two random values ma and na and keeps these secret. These will be scalar values.
She then determines a secret point Ra which is:
Ra=ma×Pa +na×Qa
This is her secret isogeny (ϕa).
She then transforms Pb and Pq. Pq with this isogeny, and where Alice evaluates ϕA at point Pb, and at Qb.
She then sends Ea (her public key), and two transformed points (ϕA(Pb) and ϕA(Qb)) to Bob.
Bob does the same, but swaps the a and b values Pa for Pb, Qa for Qb and vice versa. He will generate his own random values mb and nb. Bob calculates his secret: (ϕB).
The following defines the exchange [1]:
Next, Alice uses EB, ϕB(PA), ϕB(QA) to construct an isogeny ϕ′A using:
mA×ϕB(PA)+nA×ϕB(QA)
Bob uses EA, ϕA(PB), ϕA(QB) to construct an isogeny ϕ′B using:
mB×ϕA(PB)+nB×ϕA(QB)
Now ϕ′A maps to a curve EAB, and ϕ′B maps to EBA, and we can define them is isomorphic. After this, we can calculate a value from the j-invariant, and where j(EAB) is equal to j(EBA), and this will be the same shared secret between Bob and Alice. Here a look here for the calculation of the invariant.
At the end of this, Bob and Alice will have the same key, and they will know that a quantum computer will not be able to crack it, and that no previous keys can be cracked.
The demonstrator of this method is defined here.
Conclusion
Cryptography is fixing many of the problems caused within security, but it can help build a more trusted world. With quantum computers, many of the methods we use for trust will be cracked, and we must migrate to newer, and more robust methods, soon.
References
[1] https://www.academia.edu/32263564/Introduction_to_Supersingular_Isogeny_Diffie-Hellman
[2] De Feo, Luca, David Jao, and Jérôme Plût. “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies.” Journal of Mathematical Cryptology 8.3 (2014): 209–247.
[3] Costello, C., Longa, P., & Naehrig, M. (2016, August). Efficient algorithms for supersingular isogeny Diffie-Hellman. In Annual Cryptology Conference (pp. 572–601). Springer, Berlin, Heidelberg.