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

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.

Metadata

• Available format(s)

PDF

• Category
• Public-key cryptography
• Publication info
• Preprint.
• Keywords
• Post-quantumKEMML-KEMEncrypt-then-MAC
• Contact author(s)

•   g66xu @ uwaterloo ca
  

kmandal @ unb ca ggong @ uwaterloo ca

• History
• 2026-10-14: approved
• 2026-10-11: received
• See all versions
• Short URL
• https://ia.cr/2026/2442
• License

CC BY

BibTeX

@misc{cryptoeprint:2026/2442,
      author = {Ganyu Xu and Kalikinkar Mandal and Guang Gong},
      title = {Faster generic {CCA} secure {KEM} transformation using encrypt-then-{MAC}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2442},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2442}
}