All currently deployed Elliptic Curve Cryptography (ECC) ideally requires an attacker to solve an instance of the discrete logarithm problem on an elliptic curve E over a finite field Fp with p elements, where p is a prime number. Concretely, his or her task is to find a secret integer n for which P’ = nP upon input of two points P and P’ on E, where multiplication by n is done through a repeated tangent and chord construction which calls in at the points of E in a seemingly irregular and unpredictable way. When stated in geometric terms, the discrete logarithm problem is about untangling this iteration.
For well-chosen E and p this is believed to be extremely difficult. For example, breaking the widely used Curve25519 using the best attacks available would require more than 2128 bit operations, an astronomical amount which agrees with the current security standards. The main selling point of ECC is that this security level is achieved using very short system parameters. According to most recommendations the key lengths can be taken about twelve times shorter than their counterparts in RSA or in classical discrete logarithm based cryptography; concretely Curve25519 works with keys consisting of about 256 bits, while an equivalent RSA instantiation would need key sizes of 3072 bits long.
However, if our attacker would possess a large enough universal quantum computer equipped with an implementation of Shor’s algorithm, then this analysis would collapse dramatically: in this case he or she would easily break all aforementioned systems, including ECC. While it is not clear whether such a device will indeed be technically realizable one day, miniature versions have proven the principle to work: for instance, a five qubit quantum calculator successfully factored 15 into 5 x 3 using Shor’s method. Therefore the threat is being taken very seriously, the more since the advent of a large-scale quantum computer would make it possible to decrypt all current communication retroactively. Ironically enough, due to its shorter parameters and key lengths ECC is even in bigger danger than RSA: estimates go that 1600 qubits would suffice to break Curve25519, while 6147 qubits are needed to break RSA-3072.
The race toward safe public-key cryptography in post-quantum times is raging, with NIST calling for proposals by November 30th which will be evaluated through a competition of three to five years. Currently, the main candidates for replacing ECC are based on hard problems like finding short vectors in lattices, decoding random linear codes, inverting hash functions, or solving systems of non-linear equations over finite fields. This blog post aims at highlighting another contender which enjoys much attention lately, and uses… elliptic curves! Do not be mistaken: the underlying hard mathematical problem is not the discrete logarithm problem, of course. Rather than discovering a hidden relation between two points P and P’ on a given elliptic curve E, here one’s task is finding a connection between two elliptic curves E and E’ inside a certain large pool.
More precisely, by default each elliptic curve comes equipped with three emanating maps to other elliptic curves, called two-isogenies, which wire together our pool in a seemingly unstructured way. By repeatedly applying a random such map, one ends up with another curve E’, and the attacker’s task is to reconstruct the path that was taken, or at least find a suitable alternative route. The same pool of elliptic curves is also connected by means of three-isogenies, which are another but very similar kind of maps of which four are emerging from each curve. The same problem can be formulated: one produces an elliptic curve E’ by applying a random sequence of three-isogenies starting from E, and again the attacker’s task is to find out how to get from E to E’.
The precise mathematical terminology for our pool is a supersingular isogeny class, consisting of all supersingular elliptic curves over a finite field with p2 elements. Here p is a prime number of a rather specific form, chosen such that all two- and three-isogenies can be described in a convenient way.
For appropriate sizes of p the foregoing problems are believed to be extremely difficult. Even with the help of a large universal quantum computer, that is. This motivated David Jao and Luca De Feo to design a post-quantum key exchange protocol which goes under the name Supersingular Isogeny Diffie-Hellman (SIDH). Concretely the protocol works as follows. Alice and Bob agree on a pool of curves and a starting curve E. Then Alice applies a secret random sequence of two-isogenies, resulting in an elliptic curve EA. Similarly Bob secretly walks a random trail of three-isogenies in order to end up at a curve EB. After exchanging EA and EB publicly, Alice reapplies her sequence of two-isogenies starting from Bob’s curve EB, and Bob does the same starting from Alice’s curve EA. Now here is the magic: as it turns out Alice and Bob eventually end up with the same elliptic curve EAB! This is the common secret, only known by Alice and Bob and ready for use in further communication, for example for creating an AES key.
But wait a minute… how can Alice apply her sequence of maps to Bob’s curve EB, and vice versa? Is it mathematically possible to move a path emanating from E to a different starting point? The answer is yes, but this requires a clever trick which involves appending additional information to EA and EB. We omit the details, but point out that this trick converts breaking SIDH into a rather atypical version of the isogeny-finding problem. On the one hand the appended data potentially provides an attacker with extra tools, even though so far nobody sees how to exploit this. On the other hand it puts further constraints on the isogenies that should be found in order to break the system, making the problem seemingly harder.
So, what about the current status of SIDH in practical terms? The system does not reach top speeds, but is definitely viable. Among its features are the fairly small system parameters, with public keys that can be forced well below 3072 bits. Also, the underlying idea is versatile and can be adopted to build protocols for zero-knowledge proofs of identity, for public key encryption, and for digital signatures. In addition, prior to the introduction of SIDH, supersingular isogeny pools had been used by Denis Charles, Eyal Goren and Kristin Lauter for constructing hash functions.
Being a rather new system though, SIDH did not take a head start in the standardization race for secure post-quantum public-key cryptography, and so far it did not manage to significantly outperform any of the other main candidates. But research is actively ongoing and our assessment of both SIDH and its competitors could change in the near future, both in terms of security and in terms of performance. Since SIDH is based on a very different type of underlying hard mathematical problem, it is a highly valuable alternative to keep at hand.
Thanks to Wouter Castryck for writing this blog post!
