Isogeny-based encryption

If and when large quantum computers become practical, all currently widely deployed methods for public key cryptography will break. Even the most optimistic proponents of quantum computing believe such computers are years away, maybe decades. But it also takes years, maybe decades, to develop, test, and deploy new encryption methods, and so researchers are working now to have quantum-resistant encryption methods in place by the time they are needed.

What’s special about isogeny-based encryption?

One class of quantum-resistant encryption methods is isogeny-based encryption. This class stands out for at least a couple methods:

  • it uses the shortest keys, and
  • it uses the most sophisticated math.

Most post-quantum encryption schemes require much longer keys to maintain current levels of protection, two or three orders of magnitude longer. Isogeny-based encryption uses the shortest keys of any proposed post-quantum encryption methods, requiring keys roughly the same size as are currently in use.

The mathematics behind isogeny-based cryptography is deep. Even a high-level description requires quite a bit of background. I’ll take a shot at exploring the prerequisites starting with this blog post.

Elliptic curves

Elliptic curve cryptography is widely used today, and partly for one of the reasons listed above: short keys. To achieve a level of security comparable to 128-bit AES, you need a 256-bit key using elliptic curve cryptography, but a 3072-bit key using RSA.

Quantum computers could solve the elliptic curve discrete logarithm problem efficiently, and so elliptic curve cryptography as currently practiced is not quantum resistant. Isogeny-based encryption is based on elliptic curves, but not as directly as current ECC methods. While current ECC methods perform computations on elliptic curves, isogeny methods are based on networks of functions between elliptic curves.

SIKE

NIST is sponsoring a competition for post-quantum encryption methods, and only one of the contestants is related to elliptic curves, and that’s SIKE. The name stands for Supersingular Isogeny Key Encapsulation. “Supersingular” describes a class of elliptic curves, and SIKE is based on isogenies between these curves.

Future posts

This post raises a lot of questions. First and foremost, what is an isogeny? That’s the next post. And what are “supersingular” elliptic curves? I hope to go over that in a future post. Then after exploring the building blocks, where does encryption come in?

Past posts

I’ve written several related blog posts leading up to this topic from two directions: post-quantum encryption and elliptic curves.

Post-quantum encryption links

Elliptic curve links