Supersingular Isogeny Diffie-Hellman (SIDH) is a quantum robust key-exchange method. It has a similar methodology to the Diffie-Hellman method, but is quantum robust. It was created by Luca de Feo, David Jao and Jerome Plut [2][paper] and enhanced by Craig Costello, Patrick Longa, and Michael Naehrig at Microsoft [3][paper], and has one of the smallest key sizes for quantum robust crypo methods (where the public keys is 751 bytes). In elliptic curve methods the public key is only 32 bytes. It also supports perfect forward secrecy (PFS) and which stops the long-term key from being compromised, on the cracking of a single key (neither NTRU [here] Ring-LWS [here] are setup for PFS). Optimised code has shown the key parameters can be generated with 200 milliseconds, and the code has even been ported to ARM processors. The method is still relatively slow compared with elliptic curve methods (and requires around 50 million cycles of a processor).
SIDH with Rust |
Outline
The following defines the key sizes for the NIST KEM finalists (Kyber, SABER, NTRU, and McEliece) and SIDH/SIKE (Isogeny-based):
Type Public key size (B) Secret key size (B) Ciphertext size (B) ------------------------------------------------------------------------ Kyber512 800 1,632 768 Learning with errors (Lattice) Kyber738 1,184 2,400 1,088 Learning with errors (Lattice) Kyber1024 1,568 3,168 1,568 Learning with errors (Lattice) LightSABER 672 1,568 736 Learning with rounding (Lattice) SABER 992 2,304 1,088 Learning with rounding (Lattice) FireSABER 1,312 3,040 1,472 Learning with rounding (Lattice) McEliece348864 261,120 6,452 128 Code based McEliece460896 524,160 13,568 188 Code based McEliece6688128 1,044,992 13,892 240 Code based McEliece6960119 1,047,319 13,948 226 Code based McEliece8192128 1,357,824 14,120 240 Code based NTRUhps2048509 699 935 699 Lattice NTRUhps2048677 930 1,234 930 Lattice NTRUhps4096821 1,230 1,590 1,230 Lattice SIKEp434 330 44 346 Isogeny SIKEp503 378 56 402 Isogeny SIKEp751 564 80 596 Isogeny SIDH 564 48 596 Isogeny
Theory
If we have two elliptic curves (\(E_1\) and \(E_2\)), we can create a function that maps a point (P) on \(E_1\) to a point Q on \(E_2\). This function is known as an isogeny. If we can map this function, every point on \(E_1\) can be mapped to \(E_2\). Our secret key is then the isogeny, and the public key is the elliptic curve. For key exchange, Bob and Alice mix their isogeny and the other side's curve to generate a secret curve.
With isogeneous elliptic curves we thus do not deal with a single elliptic curve but a family of them [paper]. An isogeny is then a map \(\phi\) : \(E_1\) -> \(E_2\) and where points on the source curve \(E_1\) map to the target curve \(E_2\). It turns out that for every isogeny \(\phi\): \(E_1\) -> \(E_2\), there's a dual isogeny \(\phi\): \(E_2\) -> \(E_1\), so we can say that two curves are isogenous if they're linked by an isogeny.
Let's take an example of Bob and Alice generating the same shared key (as we do with the Diffie-Hellman methods). First Alice has a starting curve of \(E_0\), and four points on that curve: \(P_A\), \(Q_A\), \(P_B\), \(Q_B\).
Alice then select two random values \(m_a\) and \(n_A\) and keeps these secret. These will be scalar values.
She then determines a secret point \(R_a\) which is:
\(R_a = m_a \times P_a + n_a \times Q_a \)
This is her secret isogeny (\(\phi_a\)).
She then transforms \(P_b\) and \(P_q\) with this isogeny, and where Alice evaluates \(\phi_A\) at point \(P_b\), and at \(Q_b\).
She then sends \(E_a\) (her public key), and two transformed points (\(\phi_A(P_b)\) and \(\phi_A(Q_b)\)) to Bob.
Bob does the same, but swaps the a and b values \(P_a\) for \(P_b\), \(Q_a\) for \(Q_b\) and vice versa. He will generate his own random values \(m_b\) and \(n_b\). Bob calculates his secret: (\(\phi_B\)).
The following defines the exchange [1]:
Next, Alice uses \(E_a\), \(\phi_a(P_a)\), \(\phi_b(Q_a)\) to construct an isogeny \(\phi'_a\) using \(m_a \times \phi_a(P_a) + n_a \times \phi_b(q_a)\).
Bob uses \(E_a\), \(\phi_a(P_b)\), \(\phi_a(Q_b)\) to construct an isogeny \(\phi'_b\) using \(m_b \times \phi_a(P_b) + n_b \times \phi_a(Q_b)\).
Now \(\phi'a\) maps to a curve \(E_{ab}\), and \(\phi'_b\) maps to \(E_{ba}\), and we can define them is isomorphic. After this, we can calculate a value from the j-invariant, and where \(j(E_{ab})\) is equal to \(j(E_{ba})\), and this will be the same shared secret between Bob and Alice. For a curve of \(y^2 = x^3 + px + q\), the j-invariant is:
\(j = 1728 \frac{4p^3}{4p^3 + 27q^2}\)
At the end of this, Bob and Alice will have the same key, and they will know that a quantum computer will not be able to crack it, and that no previous keys can be cracked.
Coding
The following is an outline (based on code [here]):
extern crate rand; extern crate sidh; extern crate hex; use sidh::sidh::*; use rand::{thread_rng}; fn main() { let mut rng = thread_rng(); print!("=== SIDH ===\n\n"); let (alice_public, alice_secret) = generate_alice_keypair(&mut rng); print!("Alice Private: {}\n",hex::encode(alice_secret.scalar)); print!(" Alice Private Key Length: {} bytes\n",alice_secret.scalar.len()); print!("Alice Public (64 bytes): {}\n",&hex::encode(alice_public.to_bytes())[0..64]); print!(" Alice Public Key Length: {} bytes\n",alice_public.to_bytes().len()); let (bob_public, bob_secret) = generate_bob_keypair(&mut rng); print!("Bob Private: {}\n",hex::encode(bob_secret.scalar)); print!(" Bob Private Key Length: {} bytes\n",bob_secret.scalar.len()); print!("Bob Public (64 bytes): {}\n",&hex::encode(bob_public.to_bytes())[0..64]); print!(" Bob Public Key Length: {} bytes\n",bob_public.to_bytes().len()); let alice_shared_secret = alice_secret.shared_secret(&bob_public); let bob_shared_secret = bob_secret.shared_secret(&alice_public); print!("Alice Private: {}\n",hex::encode(alice_shared_secret)); print!(" Length: {} bytes\n",hex::encode(alice_shared_secret).len()); print!("Alice Private: {}\n",hex::encode(bob_shared_secret)); print!(" Length: {} bytes\n",hex::encode(bob_shared_secret).len()); }
A sample run is:
=== SIDH === Alice Private: 84598b1eecf90071af612140093d8a9fcb2db953e7403c49f16c66e4ebc03151ed7b6e973b8954b6f43f2366f5a10400 Alice Private Key Length: 48 bytes Alice Public (64 bytes): ad0e4167b95c512aa165b0817f4e6080fb0cdb113cfbd810085278935c8fe65c Alice Public Key Length: 564 bytes Bob Private: 53169f1fb656e89a48efea4b478cd423f643eb6791660e7dcdb603c8c59a75a1008b3589bc78c93d361b2773ffff5c05 Bob Private Key Length: 48 bytes Bob Public (64 bytes): f0536e48f278699751171d67026c26c59f7ff5b78d840aa0e73c8c25cd1170b7 Bob Public Key Length: 564 bytes Alice Private: bac23aa4042fdcc2c9367a32ad454fd7d7ff1634cdb380601368b9f26127d45acd7f37ca220a1272d5fcfbbcc8fd3f2fb2e3cfc93b920e086be791b0514910ae7e3a57921f145160e7aaad18479f60fd0a529c3689945e942a1ba48490544928c81a52fca4fbc76d8262d2506349bf3fd310a65aeae233d393cbf0131b28e55419fbe78f023d1b25306b892e5deae2e59ac98e863a5c59194458fcbccee7002d00d166b43cd5796353d86f2a5275f7f018575e945ce3acdf5fd9625f Length: 376 bytes Alice Private: bac23aa4042fdcc2c9367a32ad454fd7d7ff1634cdb380601368b9f26127d45acd7f37ca220a1272d5fcfbbcc8fd3f2fb2e3cfc93b920e086be791b0514910ae7e3a57921f145160e7aaad18479f60fd0a529c3689945e942a1ba48490544928c81a52fca4fbc76d8262d2506349bf3fd310a65aeae233d393cbf0131b28e55419fbe78f023d1b25306b892e5deae2e59ac98e863a5c59194458fcbccee7002d00d166b43cd5796353d86f2a5275f7f018575e945ce3acdf5fd9625f Length: 376 bytes