NTRU+ Security Considerations

2.1. Scheme Description

Following Lyubashevsky and Seiler [LS19], NTRU+ operates over the polynomial ring R_q = Z_q[x]/<Phi_{3n}(x)>, where Phi_{3n}(x) = x^n - x^{n/2} + 1 is a cyclotomic trinomial and q denotes the coefficient modulus. For all three NTRU+ parameter sets specified in this document, the coefficient modulus is q = 3457. The use of a cyclotomic trinomial enables efficient polynomial multiplication through the Number Theoretic Transform (NTT). Secret polynomials are sampled according to a centered binomial distribution (CBD), where each coefficient is generated by subtracting one uniformly random bit from another, resulting in values in {-1, 0, 1}.¶

NTRU+ uses three hash functions, denoted by F, G, and H, which are instantiated with SHAKE-256 in [KP26].¶

Throughout this document, equations are written in simplified polynomial notation. The corresponding NTT-domain computations and byte encodings are specified in [KP26].¶

2.2. Parameter Sets

NTRU+ provides three parameter sets: NTRU+768, NTRU+864, and NTRU+1152. Table 1 summarizes the ring parameters and the sizes of the cryptographic material associated with each parameter set, together with the estimated classical security levels obtained using the Lattice Estimator [APS15].¶

In Table 1, n is the polynomial degree, q is the coefficient modulus, pk = public key, sk = private key, ct = ciphertext, and ss = shared secret. Key, ciphertext, and shared-secret sizes are given in bytes. Security levels are given in bits.¶

Table 2 summarizes end-to-end single-core performance measurements of the NTRU+ KEM API. Measurements were taken on an Intel Core i7-8700K CPU @ 3.70GHz on Linux/x86_64 using clang 18.1.3 with -O3. Each benchmark was pinned to a single CPU core and measured for 10 seconds per operation. Values are rounded to the nearest operation per second.¶

Key generation and encapsulation include randomness generation performed by the implementation.¶

3.1. Correctness and Security Properties

Historically, achieving negligible worst-case correctness error has been a significant challenge in NTRU-based public key encryption schemes. In classical NTRU encryption, an adversary may construct ciphertexts of the form c = hr + M by choosing r or M maliciously, making it difficult to achieve negligible worst-case correctness errors for all possible ciphertexts.¶

To address this issue, NTRU+ employs two techniques. First, the polynomial r is deterministically derived through the Fujisaki-Okamoto (FO) transform. Second, the encoded message polynomial M is generated through the SOTP encoding procedure. As a result, an adversary no longer has direct control over the values of r and M appearing in honestly generated ciphertexts.¶

This result builds upon [DHK23] and extends the analysis to the CBD sampling used in NTRU+, where r is generated by the CBD sampling procedure and the SOTP encoding makes the coefficients of M follow the same CBD distribution. Consequently, the worst-case correctness error of NTRU+ is effectively identical to the average-case correctness error over honestly generated ciphertexts.¶

As with other lattice-based KEMs, decapsulation failures may potentially leak information about the private key. However, NTRU+ is designed so that the probability of a decapsulation failure for an honestly generated ciphertext is negligible, rendering such failures irrelevant in practice.¶

The IND-CCA2 security of NTRU+ is based on the hardness of the NTRU and Ring-LWE problems and, in particular, admits a tight security reduction in the random oracle model. The security proof begins with the construction of an underlying NTRU encryption scheme (denoted as GenNTRU in [KP26]), which is OW-CPA secure under the NTRU and Ring-LWE assumptions.¶

The explicit rejection of invalid ciphertexts follows from the \gamma-spreadness property of GenNTRU, while the re-encryption-free FO transform relies on the rigidity properties of both GenNTRU and SOTP.¶

3.2. Rejection Sampling in Key Generation

As described in Section 2.1, key generation repeats the sampling of f and g until both polynomials are invertible in the ring R_q.¶

