CRYSTALS (Cryptographic Suite for Algebraic Lattices) supports two quantum robust mechanisms: Kyber for key-encapsulation mechanism (KEM) and key exchange; and Dilithium for a digital signature algorithm. CRYSTALS-Kyber uses LWE (Learning with Errors) with lattice methods. A new lattice attack was discovered within the period of the assessment [1], but it is hoped that an updated version of Kyber can be produced for the final assessment. NIST have some worried about its side-channel robustness, but is a strong contender for KEM. Overall a KEM allows a symmetric key to be passed using public key methods. In this case, Alice will generate her key pair of a public key (\(pk\)) and a private key (\(sk\)). She then passes her public key to Bob, and then Bob creates a cipher text (\(ct\)) with Alice's public key. He passes the ciphertext to Alice, and who decrypts with her private key. This will reveal the key that Bob wants Alice to use. Kyber512 has a security level of AES-128, Kyber738 maps to AES-192, and Keyber1024 to AES-256. In the case we will use the Cloudflare CIRCL library to implement Kyber [CIRCL].
Kyber, Frodo, SIKE and Hybrid PQC Key Exchange Mechanism (KEM) with CIRCL |
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
Coding
In this example, we will use the Kyber 512 method:
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-X25519" // SIKEp424 SIKEp751 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)) } for i := 0; i < scheme.SeedSize(); i++ { kseed[i] = byte(rand.Intn(255)) } for i := 0; i < scheme.EncapsulationSeedSize(); i++ { eseed[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 (sk) = %d bytes\n", len(psk)) fmt.Printf("Length of Cipher text (ct) = %d bytes\n", len(ct)) }
A sample run is for Kyber512 is:
Method: Kyber512 Seed for key exchange: 061550234D158C5EC95595FE04EF7A25767F2E24CC2BC479D09D86DC9ABCFDE7056A8C266F9EF97ED08541DBD2E1FFA1 Public Key (pk) = 115ACE0E64677CBB7DCFC93C16D3A305F67615A488D711AA56698C5663AB7AC9 (first 32 bytes) Private key (sk) = 6C892B0297A9C7641493F87DAF3533EED61F07F4652066337ED74046DCC71BA0 (first 32 bytes) Cipher text (ct) = EDF24145E43B4F6DC6BF8332F54E02CAB02DBF3B5605DDC90A15C886AD3ED489 (first 32 bytes) Shared key (Bob): 0A6925676F24B22C286F4C81A4224CEC506C9B257D480E02E3B49F44CAA3237F Shared key (Alice): 0A6925676F24B22C286F4C81A4224CEC506C9B257D480E02E3B49F44CAA3237F Length of Public Key (pk) = 800 bytes Length of Secret Key (pk) = 1632 bytes Length of Cipher text (ct) = 768 bytes
and for Kyber738:
Method: Kyber768 Seed for key exchange: 061550234D158C5EC95595FE04EF7A25767F2E24CC2BC479D09D86DC9ABCFDE7056A8C266F9EF97ED08541DBD2E1FFA1 Public Key (pk) = A72C2D9C843EE9F8313ECC7F86D6294D59159D9A879A542E260922ADF999051C (first 32 bytes) Private key (sk) = 07638FB69868F3D320E5862BD96933FEB311B362093C9B5D50170BCED43F1B53 (first 32 bytes) Cipher text (ct) = B52C56B92A4B7CE9E4CB7C5B1B163167A8A1675B2FDEF84A5B67CA15DB694C9F (first 32 bytes) Shared key (Bob): 914CB67FE5C38E73BF74181C0AC50428DEDF7750A98058F7D536708774535B29 Shared key (Alice): 914CB67FE5C38E73BF74181C0AC50428DEDF7750A98058F7D536708774535B29 Length of Public Key (pk) = 1184 bytes Length of Secret Key (pk) = 2400 bytes Length of Cipher text (ct) = 1088 bytes
and for Kyber1024:
Method: Kyber1024 Seed for key exchange: 061550234D158C5EC95595FE04EF7A25767F2E24CC2BC479D09D86DC9ABCFDE7056A8C266F9EF97ED08541DBD2E1FFA1 Public Key (pk) = D22302CBD3399FACC630991FC8F28BDB4354762541527678BCF61F65C241146C (first 32 bytes) Private key (sk) = 07638FB69868F3D320E5862BD96933FEB311B362093C9B5D50170BCED43F1B53 (first 32 bytes) Cipher text (ct) = A6AF29D5F5B80BD130F518BADDD6C8F17545413D860FB3DE451979EBFA5E4E31 (first 32 bytes) Shared key (Bob): B10F7394926AD3B49C5D62D5AEB531D5757538BCC0DA9E550D438F1B61BD7419 Shared key (Alice): B10F7394926AD3B49C5D62D5AEB531D5757538BCC0DA9E550D438F1B61BD7419 Length of Public Key (pk) = 1568 bytes Length of Secret Key (pk) = 3168 bytes Length of Cipher text (ct) = 1568 bytes
For Kyber512-X25519:
Method: Kyber512-X25519 Seed for key exchange: 6A298FEC06D8615B8C5DE0233B529DBAB9672DC01A0CF665C0B541FBD620E4ED2293E0CBEC57151E75F5118651E60EC4 Public Key (pk) = DD950421529058EDF428C5C301DB3614EE8342B6D785E3A54EE356B5FF3F3866 (first 32 bytes) Private key (sk) = 52E63B13393BA7E246CA8708A91D599F8A5666C5D31269A8B102A499CFD3EAA0 (first 32 bytes) Cipher text (ct) = 1CA1D8AFAF43A509DF40A470F951FE27331703C69D02E6EE4C7295E30C65362B (first 32 bytes) Shared key (Bob): 83BC722272F42847DAAF34C94FD079700CD2A1BF9E5ACD05654F2FC62CF26A3A5EE652E4A76B87DCCF1D6C14DC259EF62AA5DA9A1CFB1A73C055FB3ABF223DCB Shared key (Alice): 83BC722272F42847DAAF34C94FD079700CD2A1BF9E5ACD05654F2FC62CF26A3A5EE652E4A76B87DCCF1D6C14DC259EF62AA5DA9A1CFB1A73C055FB3ABF223DCB Length of Public Key (pk) = 832 bytes Length of Secret Key (sk) = 1664 bytes Length of Cipher text (ct) = 800 bytes