NTRU KEM Security Considerations

2.1. Security Goal

For the parameter sets listed above, the NTRU draft identifies IND-CCA2 as the desired security property and lists the intended bit strength for each parameter set ([NTRU-DRAFT]). This document treats IND-CCA2 security as the relevant baseline for protocol use because the calling protocol may need security against active attacks, ciphertext manipulation, or authentication-sensitive composition ([RFC9180], [AUTHKEM]).¶

Representative IETF examples are HPKE, where RFC 9180 requires that the KEM used within HPKE support the protocol's desired security properties and analyzes the KEM in IND-CCA2 terms ([RFC9180]), and KEMTLS / AuthKEM, where the IETF draft for KEM-based authentication in TLS 1.3 discusses handshake security and authentication goals that go beyond an IND-CPA-only KEM assumption ([AUTHKEM]).¶

The parameter sets above target the usual NIST-style strength levels ([NTRU-DRAFT]): ntruhps2048677 and ntruhrss701 target 128-bit security, ntruhps4096821 targets 192-bit security, and ntruhps40961229 and ntruhrss1373 target 256-bit security.¶

2.2. Basis for Confidence

Confidence in NTRU comes from two statements:¶

• The underlying public-key encryption primitive is believed secure against the known attacks for the published parameter sets, based on the public NTRU cryptanalysis and parameter-selection rationale ([NTRU-NIST], [NISTIR8309]).¶
• The SXY transform gives a provable IND-CCA2 KEM construction in the quantum random oracle model under the assumptions stated by Saito, Xagawa, and Yamakawa ([SXY]).¶

The first statement is a primitive-security estimate. For lattice-based schemes, the standard assessment is to analyze the best known lattice attacks, commonly expressed with a core-SVP style cost model. This model reduces the attack cost to a BKZ block size and to the cost of the sieving step used inside lattice reduction ([CORE-SVP], [NTRU-NIST], [NISTIR8309]). These estimates are not proofs; they rely on the current understanding that no more efficient public attack is known for the selected parameters. Using this framework and the parameter-set security table in the NTRU draft, the published NTRU parameter sets are assessed as meeting their intended bit-security targets ([NTRU-DRAFT], [NTRU-NIST]).¶

2.3. Assumptions and Conditions

The assumptions behind the NTRU security claim form a reduction chain. As discussed above, there is a reduction from the KEM security claim to the security of the underlying deterministic public-key encryption primitive, and the primitive security is then assessed through the hardness of the associated NTRU lattice search problems.¶

The first kind of assumption is that the proof model matches the implementation:¶

• The values sampled by KeyGen and Encaps have the required entropy and distribution.¶
• The implementation exposes only the public inputs and outputs modeled by the security game. In particular, no secret-dependent information is available through side-channel behavior, fault behavior, logs, or other externally visible behavior.¶

Under those black-box conditions, the remaining computational assumption is that the associated NTRU lattice search problems are hard at the claimed security level. The primitive-security estimate for this assumption is discussed in Section 2.2.¶

3.1. Encodings and Sizes

Implementations need to use the canonical encodings defined by the NTRU specification ([NTRU-DRAFT]):¶

public_key = pack_Rq0(H)
ciphertext = pack_Rq0(C)
shared secret = SHA3-256(pack_S3(R_shared,3) || pack_S3(M_shared,3))

All public keys and ciphertexts are fixed-length byte strings. The exact sizes for the parameter sets covered by this document are listed in Section 1. Implementations need to reject public-key or ciphertext inputs whose lengths do not match the selected parameter set.¶

The NTRU draft describes the private key as internal values. A private-key interchange format is not required for KEM interoperability and is not defined in this document.¶

Protocol profiles that carry public keys or ciphertexts should use the canonical NTRU byte strings for those values. In particular, the packed Rq0 byte string is the protocol representation of a public key or ciphertext, and the 32-byte SHA3-256 output is the KEM shared secret.¶

3.2. Validation and Failure Handling

The NTRU draft defines validation primarily through decoding of packed polynomials and through decapsulation-time validity checks ([NTRU-DRAFT]). This document does not add a separate public-key validity check.¶

Implementations need to check that public-key and ciphertext byte strings have the exact length for the selected parameter set before applying unpack_Rq0. After unpacking, the reconstructed polynomial is the value processed by the NTRU algorithm.¶

During decapsulation, implementations need to perform the parameter-set-specific validity checks on the reconstructed randomizer and message/preimage values, and then select either K1 or the fallback value K2 exactly as specified by NTRU. If those checks fail, NTRU decapsulation outputs K2 rather than a detailed cryptographic error. The decapsulation interface should not reveal whether K1 or K2 was selected; in particular, implementations should not return distinct error codes or expose ciphertext validity through logs, metrics, or debugging interfaces.¶

3.3. Randomness Requirements

NTRU uses randomness in two different places ([NTRU-DRAFT]):¶

• KeyGen samples the secret polynomials, abstractly the short secret and auxiliary values produced by the parameter-set-specific sample_fg procedure. Any private fallback material s used to compute K2 is also private key material.¶
• Encaps samples the ephemeral pair R_shared,3 and M_shared,3 using the parameter-set-specific sample_rm procedure.¶

For both uses, sampled values need to have the entropy and distributions required by the selected parameter set. They can be obtained directly from a true random source, or from a cryptographically secure pseudorandom generator or deterministic random bit generator that is properly seeded with entropy at least equal to the security level of the selected parameter set ([RFC4086], [RFC8937]). If a pseudorandom generator is used, its seed and internal state need to be protected as secret state.¶

Encapsulation randomness needs to be freshly and independently sampled for every encapsulation.¶

3.4. Side-Channel Considerations

Implementations need to avoid leaking secret-dependent information through timing, branches, memory access patterns, or other externally visible behavior. This applies to secret-dependent processing in KeyGen, Encaps, and Decaps, including handling of decapsulation validity checks and selection between K1 and K2.¶

Decapsulation should not expose whether the normal value K1 or the fallback value K2 was selected. Public length checks and parsing decisions that depend only on public byte string lengths need not be constant-time.¶

Sensitive intermediate values should be cleared as soon as they are no longer needed. Implementations deployed in environments with physical or shared-resource attack exposure should apply the usual side-channel protections for modern KEM implementations.¶