NIST have defined that CRYSTALS (Cryptographic Suite for Algebraic Lattices) Kyber is a standard for PQC key-encapsulation mechanism (KEM). Overall a KEM allows a symmetric key to be passed using public key methods. In this case, Bob will generate her key pair of a public key (\(pk\)) and a private key (\(sk\)). He then passes his public key to Alice, and then Alice creates a cipher text (\(ct\)) with Bob's public key. He passes the ciphertext to Bob, and who decrypts with his private key. This will reveal the key that Alice wants Bob to use. Kyber512 has a security level of AES-128, Kyber768 maps to AES-192, and Kyber1024 to AES-256. This page will implement Kyber768.
Kyber KEM 768 |
Outline
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 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
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
The code is:
package main import ( "fmt" "github.com/FiloSottile/mlkem768" ) func main() { pubBob, privBob, _ := mlkem768.GenerateKey() c, kAlice, _ := mlkem768.Encapsulate(pubBob) kBob, _ := mlkem768.Decapsulate(privBob, c) fmt.Printf("Bob public (first 32 bytes)\t%x Length\t%d\n", pubBob[:32], len(pubBob)) fmt.Printf("Bob private (first 32 bytes)\t%x Length\t%d\n", privBob[:32], len(privBob)) fmt.Printf("\nKey Bob:\t%x\n", kBob) fmt.Printf("Key Alice:\t%x\n", kAlice) }
A sample run of Kyber768 shows that the public key size is 800 bytes, the secret key is 2,400 bytes, a public key of 1,184 bytes and the ciphertext size is 1,088 bytes:
Bob public (first 32 bytes) e17335eda72fe0b1c2b78c3036e08322e477e69c87e0259a50c3006878635b27 Length 1184 Bob private (first 32 bytes) b387b5c5f4c5ab7ab7d806023d8c01a9302674a59a9f8a504e25654e104b6a96 Length 2400 Alice sends cipher (first 32 bytes) ff336c8e003d6d6160fa5550b9daee762675cb649d2445df6ecbbd77b580c960 Length 1088 Key Bob: 023e99f8e01de06518f91758e7934912b580a0f333b1252a5a0f3501c9a75106 Key Alice: 023e99f8e01de06518f91758e7934912b580a0f333b1252a5a0f3501c9a75106
Reference
[1] Chen, M. S., & Chou, T. Classic McEliece on the ARM Cortex-M4 [here].