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). In this case we will implement SIKEp434 (128-bit security), SIKEp503 and SIKEp751 (256-bit security).
SIKE (Supersingular Isogeny Key Encapsulation) for KEM |
Outline
For our existing ECC methods, the key sizes are:
Type Public key size (B) Secret key size (B) Ciphertext size (B) ------------------------------------------------------------------------ P256_HKDF_SHA256 65 32 65 P384_HKDF_SHA384 97 48 97 P521_HKDF_SHA512 133 66 133 X25519_HKDF_SHA256 32 32 32 X448_HKDF_SHA512 56 56 56
In this case, we see a 32-byte secret (private) key size for P256, and 64 bytes for the public key (as it has an x- and y-co-ordinate value) and then another byte added to identify the type of point. This gives a 65 byte public key. For X22519, we only require a single co-ordinate value, and thus only need 32 bytes for the public key (and which is the same size as the secret key). The following defines the key sizes for Kyber, SABER, NTRU and McEliece:
Type Public key size (B) Secret key size (B) Ciphertext size (B) ------------------------------------------------------------------------ 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 SIKEp434 330 44 346 SIKEp503 378 56 402 SIKEp751 564 80 596
Note: LightSABER has a security level of AES-128, SABER maps to AES-192, and FireSABER to AES-256. Kyber512 has a security level of AES-128, Kyber738 maps to AES-192, and Keyber1024 to AES-256. NTRUhps2048509 has a security level of AES-128, NTRUhps2048677 maps to AES-192, and NTRUhps4096821 to AES-256.
In terms of performance on an ARM Cortex-M4 (32-bit RISC processor), the following is the number of cycles taken for various operations for key generation, key encapulation and key decapsulation [1]:
scheme (implementation) level key generation encapsulation decapsulation ---------------------------------------------------------------------------- frodokem640aes (m4) 1 48,348,105 47,130 922 46,594,383 kyber512 (m4) 1 463,343 566,744 525,141 kyber768 (m4) 3 763,979 923,856 862,176 lightsaber (m4f) 1 361,687 513,581 498,590 saber (m4f) 3 654,407 862,856 835,122 ntruhps2048509 (m4f) 1 79,658,656 564,411 537,473 ntruhps2048677 (m4f) 3 143,734,184 821,524 815,516 sikep434 (m4) 1 48,264,129 78,911,465 84,276,911 sikep610 (m4) 3 119,480,622 219,632,058 221,029,700 mceliece348864f 1 1,430,811,294 582,199 2,706,681 mceliece348864 1 2,146,932,033 582,199 2,706,681
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:
package main // Based on examples at https://github.com/cloudflare/circl/tree/master/kem/kyber import ( "fmt" "math/rand" "os" "time" "github.com/cloudflare/circl/kem/schemes" ) func main() { meth := "Kyber512" argCount := len(os.Args[1:]) if argCount > 0 { meth = os.Args[1] } scheme := schemes.ByName(meth) rand.Seed(time.Now().Unix()) var seed [48]byte kseed := make([]byte, scheme.SeedSize()) eseed := make([]byte, scheme.EncapsulationSeedSize()) for i := 0; i < 48; i++ { seed[i] = byte(rand.Intn(255)) } pk, sk := scheme.DeriveKeyPair(kseed) ppk, _ := pk.MarshalBinary() psk, _ := sk.MarshalBinary() ct, ss, _ := scheme.EncapsulateDeterministically(pk, eseed) ss2, _ := scheme.Decapsulate(sk, ct) fmt.Printf("Method: %s \n", meth) fmt.Printf("Seed for key exchange: %X\n", seed) fmt.Printf("Public Key (pk) = %X (first 32 bytes)\n", ppk[:32]) fmt.Printf("Private key (sk) = %X (first 32 bytes)\n", psk[:32]) fmt.Printf("Cipher text (ct) = %X (first 32 bytes)\n", ct[:32]) fmt.Printf("\nShared key (Bob):\t%X\n", ss) fmt.Printf("Shared key (Alice):\t%X", ss2) fmt.Printf("\n\nLength of Public Key (pk) = %d bytes \n", len(ppk)) fmt.Printf("Length of Secret Key (pk) = %d bytes\n", len(psk)) fmt.Printf("Length of Cipher text (ct) = %d bytes\n", len(ct)) }
A sample run for SIKEp434 is:
Method: SIKEp434 Seed for key exchange: 5C654D1BABF98CDFEABE56B235EA52FDEC1839DB9FC0AA143B0E7D5235AB8925DB73BE4B125032579F2BEE16F06E1167 Public Key (pk) = C813D012F6A8A8E4873945170EE49010166D5EE1B27CC2EB7BC3E9149B900D44 (first 32 bytes) Private key (sk) = D21D2742521EF908C4BB621F858E49F773D5184554F1CF5DFD1C889FD62763E5 (first 32 bytes) Cipher text (ct) = D2B28A66405C896ACBA843E1E144969055D4F06614E04C5D639BE0EFE28543A7 (first 32 bytes) Shared key (Bob): 38FEF101B08A344A5AA462D139666ACE Shared key (Alice): 38FEF101B08A344A5AA462D139666ACE Length of Public Key (pk) = 330 bytes Length of Secret Key (pk) = 44 bytes Length of Cipher text (ct) = 346 bytes Keys are the same
A sample run for SIKEp434 is:
Method: SIKEp503 Seed for key exchange: 74A5E508A3187CBE7D005EA27B819D78CEDE8C0FE02FFCACE277CCC17BFB79C4046C3DFD2541BA463A87E2ABD8AEDC2F Public Key (pk) = 7F109D0EFFE2120F808BD8BE935C1438CC0A39D1BCADA650F0C1A564F693429B (first 32 bytes) Private key (sk) = 59A8853A5D2C582863F57554D5AE0EFFF76FFF6E812CBA12E6675738E1D86A2A (first 32 bytes) Cipher text (ct) = F5BDA6BAB3F12CC74D912E8B0B975D04E1763B1902D32F70DE9E1391E1B8CDB9 (first 32 bytes) Shared key (Bob): C1D5E520E4571C5F595FA6D7ED1EDB59CFDF7E26563DDC63 Shared key (Alice): C1D5E520E4571C5F595FA6D7ED1EDB59CFDF7E26563DDC63 Length of Public Key (pk) = 378 bytes Length of Secret Key (pk) = 56 bytes Length of Cipher text (ct) = 402 bytes
A sample run for SIKEp751:
Method: SIKEp751 Seed for key exchange: E7B1B58ED1098C6F1D91ACE00B7FBB4165ADCCBC17129992C42DBC5EAF6B628936701573D6C305DBCFB1259EAB78C6AB Public Key (pk) = C3EC4A47C4DA001F484F6E30F2E479F7F33F470225ECFE0F63C6F914CDA6C652 (first 32 bytes) Private key (sk) = 05A309A4CCF5A77BE8BF9CB76AC8AE31BA3F40813A2616484CDF7424D679E42D (first 32 bytes) Cipher text (ct) = 7C43E5C0D906DA84F626E037099022916ABE481B39ABD01D84B6269642F95328 (first 32 bytes) Shared key (Bob): A81E89A4B679B3CAB207B0E5FE8C65985FC83D3C50144DC8D36A8678C5EDB5E7 Shared key (Alice): A81E89A4B679B3CAB207B0E5FE8C65985FC83D3C50144DC8D36A8678C5EDB5E7 Length of Public Key (pk) = 564 bytes Length of Secret Key (pk) = 80 bytes Length of Cipher text (ct) = 596 bytes
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].