Last updated: 2018-03-01
This was originally published on my blog.
In the first part of this series, I discussed some basics of quantum mechanics and how they apply to quantum computing. In this part, I’ll continue that discussion by examining the proposed families of post-quantum functions, beginning with Supersingular Isogeny Diffie-Hellman.
Disclaimer: I wrote this article as a grounding point to learn about supersingular isogenies. I think I mostly failed. Trust this content at your peril.
First, what is post-quantum cryptography? Post-quantum crypto (PQC) is the use of classical methods (as opposed to quantum mechanics) to create functions that will be resistant to known quantum attacks. Quantum cryptography, on the other hand, exploits the principles of quantum mechanics to achieve cryptographic goals. The hope of PQC is that it will be a drop-in replacement to current cryptographic methods. As I mentioned in the previous article, Shor’s Algorithm and Grover’s Algorithm are algorithms designed to run on a quantum computer. With enough qubits, Shor’s Algorithm can be used to break asymmetric encryption schemes, such as RSA. A modified version of Shor’s Algorithm can be used to break elliptic curve cryptography. Grover’s Algorithm cannot break symmetric encryption schemes but does cut down the amount of work necessary to brute force symmetric schemes by half (AES-256 will have the same security guarantees as AES-128 does today). Shor’s and Grover’s algorithms are quantum cryptanalysis, but it is likely possible to mitigate their effects using PQC functions.
Supersingular Isogeny Diffie Hellman
There are several families of PQC functions. The first we will look at is supersingular isogenies, specifically, Supersingular Isogeny Diffie-Hellman (SIDH). I assume that you are familiar with Diffie-Hellman (DH). If you are not, the linked Stack Exchange post is a great concise explanation of how DH works. SIDH mirrors the functionality of DH in a quantum-resistant manner. I am not going to go into detail on elliptic curve cryptography (ECC) now, although I may discuss it in another post at a later date. The article I linked to is an extremely excellent explanation of how elliptic curve cryptography works from Cloudflare. We will need to know a little bit about elliptic curves, however, as SIDH relies on additional properties applied to elliptic curves. In brief, elliptic curves are curves defined over a finite field, represented by the Weierstrass form, y2 = x3 + ax + b, and are non-singular, meaning that there must be a unique tangent line at every point on the curve; the curve does not self-intersect or contain any cusps. Elliptic curves are defined over a finite field K. All elliptic curves have a special point called the point at infinity and a group structure of K-rational points defined over that K-field.
An isogeny is a special type of morphism between elliptic curves. This means that the mapping between curves is surjective - each point on the second curve is mapped to by at least one point on the first curve - and the points on the curves are defined over a finite space, known as the isogeny’s kernel. An isogeny between two elliptic curves is a rational morphism that maps a point at infinity on curve 1 to a point at infinity on curve 2. An isogeny can be uniquely identified by its “kernel” - the subgroup of points on the source curve that map to the point at infinity of a target curve. Isogenies are typically represented as a set of formulas1.
A supersingular elliptic curve is a certain type of elliptic curve with unusually high endomorphism rings of rank 4. This property is important from a mathematical perspective but is not something you need to understand for this article. Furthermore, the use of ‘supersingular’ is unrelated to the non-singularity property of elliptic curves mentioned above. Supersingular elliptic curves are non-singular. ‘Supersingular’ refers to the fact that the j-invariants of the elliptic curves have singular values. For the purposes of this article, you only need to understand that j-invariants are a mathematical function2. This supersingularity property means that every j-invariant for supersingular elliptic curves will equal an algebraic integer. This property of j-invariants is important, as we will see in a moment.
SIDH works with a family of elliptic curves that are supersingular and isogenous - isogenies can be defined between any two curves in the family. SIDH works like this: party A wants to communicate with party B. Each party chooses two curves in the family and each derives a secret value. They select a point on one of their chosen curves and create a kernel mapping to the second curve (Group 1). Through the application of the isogeny formulas that are beyond the scope of this article, inputting their secret value into those functions, each party creates new kernels and new pairs of points (Group 2). These new points are shared between the two parties. A new isogeny is created based on a kernel derived from the shared points (Group 3). Each party runs these Group 3 points through the isogeny formulas as before, again inputting their individual secret values, in order to derive new points and isogenies/kernels (Group 4). Each party computes new coefficients of the new elliptic curves based on the Group 4 isogenies. Finally, each party computes the j-invariant of their latest curve. If the handshake was successful, this j-invariant will be the same for both parties. Similar to the difficulty of determining the prime factors that produced some large number in DH knowing only the large number, given the knowledge of almost all of the information, e.g. the Group 1 and 2 points and the shared Group 3 points, it is very very hard to determine the Group 4 points and thus the j-invariant, thereby securing the communication between the two parties.
Advantages and Disadvantages of SIDH
Now that we have an understanding of the key exchange process using SIDH, let’s look at the advantages and disadvantages of using this PQC function. Most importantly, what is the security guarantee of SIDH? The current research describes the hardness of breaking SIDH, which is the hardness of computing an isogeny between isogenous supersingular elliptic curves, at:
where p is some long number, e.g. a 768-bit number 2 * 2386 * 3242 - 1 for 128-bit security. As we can see, the hardness difference between a classical computer and a quantum computer is very small, thereby successfully mitigating the threat of quantum computing on secure key exchange.
The biggest disadvantage of SIDH is that it is very computationally expensive, especially when compared to other PQC function families, such as lattice-based cryptosystems (which we will discuss in a later article). This makes the function much slower than its alternatives. This penalty is somewhat softened by the fact that SIDH keys are very small.
If you would like more resources to understand SIDH, I found this video lecture useful, as well as this silly metaphor about SIDH using aliens. This article provides a great explanation of the mathematics around SIDH. Cloudflare also has a very good article describing the mechanics of SIDH, as well as an implementation of SIDH in Go. In the next part of this series, we will examine lattice-based cryptography and the RLWE and NTRU PQC functions.
1: These are known as Velu’s formulas. ↩
2: For the curious, all elliptic curves used by SIDH are defined by the following j-invariant: ↩
Top comments (0)