Supersingular Isogeny Key Encapsulation (SIKE) [4] is a post-quantum cryptography key encapsulation method for key exchange, and is based on Supersingular Isogeny Diffie-Hellman (SIDH). 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 key is 378 bytes and the private key is 434 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).
SIKE (Supersingular Isogeny Key Encapsulation) for KEM |
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 of the code:
#include stddef.h #include stdio.h #include string.h #include stdlib.h #include stdint.h #include "api.h" #include "tests/test_extras.h" #define SCHEME_NAME "SIKEp503" char *showhex(uint8_t a[], int size) ; char *showhex(uint8_t a[], int size) { char *s = malloc(size * 2 + 1); for (int i = 0; i < size; i++) sprintf(s + i * 2, "%02x", a[i]); return(s); } int main() { unsigned int i; unsigned char sk[CRYPTO_SECRETKEYBYTES] = {0}; unsigned char pk[CRYPTO_PUBLICKEYBYTES] = {0}; unsigned char ct[CRYPTO_CIPHERTEXTBYTES] = {0}; unsigned char ss[CRYPTO_BYTES] = {0}; unsigned char ss_[CRYPTO_BYTES] = {0}; uint8_t key_a[CRYPTO_BYTES]; uint8_t key_b[CRYPTO_BYTES]; int rtn; printf("\n\nTESTING ISOGENY-BASED KEY ENCAPSULATION MECHANISM %s\n", SCHEME_NAME); puts("Hello world"); crypto_kem_keypair(pk, sk); crypto_kem_enc(ct, key_a, pk); crypto_kem_dec(key_b, ct, sk); rtn=memcmp(key_a, key_b, CRYPTO_BYTES); printf("\nPublic key (only showing 1/8 of key): %s\n",showhex(pk,CRYPTO_PUBLICKEYBYTES/8)); printf("Secret key (only showing 1/8 of key): %s\n",showhex(sk,CRYPTO_SECRETKEYBYTES/8)); printf("Cipher text: %s\n",showhex(ct,CRYPTO_CIPHERTEXTBYTES/8)); printf("\nKey (A): %s\n",showhex(key_a,CRYPTO_BYTES)); printf("Key (B): %s\n",showhex(key_b,CRYPTO_BYTES)); if (rtn==0) { printf("Keys are the same");} else printf("Error in the keys!"); }
A sample run is:
SIKE (Supersingular Isogeny Key Encapsulation) for KEM SIKEp503 Public key size: 378 Secret key size: 434 Ciphertext size: 16 Public key (only showing 1/8 of key): 64c209b4c7a10a085e4e70506f09103cc39beae3a41603a452b69b59d4e56ef7d04d9508f7d86f4336236a12bb23eb Secret key (only showing 1/8 of key): 86e22023d7aec17293c6d55d999cdafbf718e59d0b30e60286e22023d7aec17293c6d55d999cdafbf718e59d0b30e602e8b92ccafa7d Cipher text: a6bb0b631f1743c895015a48cfc33ee882bcbe1a915ccd0c166ce04e4a61602aeb8b1c48386acb364ba22f86337bcf64cd82 Key (A): 1f8a0606f64966bfdeaa82d2884e3f2d Key (B): 1f8a0606f64966bfdeaa82d2884e3f2d Keys are the same
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].