Supersingular Isogeny Diffie–Hellman (SIDH) key exchange

Supersingular Isogeny Diffie–Hellman (SIDH) key exchange

When Bob and Alice Went For A Walk (But not together!)

Let’s send Bob and Alice out for a walk — separately (as they may be self isolating). Let’s start them at the same place, and let each of them take a random walk, and share their locations. Then let them take the same random walk, and they should end up together in the same place — and no-one will be able to know where they are!

The next decade will bring a complete change, and where we see RSA leave the stage, and where there will be severe warnings on the robustness of ECC (Elliptic Curve Cryptography). The new implementations of tunnelling methods will see a rise in the quantum robust techniques, and these will give us alternatives to ECC, while highlighting that we need to have a migration path.

And so we are in a phase of coming up with new puzzles which will allow us to sustain our public key encryption methods, and which will not be easily broken by quantum computers. One of the methods proposed for key exchange is Supersingular isogeny Diffie–Hellman key exchange (SIDH). So let’s try and explain its basic operation, in a simple way.

How do elliptic curves work in public key crypto?

First, let’s talk about elliptic curves. These have the form of:

y² = x³ + ax +b

and where a and b are characteristics of the curve. With this we might have an elliptic curve of:

y² = x³ + x

In public key cryptography, we constrain this within a finite field using a prime number (p). Our equation then becomes:

y² = x³ + x (mod p)

and where we will only get values for x and y within 0 and p-1. If we select x=1, and p=97, we get our first point at y=83:

83² = 1 + 1 (mod 97)

This because 83² (mod 97) = 2. There is then no solution if we try x=2, x=3, and x=4. The next point is at x=5:

79² = 5³+ 5 (mod 97) = 130 (mod 97) = 33 (mod 97)

As 79² (mod 97) = 33.

What’s an isogeny?

An isogeny (“equal origin”) provides a mapping from one elliptic curve to another. In this way we transform from one curve into another. For example, y²=x³+x maps to y²=x³−4x with the mapping:

The code is [here]:

A sample run [here]:

Finite field: 97

y^2 = x^3 + x (mod 97)		y^2 = x^3 - 4x (mod 97)
(1 83)				    (2 0)	Check (2 0)
(5 79)				    (44 91)	Check (44 6)
(8 61)				    (93 7)	Check (93 7)
(11 88)				    (64 52)	Check (64 52)
(12 73)				    (4 57)	Check (4 57)
(19 66)				    (65 7)	Check (65 90)
(20 39)				    (54 37)	Check (54 60)
(22 0)				    (0 0)	Check (0 0)
(23 68)				    (61 57)	Check (61 40)
(25 79)				    (91 83)	Check (91 14)
(30 89)				    (85 39)	Check (85 39)

The check is correct in this case, as (44,91) is the same as (44,6) as we are using (mod 97). This is because we generate two points for every x value (y and -y).

So what is Supersingular isogeny Diffie–Hellman key exchange?

One application area of isogenies is the post-quantum cryptography method of Supersingular isogeny Diffie–Hellman key exchange (SIDH) and which uses these isogenies to create a shared secret key between Bob and Alice. Basically Bob and Alice start off with the same curve (E0), and then they randomly walk away from the curves. This creates EA (Alice’s curve) and EB (Bob’s curve). Bob sends Alice his curve, and Alice sends Bob hers. Alice then starts the random again from EB, and repeats her random walk. Bob starts his walk from EA and repeats his random walk, and then eventually meet at a new secret curve (ES). This will be a curve which is only known to them, and they can use this to create a new key, as no-one else will know this curve, unless they know both Bob and Alice’s random walk.

Rather than use elliptic curves, let’s just prove this will a simple linear equation. Let’s say that Bob and Alice start with:

y = 4x + 3

Bob now takes a walk of (x+2), and will end up with:

yB = 4 (x+2) + 3 = 4x + 11

Alice now takes a walk of (x-3) and will send up with:

yA = 4 (x-3) + 3 = 4x-9

Bob gets yA, and takes the same walk (x+2) and gets:

kB = 4 (x+2) — 9 = 4x -1

And Alice get yB, and and takes the same walk (x-3) and gets:

kA = 4 (x-3) + 11 = 4x -1

and thus Bob and Alice have the same linear equation, and if they take a value of x, they will end up with the same key.

Conclusions

I hope you understand the basics of this. In practice it is much more complex, and here’s the method in a bit more detail: