McEliece is a post-quantum key exchange mechanism, and a finalist for the NIST PQC competition. This page uses various methods including mceliece348864, mceliece460896, mceliece6688128, mceliece6960119 and mceliece8192128. In McEliece methods, we have three main parameters: \(m\), \(n\) and \(t\). With mceliece348864, we have a Level 1 security level with a public key size of 261,120 bytes, a private key size of 6,492 bytes, and a cipher text size of 128 bytes. mceliece460896 has a Level 3 security level with a public key size of 524,160 bytes, a private key size of 13,608 bytes, and a cipher text size of 188 bytes. mceliece460896 has a Level 5 security level with a public key size of 1,0454,992 bytes, a private key size of 13,932 bytes, and a cipher text size of 240 bytes. [Kyber KEM] [SABER KEM] [NTRU KEM] [McEliece KEM]
McEliece - Key Encapsulation Mechanism (KEM) |
Outline
The following is the derived key size and cipher text (in bytes) of each of the core methods [1]:
m n t level | public key secret key ciphertext -------------------------------------------------------------------------- mceliece348864 12 3,488 64 1 | 261,120 6,492 128 mceliece460896 13 4,608 94 3 | 524,160 13,608 188 mceliece6688128 13 6,688 128 5 | 1,044,992 13,932 240 mceliece6960119 13 6,960 119 5 | 1,047,319 13,948 226 mceliece8192128 13 8,192 128 5 | 1,357,824 14,120 240
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
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.
With McEliece348864 KEM, we have parameters of \(m = 12\), \(n = 3488\), and \(t = 64\). The field polynomials are: \(f(z) = z^{12} + z^3 + 1\) and \(F (y) = y^{64} + y^3 + y + z\). With McEliece460896 KEM, we set \(m = 13\), \(n = 4608\), and \(t = 96\), and the field polynomials are: \(f(z) = z^{13} + z^4 + z^3 + z + 1\) and \(F (y) = y^{96} + y^{10} + y^9 + y^6 + 1\). 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
We can see that McEliece has the slowest key generation speed, but is one of the fastest for encapsulation, and is faster than SIKE for decapsulation. Generally, though, Kyber and SABER have the best all round tests.
The following is the code:
#include stddef.h #include stdio.h #include string.h #include stdlib.h #include stdint.h #include time.h #include "api.h" #include "crypto_kem.h" #define SCHEME_NAME "McEliece" 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; srand ((unsigned int) time (NULL)); printf("McEliece for KEM %s\n", SCHEME_NAME); printf("\nPublic key size: %d\nSecret key size: %d\nCiphertext size: %d\n",CRYPTO_PUBLICKEYBYTES,CRYPTO_SECRETKEYBYTES,CRYPTO_BYTES); 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 64 bytes of key): %s\n",showhex(pk,128)); printf("Secret key (only showing bytes of key): %s\n",showhex(sk,128)); 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!"); }
In the same run, Alice generates a public key and a private key. Bob encrypts a shared key for her, and she decrypts with her private key:
McEliece for KEM McEliece Public key size: 261120 Secret key size: 6492 Ciphertext size: 32 Public key (only showing 64 bytes of key): d4693cb8e31fded81f6184728df670402cc6790110c76289bb35df06f00704c2e452ced35138b9e4ba8356630ba5d0de55e066d6ec80a05445325a23405157976a0d4678832190c62ee3ff25068fd1f00787a45afa73161014c30160c39fa4ee2142d158b6163eb9119f44f1e5ecc6f25a9f564e59642f6b04e4df31f8c444e5 Secret key (only showing bytes of key): 530f8afbc74536b9a963b4f1c4cb738bcea7403d4d606b6e074ec5d3baf39d18ffffffff00000000460fad05350fa8088f0cdf0ed30f6f0d2209c80ae3087905a9085104df0dd70d0600040fa20e04049d0c2c0a7c094600300ab80ed40e6804880b9d0fa30278022400080e470a4f08d503dc03e804190a8303b300b5053c0e Cipher text: c3fc3c866a4174327f13bdcee9b835f8 Key (A): 4010284a2256ae63c4e0710ca3290efb249934d83630d894f16fa3e2cadca379 Key (B): 4010284a2256ae63c4e0710ca3290efb249934d83630d894f16fa3e2cadca379
Build the project, and then run "./kem":
Reference
[1] Chen, M. S., & Chou, T. Classic McEliece on the ARM Cortex-M4 [here].