Skip to content

Back to the catalog

Faster generic CCA secure KEM transformation using encrypt-then-MAC
eprint.iacr.orgpaper

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

The paper proposes a generic encrypt-then-MAC transformation for building CCA-secure KEMs. The PKE ciphertext is authenticated by a MAC keyed from the PKE plaintext, so decapsulation no longer needs the Fujisaki-Okamoto re-encryption step. It proves IND-CCA security in the random oracle model from OW-PCA, and IND-qCCA security from a new OW-qPCA notion. It presents ML-KEM-EtM and McElieceEtM (Classic McEliece), and benchmarks ML-KEM-EtM with Poly1305, GMAC, CMAC and KMAC256. The result is a substantially lower decapsulation cycle count for a small cost in encapsulation cycles and ciphertext size.

TL;DR Encrypt-then-MAC replaces FO re-encryption in ML-KEM decapsulation: provably IND-CCA/qCCA, with much faster decapsulation.
Open original ↗
Document

What it is

A preprint (ePrint 2026/2442, not peer reviewed) proposing encrypt-then-MAC as a generic PKE-to-KEM transformation. It is an alternative to Fujisaki-Okamoto (FO) for ML-KEM and Classic McEliece. The authors are Xu, Mandal and Gong.

How it works

  • The abstract's argument is that ML-KEM's PKE encryption is slower than its decryption, so FO's re-encryption dominates decapsulation.
  • In the new scheme the MAC key is derived from the PKE plaintext, and the MAC authenticates the PKE ciphertext.
  • The random oracle is applied only to the short PKE plaintext. The long ciphertext goes through a standard-model MAC that only needs to be one-time existentially unforgeable.
  • The abstract contrasts this with the tag-based IND-1CCA transformations of Huguenin-Dumittan and Vaudenay (Eurocrypt 2022). Their tag is a random-oracle hash over the plaintext and the entire ciphertext.

Preconditions / Affected

The security level you get depends on the instantiation:

SchemeSecurity claimedRests on
ML-KEM-EtMIND-qCCA (q-bounded)OW-qPCA of the ML-KEM PKE
McElieceEtMFull IND-CCAConjectured OW-PCA of the Niederreiter PKE

ML-KEM-EtM is therefore not a drop-in equivalent of the FIPS 203 KEM's full IND-CCA guarantee. It is a different KEM with a bounded-query guarantee, and the bound is tied to the new OW-qPCA assumption.

What to do

  • If you are evaluating this for ML-KEM, treat it as research. Check whether your threat model tolerates a q-bounded CCA guarantee, and how large q is in your deployment.
  • The abstract gives no cycle counts or ciphertext sizes. Get them from the full paper before judging the tradeoff.
  • The MAC choice is open. The authors implemented Poly1305, GMAC, CMAC and KMAC256, so compare them in the paper's benchmarks.

Caveats

  • The abstract states the cost only as "minimal increase" in encapsulation cycles and ciphertext size, and a "substantial reduction" in decapsulation cycles. No figures appear on the fetched page.
  • OW-qPCA is a new notion introduced by the paper, and McEliece's full CCA result depends on a conjectured assumption.
  • The page is the abstract and metadata only, so I could not check the proofs, the value of q, or the benchmark setup.

Organisations named here

  • FIPS 203
  • Fujisaki-Okamoto transformation
  • IND-CCA
  • McElieceEtM
  • ML-KEM
  • ML-KEM-EtM
  • OW-PCA

Technologies named here

  • ML-KEM-EtM
  • Classic McEliece, instantiated in McElieceEtM
  • McElieceEtM
  • Poly1305, GMAC, CMAC, KMAC256
  • ML-KEM
  • NIST
  • Classic McEliece
  • CMAC
  • GMAC
  • KMAC256
  • Poly1305

Techniques named here

  • OW-qPCA

Related in other