Applications of Research

Elliptic curves started as a question about solving cubic equations, and they now protect most of the internet's traffic, sit at the heart of the proof of Fermat's Last Theorem, and even appear in string theory. This page is a tour of where they show up. For the basics, see Background & Introduction.

Jump to: Cryptography · Isogeny-based cryptography · Beyond cryptography

Cryptography

Over a finite field, the group law makes an elliptic curve a group in which one direction is easy and the other is hard: given a point \(G\) and an integer \(k\), computing \(kG\) takes only about \(\log_2 k\) steps, but given \(G\) and \(kG\), recovering \(k\) (the elliptic curve discrete logarithm problem) is believed to be infeasible on well-chosen curves. Because of this, a 256-bit elliptic curve key gives about the same security as a 3072-bit RSA key, which is why elliptic curves are now the default in most of the cryptography people use every day. The methods themselves, with worked examples, are on my Encryption Methods page from the Secure Messenger project; here are three stories of elliptic curve cryptography in the real world.

End-to-end encryption in WhatsApp

Since April 2016, WhatsApp messages and calls have been end-to-end encrypted by default, using the Signal Protocol, which means billions of people use elliptic curve cryptography every day. When the app is installed, each phone generates several key pairs on the elliptic curve Curve25519:

a long-term identity key;
a medium-term signed prekey, signed by the identity key and replaced periodically;
a batch of one-time prekeys, each used for a single conversation.

Only the public halves are uploaded. To start a conversation, the sender's phone downloads the recipient's public keys and combines several elliptic curve Diffie–Hellman computations into a shared secret, so a secure session can begin even while the recipient is offline. From then on, a new key is derived for every message, so stealing one key does not expose past messages. WhatsApp's servers relay the ciphertext but never hold the keys needed to read it.

When the implementation goes wrong: the PlayStation 3

Sony used the Elliptic Curve Digital Signature Algorithm (ECDSA) to sign PlayStation 3 software, so that consoles would only run code Sony had approved. An ECDSA signature on a message with hash \(z\) is a pair \((r, s)\) with

\[s = k^{-1}(z + r\,d) \bmod n,\]

where \(d\) is the private key and \(k\) must be a fresh random number for every signature. Sony used the same \(k\) every time. Two signatures \(s_1, s_2\) on different messages \(z_1, z_2\) with the same \(k\) give two linear equations in the two unknowns, which anyone can solve:

\[\begin{aligned} k &\equiv \frac{z_1 - z_2}{s_1 - s_2} \pmod{n}, \\[1ex] d &\equiv \frac{s_1 k - z_1}{r} \pmod{n}. \end{aligned}\]

The hacking group fail0verflow announced this at the Chaos Communication Congress in December 2010. The private signing key could be recovered, and because the matching public key was built into the console's bootloader, the flaw could never be patched. The mathematics of elliptic curves was never broken; one missing random number was enough.

A backdoor in a standard: Dual_EC_DRBG

Cryptography depends on unpredictable random numbers. Dual_EC_DRBG was a random number generator built from two fixed points \(P\) and \(Q\) on a standard elliptic curve, published by NIST in 2006. Roughly, it keeps a secret state \(s\), outputs most of the bits of the \(x\)-coordinate of \(sQ\), and updates its state from the \(x\)-coordinate of \(sP\).

In 2007, Dan Shumow and Niels Ferguson pointed out that if anyone knew a secret number \(e\) with \(P = eQ\), then from about 32 bytes of output they could reconstruct \(sQ\), compute \(e \cdot sQ = sP\), learn the generator's next state, and predict everything it would ever produce. Nobody outside knew how \(P\) and \(Q\) had been chosen, and the generator had been championed by the NSA. It is widely believed to contain an NSA backdoor, though that has never been officially confirmed, and NIST withdrew it in 2014. It is a lesson in why the constants in a cryptographic standard should be chosen in a way everyone can verify.

Isogeny-Based Cryptography

A large enough quantum computer would break elliptic curve cryptography: Shor's algorithm solves the discrete logarithm problem efficiently, and it breaks RSA as well. That has driven the search for post-quantum cryptography, and one of the most mathematically striking candidates is built from isogenies, the maps between elliptic curves that my own research on isogeny graphs studies.

The hard problem: finding a path in a graph

Fix a large prime \(p\) and a small prime \(\ell\), such as \(\ell = 2\). The supersingular isogeny graph has:

vertices: the supersingular elliptic curves over \(\mathbb{F}_{p^2}\), up to isomorphism, of which there are about \(p/12\);
edges: the isogenies of degree \(\ell\) between them, so every vertex has exactly \(\ell + 1\) neighbors.

This graph is an excellent expander (in fact a Ramanujan graph): a short random walk from any vertex lands almost anywhere. Taking a walk is easy, but given two curves, finding a path of isogenies between them appears to be hard, even for a quantum computer. That path-finding problem is the foundation of isogeny-based cryptography.

A short history

Hash functions (2009). Charles, Goren, and Lauter turned walks in the isogeny graph into a hash function: the bits of the input choose which edge to follow.
SIDH and SIKE (2011–2022). Jao and De Feo designed a Diffie–Hellman-style key exchange in which Alice and Bob each take a secret walk. Its standardized version, SIKE, reached the fourth round of the U.S. National Institute of Standards and Technology's post-quantum competition.
The break (2022). Castryck and Decru found an attack that recovers SIKE's secret key in about an hour on a single computer core. It exploited extra torsion-point information that the protocol published, analyzed through higher-dimensional abelian varieties: a vivid example of deep theory about elliptic curves and their torsion having immediate real-world consequences.
What survives. Schemes that do not publish that extra information were not affected, including CSIDH, which uses a group action on supersingular curves over \(\mathbb{F}_p\), and SQIsign, a signature scheme with some of the smallest keys and signatures of any post-quantum proposal. Isogeny-based cryptography remains an active area of research.

Beyond Cryptography

Fermat's Last Theorem

Fermat claimed that \(a^n + b^n = c^n\) has no solutions in positive integers for \(n \ge 3\). The proof came through elliptic curves. Frey observed that a solution \(a^p + b^p = c^p\) would produce the curve

\[y^2 = x(x - a^p)(x + b^p),\]

which would be so unusual that it could not be modular; Ribet proved this in 1986. Wiles, with Taylor, then proved in 1995 that semistable elliptic curves over \(\mathbb{Q}\), including any Frey curve, are modular, so no solution can exist.

String theory

Elliptic curves even appear in physics. In F-theory, a framework within string theory, a field of type IIB string theory called the axio-dilaton is interpreted as the shape parameter of an elliptic curve, and the extra dimensions of spacetime are modeled by Calabi–Yau spaces built from families of elliptic curves (elliptic fibrations). The way these curves degenerate, classified by Kodaira, determines the physics of the resulting model.

A million-dollar problem

The Birch and Swinnerton-Dyer conjecture, one of the Clay Mathematics Institute's seven Millennium Prize Problems, predicts that the rank of an elliptic curve can be read off from its \(L\)-function: the rank should equal the order of vanishing of \(L(E, s)\) at \(s = 1\). It is proven only when that order is 0 or 1, and its most basic consequence, the Parity Conjecture, is a key tool in my work on ranks.