SABER (Lattice - Learning With Rounding) - Key Encapsulation Mechanism (KEM)[Lattice Home][Home]
SABER is a finalist for Public-Key Encryption/KEMs for Post Quantum Cryptography (PQC). It uses Learning with Rounding (LWR), and which is based on learning with errors (LWE) where random errors are replaced with deterministic rounding. It was created by Banerjee, Peikert and Rosen [1] at EUROCRYPT 2012 and is seen to be Indistinguishability under chosen-plaintext attack (IND-CPA). In this case the public key size is 672 bytes and the private key size is 1,568 bytes. Overall a KEM allows a symmetric key to be passed using public key methods [2]. 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. LightSABER has a security level of AES-128, SABER maps to AES-192, and FireSABER to AES-256. [article]
[Kyber KEM]
[SABER KEM]
[NTRU KEM]
[McEliece KEM]
|
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 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.
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 [3]:
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:
#include stddef.h #include stdio.h #include string.h #include stdlib.h #include stdint.h #include "kem.h" #include "randombytes.h" #include "SABER_params.h" #define CRYPTO_PUBLICKEYBYTES SABER_PUBLICKEYBYTES #define CRYPTO_SECRETKEYBYTES (SABER_SECRETKEYBYTES) #define CRYPTO_CIPHERTEXTBYTES SABER_BYTES_CCA_DEC #define CRYPTO_BYTES SABER_KEYBYTES 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(void) { uint8_t pk[CRYPTO_PUBLICKEYBYTES]; uint8_t sk[CRYPTO_SECRETKEYBYTES]; uint8_t ct[CRYPTO_CIPHERTEXTBYTES]; uint8_t key_a[CRYPTO_BYTES]; uint8_t key_b[CRYPTO_BYTES]; int rtn; printf("SABER"); printf("\nPublic key size: %d\nSecret key size: %d\nCiphertext size: %d\n",CRYPTO_PUBLICKEYBYTES,CRYPTO_SECRETKEYBYTES,CRYPTO_BYTES); //Alice generates a public key crypto_kem_keypair(pk, sk); //Bob derives a secret key and creates a response crypto_kem_enc(ct, key_b, pk); //Alice uses Bobs response to get her shared key crypto_kem_dec(key_a, ct, sk); printf("\nPublic key (only showing 1/8 of key): %s\n",showhex(pk,CRYPTO_PUBLICKEYBYTES/8)); printf("Secret key (only showing 1/8 of key): %s\n",showhex(sk,CRYPTO_SECRETKEYBYTES/8)); 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)); rtn=memcmp(key_a, key_b, CRYPTO_BYTES); if (rtn==0) { printf("Keys are the same");} else printf("Error in the keys!"); return 0; }
A sample run of SABER shows that the public key size is 672 bytes, the secret key is 1,568 bytes, and the ciphertext size is 32 bytes:
SABER Public key size: 672 Secret key size: 1568 Ciphertext size: 32 Public key (only showing 1/8 of key): 5998968e0ddae8c0c910b7625e3960ad74ac56585083934963c8934bff920076e1b73ff7acb02fe904fe5fbe463c7691f0d2ee069a3d090a933d4d44adbbb5e8e09d3bcbc4637f71289e8ef9d92a5b73643139fc Secret key (only showing 1/8 of key): 022000008000d0ff0140ffffff032000fc7fffffff0100000000ff3f0004000120000440ffffff024000000000f0ff030000f0ffff3f000400000000feff001000ff3f000080ff0f000040ff070000c0ff0300ff3f00fe7fffffffff3f000880001000febfff17000220000800014000feffff0f00012000fc7f000000fabfff0f00022000f47f00d0fffd7f00100001e0fff7ff00000000c0ff1f000140000400001000fabf000800006000f47f01f0fffd3f00f8fffe1f00fc7f00000004c000000002 Cipher text: 8b7a3eb9a2358fddbd1364bd3472c3dd8952debbdb6a94329e468769fae9e7dfa2be550e64628b8225f2b390e7d559fd9539347f752371724276fbb59b2ed1458655aee46362166b5057f28455b54f0e01ac59c184c6b7a8bfb1bec3 Key (A): c0164eb4ffa98abf2e927e6d47a14b2fc10bc8bb5a2e22271a0bb3213b967e79 Key (B): c0164eb4ffa98abf2e927e6d47a14b2fc10bc8bb5a2e22271a0bb3213b967e79 Keys are the same Keys are the same
In order to build the methods for LightSABER, SABER and FireSABER, we modify "#define SABER_L 3" to define 2 (LightSABER), 3 (SABER) or 4 (FireSABER) in saber_parameters.h:
#ifndef PARAMS_H #define PARAMS_H /* Change this for different security strengths */ // #define SABER_L 2 /* LightSaber */ #define SABER_L 3 /* Saber */ // #define SABER_L 4 /* FireSaber */ /* Don't change anything below this line */ #if SABER_L == 2 #define SABER_MU 10 #define SABER_ET 3 #elif SABER_L == 3 #define SABER_MU 8 #define SABER_ET 4 #elif SABER_L == 4 #define SABER_MU 6 #define SABER_ET 6 #endif #define SABER_EQ 13 #define SABER_EP 10 #define SABER_N 256 #define SABER_SEEDBYTES 32 #define SABER_NOISE_SEEDBYTES 32 #define SABER_KEYBYTES 32 #define SABER_HASHBYTES 32 #define SABER_POLYCOINBYTES (SABER_MU * SABER_N / 8) #define SABER_POLYBYTES (SABER_EQ * SABER_N / 8) #define SABER_POLYVECBYTES (SABER_L * SABER_POLYBYTES) #define SABER_POLYCOMPRESSEDBYTES (SABER_EP * SABER_N / 8) #define SABER_POLYVECCOMPRESSEDBYTES (SABER_L * SABER_POLYCOMPRESSEDBYTES) #define SABER_SCALEBYTES_KEM (SABER_ET * SABER_N / 8) #define SABER_INDCPA_PUBLICKEYBYTES (SABER_POLYVECCOMPRESSEDBYTES + SABER_SEEDBYTES) #define SABER_INDCPA_SECRETKEYBYTES (SABER_POLYVECBYTES) #define SABER_PUBLICKEYBYTES (SABER_INDCPA_PUBLICKEYBYTES) #define SABER_SECRETKEYBYTES (SABER_INDCPA_SECRETKEYBYTES + SABER_INDCPA_PUBLICKEYBYTES + SABER_HASHBYTES + SABER_KEYBYTES) #define SABER_BYTES_CCA_DEC (SABER_POLYVECCOMPRESSEDBYTES + SABER_SCALEBYTES_KEM) #endif
References
[1] Banerjee, A., Peikert, C., & Rosen, A. (2012, April). Pseudorandom functions and lattices. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 719-737). Springer, Berlin, Heidelberg. [paper]
[2] D’Anvers, J. P., Karmakar, A., Roy, S. S., & Vercauteren, F. (2018, May). Saber: Module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM. In International Conference on Cryptology in Africa (pp. 282-305). Springer, Cham. [paper]
[3] Chen, M. S., & Chou, T. Classic McEliece on the ARM Cortex-M4 [here].