Module LWE ⇒ IND-CCA KEM

Random oracle model · BDK+18 · security loss: tight in the random-oracle model: a constant multiple of the Module-LWE advantage plus a term of order $q\delta$ for $q$ random-oracle queries and decryption-failure probability $\delta$; non-tight in the quantum random-oracle model

Statement

Kyber, the basis of ML-KEM (FIPS 203), is a KEM over module lattices. If Module LWE is hard (module rank $k\in \{2,3,4\}$ in the proposed parameter sets), Kyber is IND-CCA-secure in the random-oracle model: an IND-CPA public-key encryption scheme from Module LWE is converted into an IND-CCA KEM by a Fujisaki–Okamoto transform with implicit rejection. The reduction is tight in the random-oracle model and non-tight in the quantum random-oracle model — BDK+18.

Sketch

The IND-CPA scheme is the module analogue of the LPR10 scheme: the public key is $(\mathbf{A},\mathbf{t}=\mathbf{As}+\mathbf{e})$ and a ciphertext is a pair of compressed Module LWE samples carrying the message in the high-order bits, so key and ciphertext are pseudorandom under Module LWE. The Fujisaki–Okamoto transform then derives the encryption coins and the session key by hashing the message; decapsulation re-encrypts and, on a mismatch, outputs a pseudorandom key derived from a secret seed.

Notes

• Kyber’s IND-CCA proof instantiates the modular Fujisaki–Okamoto analysis, which supplies the ROM and QROM bounds — HHK17.