Paper 2026/2442

Faster generic CCA secure KEM transformation using encrypt-then-MAC

Abstract

ML-KEM is a lattice-based IND-CCA secure key encapsulation mechanism (KEM) standardized by NIST in FIPS 203. ML-KEM achieves chosen-ciphertext security by applying the Fujisaki-Okamoto (FO) transformation to an IND-CPA secure public key encryption (PKE) scheme. The FO transformation uses de-randomization and re-encryption to ensure ciphertext non-malleability, but because ML-KEM's underlying PKE encryption subroutine is slower than the decryption subroutine, ML-KEM's decapsulation performance is dominated by re-encryption. In this paper, we revisit the ``encrypt-then-MAC'' paradigm as a generic KEM transformation: the PKE ciphertext is authenticated by a message authentication code (MAC) whose key is derived from the PKE plaintext. We prove that the transformation achieves IND-CCA security in the random oracle model when the underlying PKE is one-way under plaintext-checking attack (OW-PCA), and we introduce a fine-grained security notion, one-wayness under $q$-bounded plaintext-checking attack (OW-$q$PCA), under which the transformation achieves IND-$q$CCA security. In contrast to the tag-based IND-1CCA transformations of Huguenin-Dumittan and Vaudenay (Eurocrypt 2022), whose tag is a random-oracle hash of the plaintext and the entire ciphertext, our transformation applies the random oracle only to the short PKE plaintext, while the long ciphertext is processed by a standard-model MAC that needs only to be one-time existentially unforgeable. We present ML-KEM-EtM, an IND-$q$CCA secure KEM derived from applying the encrypt-then-MAC transformation to the PKE subroutines of ML-KEM, and McElieceEtM, an instantiation with Classic McEliece that achieves full IND-CCA security under the conjectured OW-PCA security of its Niederreiter PKE. We implement ML-KEM-EtM with a wide selection of MACs including Poly1305, GMAC, CMAC, and KMAC256. At the cost of minimal increase in encapsulation CPU cycle count and ciphertext size, ML-KEM-EtM achieves a substantial reduction of the decapsulation CPU cycle count.