The probability that a randomly generated small polynomial is invertible in R_q can be heuristically estimated from the full factorization of R_q over F_q. For NTRU+768, NTRU+864, and NTRU+1152, the relevant factor degrees are 2, 3, and 1, respectively, giving approximate per-polynomial invertibility probabilities of about 1.00 for (1 - 3457^{-2})^{768/2}, about 1.00 for (1 - 3457^{-3})^{864/3}, and about 0.72 for (1 - 3457^{-1})^{1152}. Consequently, the probability that both f and g are invertible is approximately 1.00 for NTRU+768 and NTRU+864, and approximately 0.51 for NTRU+1152.¶

As shown in Table 2, key generation in NTRU+ remains computationally efficient in both the optimized C and AVX2 implementations. Even for NTRU+1152, where rejection sampling is more frequent, the expected number of samples for each of f and g remains below 1.5, and the resulting overhead remains small in the measured implementations.¶

The use of rejection sampling implies that the execution time of key generation is not strictly constant and exhibits some variance. However, this timing variation depends only on the randomness used during key generation and does not affect the security of the generated key pair.¶

Polynomial inversion in NTT representation can be efficiently implemented using the hierarchical batch inversion technique of [KCP26], which applies Montgomery's trick to reduce the number of field inversions.¶

3.3. Pairwise Consistency Testing Considerations

The NTRU+ key-generation procedure described above does not include a Pairwise Consistency Test (PCT). Implementations seeking FIPS 140-3 validation may perform a PCT following CMVP guidance by executing an encapsulation and a subsequent decapsulation using a newly generated key pair and verifying that both operations derive the same shared secret. While such a test can reliably detect non-functional key pairs, it provides only limited assurance against malformed or fault-induced keys that continue to operate correctly on honestly generated ciphertexts.¶

We note that NTRU+ may admit a more direct form of Pairwise Consistency Test (PCT) than the encapsulation-decapsulation test described above. In particular, it may be possible to verify certain mathematical consistency relations between the public key pk = h and the private key sk = (f, h^{-1}, F(pk)) by exploiting properties of the SOTP encoding and the CBD-based construction used in NTRU+. Exploring such an approach is beyond the scope of this document. Moreover, incorporating such a PCT would likely require modest modifications to the current key-generation algorithm.¶

3.4. Input Entropy of Keying Material

The encapsulation algorithm internally samples an n-bit random message, from which a 32-byte shared secret is derived. This contrasts with ML-KEM, where the encapsulation process always starts from a fixed 32-byte random value. As a result, NTRU+ uses a larger amount of internal encapsulation randomness.¶

While a 32-byte randomness source is sufficient for currently targeted security levels, the NTRU+ design retains the flexibility to accommodate larger amounts of input entropy should future cryptographic requirements evolve.¶

3.5. Input Validation Checks in Encapsulation and Decapsulation

During encapsulation, an implementation should perform a type check on the public key pk before processing. If this validation fails, encapsulation must not continue. NTRU+ does not require an explicit modulus check on each coefficient of pk during encapsulation. Any modification of the public key results in a mismatch between the value F(pk) stored in the private key and the hash value derived from the modified public key during encapsulation, causing the decapsulation procedure to reject the resulting ciphertext.¶

During decapsulation, an implementation should perform both a ciphertext type check and an explicit modulus check on the received ciphertext. If either validation fails, decapsulation must not continue. In particular, the explicit modulus check is essential because the decapsulation procedure of NTRU+ does not perform a re-encryption and ciphertext equality check as part of the FO transform.¶

The modulus check is particularly important in NTRU+, where the modulus is q = 3457 and each ciphertext coefficient is represented as a 12-bit integer. The gap between the modulus q and the 12-bit representation permits multiple encodings of the same element in the ring R_q. Without an explicit modulus check, this ambiguity can potentially lead to IND-CCA2 attacks.¶

For example, if a ciphertext coefficient is equal to 1, an adversary may replace it with 3458. Both values can be represented as valid 12-bit integers and satisfy 3458 = 1 (mod 3457). As a result, an adversary can construct a ciphertext that is distinct from a target ciphertext at the bit-string level while remaining equivalent modulo q, thereby violating the uniqueness of ciphertext encodings assumed by the security proof.¶

