Two popular PQC key exchange methods are SIKE and Kyber. In order to improve the performance of PQC key exchange, we can create a hybrid model and use X25519 and X488. In this case we will use Kyber512-X25519, Kyber768-X448 and Kyber1024-X448, and which uses X25519 and X448 key exchange methods. The key size for this change a little, and where Kyber512 produces an 800 byte public key, and with 832 bytes for Kyber512-X25519.
Kyber, SIKE and Hybrid PQC Key Exchange |
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
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-X25519" // Kyber768-X448 Kyber1024-X448 argCount := len(os.Args[1:]) if argCount > 0 { meth = os.Args[1] } scheme := schemes.ByName(meth) rand.Seed(time.Now().Unix()) pk, sk, _ := scheme.GenerateKeyPair() ppk, _ := pk.MarshalBinary() psk, _ := sk.MarshalBinary() ct, ss, _ := scheme.Encapsulate(pk) ss2, _ := scheme.Decapsulate(sk, ct) fmt.Printf("Method: %s \n", meth) 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 for Kyber512-X25519 is:
Method: Kyber512-X25519 Public Key (pk) = 0D584135D3242392B5E6EC06B3990CEEC43CB3A35875F3CDECC53FEADA33E047 (first 32 bytes) Private key (sk) = 7B558F88CA046A7C1A83431ACAD94629B4A72E8BBEFFF40AD1A7024A2A6DC8A5 (first 32 bytes) Cipher text (ct) = 170F2B8C341B603A38520E16404C3D507ACB5A45BC582F4CCA1AD807196D071B (first 32 bytes) Shared key (Bob): 82B7AECBC7A5C381C712FBA258A38984DA32B9D2B39B2D118B7978371402CD9E413574B7684518ECC484D4DFDCFA0EBFE377FEF3AB982F60F47AD666C56EC196 Shared key (Alice): 82B7AECBC7A5C381C712FBA258A38984DA32B9D2B39B2D118B7978371402CD9E413574B7684518ECC484D4DFDCFA0EBFE377FEF3AB982F60F47AD666C56EC196 Length of Public Key (pk) = 832 bytes Length of Secret Key (sk) = 1664 bytes Length of Cipher text (ct) = 800 bytes
A sample run for Kyber768-X448 is:
Method: Kyber768-X448 Public Key (pk) = 0F3BC5031BB49ED1184E378C39E8BB1696442290329B716A97E79FF100B73599 (first 32 bytes) Private key (sk) = 7B86917D307381BC146125709BD2A39EF6623F8A05F264416E26660F04CA4D20 (first 32 bytes) Cipher text (ct) = 6575C5E916830D96D36C204307284AF89587BEFFC3F579EFEBE352198709FCE5 (first 32 bytes) Shared key (Bob): 5FC20E38B2267E042BCB36319732E2BD5C2D57A9C78D4955FB9423D3D982CA5A1FF791AD7707E18942505334C02FB36F30BD55ED660A781B1101B0CF205C30D767D8718E752107C3B82145330DC0B5817B5788F4A25FC4FB51BF71477B03346A Shared key (Alice): 5FC20E38B2267E042BCB36319732E2BD5C2D57A9C78D4955FB9423D3D982CA5A1FF791AD7707E18942505334C02FB36F30BD55ED660A781B1101B0CF205C30D767D8718E752107C3B82145330DC0B5817B5788F4A25FC4FB51BF71477B03346A Length of Public Key (pk) = 1240 bytes Length of Secret Key (sk) = 2456 bytes Length of Cipher text (ct) = 1144 bytes
A sample run for Kyber1024-X448:
Method: Kyber1024-X448 Public Key (pk) = ACDC644291611A014B41408A16D52479B513FBE15906B259660BB0579B1D9508 (first 32 bytes) Private key (sk) = 690133C140927B6212D539458DB18DC0F28B7CEB549BF32C2FB03229A109C705 (first 32 bytes) Cipher text (ct) = 488232A8878C312FE5988DD19EA04CBC892F25036569423E83061CAEF2C32FC7 (first 32 bytes) Shared key (Bob): FFE3DA3744D79EEBAC20C6224B9EAE6B9622F5B8202C4227A7500984DC0943842A1EE9A775E5CD699CAE5A3134925F666F0F1C78B9B3237F4EFA50EE7632F47485A9D402238AAB802E1100A1DD037EEBC781889E335328D25E536B04528D343A Shared key (Alice): FFE3DA3744D79EEBAC20C6224B9EAE6B9622F5B8202C4227A7500984DC0943842A1EE9A775E5CD699CAE5A3134925F666F0F1C78B9B3237F4EFA50EE7632F47485A9D402238AAB802E1100A1DD037EEBC781889E335328D25E536B04528D343A Length of Public Key (pk) = 1624 bytes Length of Secret Key (sk) = 3224 bytes Length of Cipher text (ct) = 1624 bytes