NTRU key generation

Question

I've been experimenting with an NTRU open-source C implementation here

I've noticed something (potentionally) strange with a certain set of params: NTRU_EES1087EP2 (defined here).

When generating keys, I seed the DRBG with 64 bytes of entropy (I assume this is enough, as the sample code states that "21 bytes of entropy are needed to instantiate a DRBG with a security strength of 112 bits", and I'm using params for 256-bit security, however if anyone can shed some light onto how this figure is calculated I'd be grateful). However, when I generate the keys - the private key seems to contain long strings of zeros towards the end (see below). Is this normal? It doesn't seem to happen with other parameters.

sample private key... 1718 bytes... concatenated to show the final bytes 156544c00710611967774836b33d4803ce89f7730d29149dfc2bca09fced9739820c831c6eab1e0f3df1d300624037810a3a0d381dd9fba4b2f915a6cf2cb3920f1b18ebe915581429a0722ae2545c2afc521ae6b9dd44b68a5ad411f04279f7880aad0482af693c93eab639fac398c73bd6bfb55aa80854e20598291b591025ace64bd63130abaaeb2d505c54da8d5835d2de210000f1b0006a26300a2013f01a80000a2000200000003060203a23663a2db002d0300060003121bea00a2003f00380200000000250300bd095ba20000870001021b00380101006300bd02ab03391b00cf510005a20000a2513c36adb442000b2dcb00001b6c00003c0912180053099ba20906005100003605a200a2020107001b120c2ed81202090000000900640100da0751bd363601521203381b010002a8010f01541b030101360a0000000006361b36b15a3f38a251000054c11c031c142d00010300000000031e0000540238a2a9010110060000a500db00

Answer 1

The secret key blob consist of 1718 bytes where the first 1500 indicates the corresponding public key. The last 200 ish bytes store the encoded secret key.

The secret key is a trinary polynomial with coefficients -1,0,1. So we only need to store the position of non-zero coefficients. The last couple of hundreds of bytes in the encoded secret key suggest which coefficients of the secret key polynomial are -1 or 1. For NTRU_EES1087EP2 parameter set, there are roughly 240 non-zero coefficients out of a total 1087 coefficients. Storing those positions requires

• privkey_packed_trits_len = (p->N + 4) / 5;

which is (1087+4)/5 = 218 bytes. Due to the method that the key is parsed, there ought to be 0s.

see function: ntru_crypto_ntru_encrypt_key_parse

---

For you other question, "21 bytes of entropy are needed to instantiate a DRBG with a security strength of 112 bits" the bits of entropy required is 1.5 times the bit security strength. i.e. 21 bytes = 168 bits = 112 *1.5 for 256 bites security, you need 48 bytes of entropy.

• min_bytes_of_entropy = (sec_strength_bits + sec_strength_bits/2) / 8;

See function: sha256_hmac_drbg_instantiate

Answer 2

NTRU private polynomial $f$, as described in Section 9.2.1 of IEEE Std. 1363.1, is computed as $f = 1 + p \cdot F \mod q$, where $F$ is a ternary polynomial of degree $N-1$ with a specific number of coefficients equal to -1, 1, and 0, determined by parameter $d_F$ (i.e., $d_F$ coefficients equal to 1, $d_F$ coefficients equal to -1, and the rest are 0's). In particular, for the EES1087EP2 parameter set ($N = 1087, p = 3, q = 2048, d_F = 120$, etc.), polynomial $F$ is of degree 1086 and has 120 coefficients equal to 1, 120 to -1, and the rest (i.e. 847) are 0's.

Knowing that, the answer to your question is a little bit complex and requires analyzing the code of the NTRU implementation you are using. When you ask for the binary representation of private key (see the code here), the NTRU library does not simply give you the private key. It actually produces a binary structure, with a header with some parameters, the public key and finally the private key, so the actual private key is just the final part of the output. Additionally, in some cases it stores the polynomial $F$ as the private key, since $f$ can be efficiently computed from $F$.

Since the polynomial $F$ is simply composed of $\{-1,0,1\}$ coefficients, then it can be represented in a much more compact way. In particular, they are storing 5 different coefficients per byte, as described here, so in your case your polynomial $F$ of 1087 terms fits in approximately 218 bytes. Since 218 bytes are 436 hexadecimals characters, this means that the polynomial $F$ will be represented in 436 hexadecimal characters. And that is exactly when the "strange behaviour" you describe begins, in the last 436 characters of the private key dump, which correspond to the polynomial $F$, that, as you know, have a lot of zeros.