Math Paths to Quantum-Safe Security: Isogeny-Based Cryptography

By Victoria de Quehen, Security Researcher, ISARA Corporation

Published July 27th, 2018

One of the most widely deployed public key cryptographic algorithms is the elliptic curve Diffie-Hellman key exchange (ECDH). This, as well as most currently used protocols, is vulnerable to attacks using quantum computers. Isogeny-based cryptography offers the closest quantum-safe cryptographic primitives to ECDH.

What are the Main Isogeny-based Algorithms?

A large group of researchers and developers working on isogeny-based cryptography united their efforts to put forth a single submission to NIST’s call for submissions: Supersingular Isogeny Key Encapsulation (SIKE) [4]. This is a key encapsulation mechanism (KEM) that is closely related to the quantum-resistant key agreement Supersingular Isogeny Diffie-Hellman (SIDH) introduced by Jao and De Feo [3].

What are the Advantages of Isogeny-Based Cryptography?

1. Small Key Sizes: Isogeny-based algorithms are known for having far smaller key sizes than other quantum-safe protocols. For example, SIKEp751 requires public keys of around 400 bytes to achieve 124-bits of quantum security [4], meanwhile, KYBER768, one of the most promising lattice-based KEM submitted to the NIST competition, requires public keys of over 1000 bytes to achieve 128-bits of quantum security [1].
2. Similar to ECDH: SIDH is inspired by ECDH and it has a similar flow. As we will see, SIDH differs from ECDH by replacing the scalar multiplication by isogenies.
3. Well-Known Hard Problem: These isogeny-based algorithms are based on a problem involving elliptic curves that is considered to be hard, in an area that has been well-studied by both mathematicians and cryptographers. This problem states that given two elliptic curves it is difficult to calculate an isogeny (a special type of function) between them.
4. Completely Different from Other Schemes: Isogeny-based algorithms are sometimes recommended in combination with lattice-based algorithms, as the two different mathematical areas are very far apart. The idea being that if one of the two areas of quantum-safe cryptography becomes vulnerable, the other will still be secure.
5. Well-Understood Parameters: The known attacks against the underlying problem are well understood. This makes it easy to choose parameters that are safe. In fact, recent arguments suggest they are more conservative than necessary!
6. Large Basis of Expertise: As isogeny-based cryptography uses elliptic curves, the expertise of classical cryptographers that are familiar with these concepts can be transferred to this new area.
7. Good Hybrid with ECDH: It is often suggested to combine quantum-safe algorithms with an established classic algorithm. Specifically, for added security, there is a hybrid algorithm that combines SIDH with the heavily scrutinized ECDH. As both use elliptic curves, this can be done efficiently [2].
8. Faster Computers: Although SIDH and SIKE are slower than some other cryptosystems, as computers and circuits get faster this will be less important. Some cryptographers believe isogeny-based cryptography will become dominant since bandwidth, especially for embedded devices, historically grows slower than computing power, making the smaller key size compensate for the slower speed.