BW-KEM

The claimed decryption failure rate averages the noise covariance over the key; per-key rates are 12 to 24 bits higher

Holds · Argued · Cause: construction

Property: correctness claim (decryption failure rate); no security property falls

Cost against claim: failure rate averaged over keys about 2^-123 to 2^-220 against claims of 2^-138 to 2^-233; still far below 2^-80

The specification computes the decryption failure rate with the Gaussian part of the block noise taken as isotropic, with the variance it has on average over the secret key. For a fixed key the covariance of a block is set by the autocorrelations of s and e, its largest eigenvalue reaching 1.37 times that variance on sampled keys, and the failure probability, dominated by that direction, is higher: averaged over 10 keys per set it is about 2^-123, 2^-187, 2^-192 and 2^-220 against the claimed 2^-138, 2^-210, 2^-216 and 2^-233. Failures remain out of reach within the 2⁸⁰ decapsulation queries the call allows, so no attack follows.

What causes it

Section 5.2 (Theorem 6 and the paragraph after it) approximates the joint law of the coefficients of e^T r − s^T(e1 + ε_u) in a block by N(0, σ²I_n) with σ² = lNσ1²(σ1² + σ2² + σ_εu²), and Section 5.1 (Corollary 1) applies a union bound over the N/n blocks. That variance is an average over the key: the analysis removes the independence assumption between coefficients but keeps the averaging over (s, e), while a user's long-term key has one covariance, not the average one.

Evidence

A second member of PQC-X rebuilt the failure model from the specification's formulas with independent code. With the isotropic covariance it reproduces the claimed rates (2^-138.27, 2^-210.28, 2^-216.63 and 2^-232.94 against the claimed 2^-138.14, 2^-209.94, 2^-216.26 and 2^-232.71 of BW-KEM-c128, -c256, -c384 and -c512). With the exact covariance of 10 sampled keys per set, built from the negacyclic autocorrelations of s and e, the rate averaged over keys is about 2^-123, 2^-187, 2^-192 and 2^-220, that is 18, 27, 19 and 19 bits above the key-independent figure of the same model, and the worst of the 10 keys is 21 to 31 bits above it. These figures replace a first estimate by PQC-X on 2000 keys per set, which had overstated the gap by treating the bounded term e2 + ε_v as Gaussian. PQC-X also compared the per-key covariance with the reference implementation on 8 BW-KEM-c512 keys and 20000 encryptions each, where the predicted and observed frequencies of large block-noise norms agree at the 10^-3 and 10^-4 thresholds; that comparison was not re-run by the second member.

Cause in the specification, traced to the specification text.

Limits

Ten keys per set; a run on 2000 keys was not completed. The per-key model, checked against the exact isotropic computation, is within 0.5 to 4 bits of it at c128, c256 and c512 and about 11 bits pessimistic at c384, so the c384 figures overstate the effect. The strengthened -s variants were not recomputed. At BW-KEM-c128 the worst sampled key gives about 2^-120, so 2⁸⁰ decapsulation queries produce a failure with probability about 2^-40; the other sets are further away.

Credit

Found by PQC-X.

The submitted ICCS wrapper returns -1 on a rejected ciphertext where the specification rejects implicitly

Holds · Demonstrated · Cause: code

Property: conformance

Cost against claim: a validity bit after the full re-encryption check; the shared secret stays the implicit-rejection key; nothing falls

Scope: Callers of the submitted ICCS interface who branch on its return value; the internal decapsulation and the specification are unaffected.

The wrapper kem_dec of the submitted code returns -1 whenever the re-encryption comparison fails, while the internal decapsulation returns 0 in every case and both write the implicit-rejection key derived from z and the received ciphertext. The specified Decaps never signals a failure, and its IND-CCA proof is stated for that algorithm. The code is raised after the full comparison of the received ciphertext with its re-encryption, so it tells a caller only whether the ciphertext was formed honestly, which an attacker already knows: no plaintext-checking oracle and no security consequence.

What causes it

The ICCS API template asks kem_dec to return -1 when decapsulation is unsuccessful, and the header shipped with the C256 and C512 trees repeats it; KEM_AlgorithmInstance.c follows that wording after crypto_kem_dec (kem.c) has already replaced the key by the implicit-rejection value. The specification's Decaps (Section 4.2, Figure 4, lines 4 to 6) returns K̃ = H1(ID(pk), z, c) on a mismatch, and Theorem 5 (IND-CCA security in the ROM and QROM) is stated for that implicit-rejection algorithm.

Evidence

PQC-X flipped every bit of honest ciphertexts of the unmodified reference code (18432, 34560 and 70656 tampered ciphertexts over three keys for BW-KEM-c128, -c256 and -c512): the wrapper returned -1 on all of them, and the key it wrote was the implicit-rejection value in every case. A second member of PQC-X rebuilt the reference code, reproduced the three official KAT files byte for byte, and repeated the test on 5676, 10638 and 21744 tampered ciphertexts per set (all returned -1, with the implicit-rejection key) and on 12 honest ciphertexts per set (all returned 0, with the right key), checked that the internal crypto_kem_dec returns 0 in all cases, and compared the wrapper with the ICCS template and with the KEM wrappers of the other round-1 submissions, about a third of which signal rejection in the same way.

Cause in the submitted code; the specification is not affected.

Limits

Nothing falls: the return value is computed after the whole ciphertext has been compared with its re-encryption, so it depends on the ciphertext's validity, not on the key, and explicit rejection after a complete re-encryption check keeps IND-CCA security in the random-oracle model. What remains is a divergence between the submitted interface and the implicit-rejection decapsulation the specification defines and proves, inherited from the ICCS API template.

Credit

Found by PQC-X.