The NTRU (Nth degree TRUncated polynomial ring) public key method is a lattice-based method which is quantum robust. It uses the shortest vector problem in a lattice, and has an underpinning related to the difficulty of factorizing certain polynomials. NTRUhps2048509 has a security level of AES-128, NTRUhps2048677 maps to AES-192, and NTRUhps4096821 to AES-256. [Kyber KEM] [SABER KEM] [NTRU KEM] [McEliece KEM]
NTRU (Nth degree TRUncated polynomial ring) - Key Encapsulation Mechanism (KEM) |
Outline
NTRU is a asymmetric encryption and has been benchmarked as twice as fast as RSA to encrypt, and three times faster to decrypt. It is the public key method which is not based on factorization (RSA) or discrete logs (Elliptic Curve).
The following is taken from Wikipedia and shows the test case [here]:
Bob and Alice agree to share \(N\) (the largest polynomial power), \(p\) and \(q\), and then Bob generates two short polynomials (\(\textbf{f}\) and \(\textbf{g}\)), and generates his key pair from this. These polynomials have the co-efficients of -1, 0 and 1. For example, with \(N=11\), \(p=3\) and \(q=32\). If Bob picks values of:
\(\textbf{f}= [-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1]\)
Then as a polynomial representation:
\(\textbf{f}=-1 + x + x^2 - x^4 + x^6 + x^9 - x^{10}\)
And then picks \(\textbf{g}\):
\(\textbf{g} = -1 + x^2 + x^3 + x^5 - x^8 - x^{10}\)
We then should be able to calculate the inverse of \(\textbf{f}\) for \(\pmod p\) and \( \pmod q\). Thus:
\(\textbf{f} \cdot \textbf{f}_p \pmod p = 1\)
\(\textbf{f} \cdot \textbf{f}_q \pmod q = 1\)
Using an inverse function we get [here]:
\(\textbf{f}_p= [9, 5, 16, 3, 15, 15, 22, 19, 18, 29, 5]\)
\(\textbf{f}_p = 9x^{10} + 5x^9 + 16 x^8 +3 x^7 + 15 x^6 + 15 x^5 + 22 x^4 + 19 x^3 + 18 x^2 + 29x +5\)
The public key then becomes:
\(\textbf{h} = p \cdot \textbf{f}_q . \textbf{f} \pmod q\)
In this case we get:
\(\textbf{f}_q \cdot \textbf{g} = [-5, -9, -1, -2, 11, 12, 13, 3, 22, 15, 16, 29, 60, 19, -2, -7, -36, -40, -50, -18, -30]\)
In order to create a ring, we then divide by \(x^N -1\) and get:
H (Bob's Public Key): [24, 19, 18, 28, 4, 8, 5, 17, 4, 17, 16]
And the private key is \(\textbf{f}\) and \(\textbf{f}_q\).
To encrypt we take Bob's public key (\(h\)), a random polynomial (\(\textbf{r}\)) and a message (\(\textbf{M}\)), and then compute:
\(Enc = \textbf{r} \cdot \textbf{h} + \textbf{M}\)
To decrypt, first we multiply by Bob's private key \(\textbf{f}_q\) and take \(\pmod q\):
\(Dec= (\textbf{r} \cdot \textbf{h} + \textbf{M}) . \textbf{f} \pmod q\)
and which gives:
\(Dec= (p \cdot \textbf{r} \cdot \textbf{f}_q \cdot \textbf{g}+ \textbf{M}) . \textbf{f} \pmod q\)
and since \((\textbf{f}_q . \textbf{f}) \pmod q\) is 1, we get:
\(Dec= (p \cdot \textbf{r} \cdot \textbf{g}+ \textbf{M} \cdot \textbf{f}) \)
Finally we multiply by \(\textbf{f}_p \pmod p\):
\(Dec= (p \cdot \textbf{r} \cdot \textbf{g}+ \textbf{M} \cdot \textbf{f}) . \textbf{f}_p \pmod p\)
This will be:
\(Dec= p \cdot \textbf{r} \cdot \textbf{f} \cdot \textbf{f}_p+ \textbf{M} \cdot \textbf{f} \cdot \textbf{f}_p \pmod p\)
And since we have a multipler of \(p\), we will get a zero value for the first term as we have \(\pmod p\) operation:
\(Dec= 0+ \textbf{M} \cdot \textbf{f} \cdot \textbf{f}_p \pmod p\)
And since \(\textbf{f} \cdot \textbf{f}_p \pmod p\) will be 1, we get:
\(Dec= \textbf{M}\)
Example values of the parameters are:
- Minimal security: \(N=167, p=3, q=128\)
- Good security: \(N=251, p=3, q=128\)
- Strong security: \(N=347, p=3, q=128\)
- Excellent security: \(N=503, p=3, q=256\)
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 [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:
#include stddef.h #include stdio.h #include string.h #include stdlib.h #include stdint.h #include "api.h" #define SCHEME_NAME "NTRU" 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; printf("NTRU 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 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)); if (rtn==0) { printf("Keys are the same");} else printf("Error in the keys!"); }
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:
NTRU for KEM NTRU Public key size: 699 Secret key size: 935 Ciphertext size: 32 Public key (only showing 1/8 of key): d123f462980e8cde575ec807b3f3bf8d8895a26b8c7d7e94a95333f0ccd510155450b25507cad9a4a674518b0bf54cf4fb05b651e2a14b92bdfb141dc6a2d6f361246229360d0133b60a5fd0b651a3bcdacc25a5e50701 Secret key (only showing 1/8 of key): 968f89d2901f6e348a95d21c42432a151329a5575064a573772d2a3b550dbdb6401c602bebe97639c1d5b6969bf1db434943bb867bd323c0c90171d5b0b6d0085db74b337b0d3ac4a2d3a80ca7eccfac9fbedf5c1898333641909dd83206527d0814c37b6a1363ba317b738d4cad63b101b99065 Cipher text: 4cef9f924ae8aad42656f4595f050ee7db27581d31561514af24fc0b23285934da6335a1e0b73a0f9126cac17946d28a082cf49ac105e4c99690fdcae7dbefcdaf6d9456bbf8a352ad28eac6068bc04cec510dac62f449 Key (A): 590eb1263edef82e5d97bcccb534f6756e07db798d87ec181490199506c8e48f Key (B): 590eb1263edef82e5d97bcccb534f6756e07db798d87ec181490199506c8e48f Keys are the same
Presentation
References
[1] Chen, M. S., & Chou, T. Classic McEliece on the ARM Cortex-M4 [here].