For Post-Quantum, Don’t Dismiss Isogenies … One of the Smallest Key Sizes for PQC
For Post-Quantum, Don’t Dismiss Isogenies … One of the Smallest Key Sizes for PQC
We need to migrate way from ECDH, as it is based on elliptic curves and which can be cracked by quantum computers. And so NIST is now assessing a range of finalists: Kyber, SABER, NTRU and McEliece. The first three are lattice based, and one of these is likely to win the competition. When we look at key sizes we see that McEliece has a relatively large public key, but it is Supersingular Isogeny Diffie-Hellman (SIDH) that has the smallest public and private key:
Type Public key size (B) Secret key size (B) Ciphertext size (B)
--------------------------------------------------------------------
SIDH 564 48 564
Kyber512 800 1,632 768
Kyber738 1,184 2,400 1,088
Kyber1024 1,568 3,168 1,568
LightSABER 672 1,568 736
SABER 992 2,304 1,088
FireSABER 1,312 3,040 1,472
McEliece348864 261,120 6,452 128
McEliece460896 524,160 13,568 188
McEliece6688128 1,044,992 13,892 240
McEliece6960119 1,047,319 13,948 226
McEliece8192128 1,357,824 14,120 240
NTRUhps2048509 699 935 699
NTRUhps2048677 930 1,234 930
NTRUhps4096821 1,230 1,590 1,230
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 crypto methods (where the public keys is 564 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. 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).
Isogenies
If we have two elliptic curves (E1 and E2), we can create a function that maps a point (P) on E1 to a point Q on E2. This function is known as an isogeny. If we can map this function, every point on E1 can be mapped to E2. Our secret key is then the isogeny, and the public key is the elliptic curve. An example of an isogeny is [here]:
Isogeny-based key exchange
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 ϕ: E1 -> E2 and where points on the source curve E1 map to the target curve E2. It turns out that for every isogeny ϕ: E1 -> E2, there’s a dual isogeny ϕ: E2 -> E1, 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 E0, and four points on that curve: PA, QA, PB, QB.
Alice then selects two random values ma and nA and keeps these secret. These will be scalar values. She then determines a secret point Ra which is:
Ra=ma×Pa+na×Qa
This is her secret isogeny (ϕa). She then transforms Pb and Pq with this isogeny, and where Alice evaluates ϕA at point Pb, and at Qb. She then sends Ea (her public key), and two transformed points (ϕA(Pb) and ϕA(Qb)) to Bob.
Bob does the same, but swaps the a and b values Pa for Pb, Qa for Qb and vice versa. He will generate his own random values mb and nb. Bob calculates his secret: (ϕB).
The following defines the exchange [1]:
Next, Alice uses Ea, ϕa(Pa), ϕb(Qa) to construct an isogeny ϕ′a using ma×ϕa(Pa)+na×ϕb(qa). Bob uses Ea, ϕa(Pb), ϕa(Qb) to construct an isogeny ϕ′b using mb×ϕa(Pb)+nb×ϕa(Qb).
Now ϕ′a maps to a curve Eab, and ϕ′b maps to Eba, and we can define them is isomorphic. After this, we can calculate a value from the j-invariant, and where j(Eab) is equal to j(Eba), and this will be the same shared secret between Bob and Alice. For a curve of y2=x3+px+q, the j-invariant is:
j=17284p34p3+27q2
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 of the code in Rust [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 [here]:
=== 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
Conclusions
NIST has defined their finalists for post-quantum key exchange (NTRU, Kyber, SABER and Mcelice), and it is likely that one of the lattice methods will be. But, they have also produced an alternative list, and SIDH has an excellent chance to be the winner of the alternative category. The contender is Supersingular Isogeny Key Encapsulation (SIKE) is based on SIDH. It has such potential that AWS has defined a standard for its integration into TLS 1.2 [here]:
References
[1] Costello, C. (2017). An introduction to supersingular isogeny-based cryptography. ECC. [paper]
[2] Jao, D., & De Feo, L. (2011, November). Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In International Workshop on Post-Quantum Cryptography (pp. 19–34). Springer, Berlin, Heidelberg. [paper]
[3] Costello, C., Longa, P., & Naehrig, M. (2016, August). Efficient algorithms for supersingular isogeny Diffie-Hellman. In Annual International Cryptology Conference (pp. 572–601). Springer, Berlin, Heidelberg. [paper]
[4] Douglas Stebila, Introduction to post-quantum cryptography and learning with errors, Summer School on real-world crypto and privacy, Šibenik, Croatia, June 11, 2018 [slides].