In addition, an implementation should verify that the private key has the expected length and corresponds to the intended parameter set before performing decapsulation. If this validation fails, decapsulation must not continue. Unlike the ciphertext modulus check described above, this private-key validation is primarily intended to detect malformed inputs and implementation errors rather than to enforce a security property of the NTRU+ construction itself.¶

3.6. Explicit Rejection in Decapsulation

Unlike ML-KEM, which returns a pseudorandom shared secret for an invalid ciphertext, NTRU+ provides explicit rejection and returns a decapsulation error. Protocol designers should understand both the benefits and limitations of this design choice.¶

In many authenticated key-exchange protocols, explicit rejection is not strictly necessary. Even if a KEM returns a pseudorandom shared secret for an invalid ciphertext, the resulting key material is typically used to derive symmetric-key encryption keys and MAC keys. Subsequent protocol steps, such as MAC verification or key confirmation, will fail if the two parties derive different shared secrets. As a result, protocols such as TLS, SSH, and IKE can safely operate with either implicit rejection or explicit rejection.¶

However, explicit rejection becomes more useful when a KEM is employed in a public key encryption setting. In such applications, the derived shared secret is often used directly to decrypt a protected payload. If implicit rejection is used, the recipient must first determine whether the derived key is valid before attempting decryption. This typically requires an additional integrity check, such as an authenticated-encryption tag or a MAC. By contrast, explicit rejection allows the recipient to terminate processing immediately upon detection of an invalid ciphertext.¶

A similar consideration arises when a KEM is used as an authentication mechanism. In a typical KEM-based authentication protocol, the verifier sends a ciphertext and the prover responds with an additional protocol message, such as a MAC, to demonstrate possession of the correct shared secret. When implicit rejection is used, decapsulation always produces a candidate shared secret, and therefore the verifier must rely on the subsequent protocol message to determine whether decapsulation succeeded. In contrast, with explicit rejection, invalid ciphertexts are detected and rejected during decapsulation itself, allowing the protocol to terminate immediately upon failure and simplifying the protocol logic.¶

Therefore, explicit rejection does not generally provide a significant advantage in authenticated key-exchange protocols that already incorporate key confirmation, authenticated encryption, or equivalent integrity checks. Nevertheless, it can simplify protocol design in public key encryption and KEM-based authentication settings by allowing invalid ciphertexts to be detected directly during decapsulation, rather than requiring validation through subsequent use of the derived key.¶

3.7. Side-Channel Leakage in Hash Computation

The following discussion is intended to illustrate a potential attack strategy and does not constitute a complete attack analysis. For a target ciphertext c = hr + M, let r and M denote the randomness polynomial and encoded message polynomial recovered during decapsulation. Leakage from the computation of G(r) may reveal information about M. This observation is similar in spirit to the side-channel attack of [UXT21], which exploits leakage during the hash computation performed as part of KEM decapsulation.¶

One possible attack proceeds as follows. Let c be a target ciphertext and let c_i denote one of its coefficients. The adversary guesses that the corresponding encoded-message coefficient M_i is zero and constructs a modified ciphertext c' by adding 1 to c_i. The modified ciphertext is then submitted to a decapsulation device holding the unknown private key sk, while the adversary observes side-channel information associated with the computation of G(r).¶

If the adversary can determine that the same polynomial r is hashed during the decapsulation of both c and c', then information about M_i is obtained. In particular, when M_i=0, the modification causes the recovered encoded message polynomial to change from M to M', while the relation c' - M' = c - M continues to hold with high probability. Consequently, (c' - M') h^{-1} = r, and the same polynomial r is supplied to the hash function. Detecting this event through side-channel observations allows the adversary to distinguish whether M_i=0, thereby revealing information about the decrypted message.¶

Implementations should ensure that the computation of G(r) is performed in constant time and does not reveal information about its input through timing, power consumption, cache access, or other side channels.¶

One important distinction between the side-channel attack of [UXT21] and the attack described above is that the former may lead to recovery of private-key information, whereas the latter is limited to leakage of information about the decrypted message. As a result, the latter does not directly threaten the long-term secrecy of the private key. Nevertheless, both attacks demonstrate the need for side-channel-resistant implementations of the hash computation performed during decapsulation.¶