CPA-secure SKE + arbitrary-length SUF-CMA MAC ⇒ AE (Encrypt-then-MAC)

Fully-black-box reduction · standard model · BN00 · security loss: none in the privacy term; factor in the integrity term: an INT-CTXT adversary making encryption and verification queries has advantage at most times the SUF-CMA advantage of a forger making tag queries

Statement

Let be a CPA-secure SKE scheme and a SUF-CMA-secure MAC for arbitrary-length messages, so that it tags every ciphertext of . Encrypt-then-MAC under an key and an independent key , which encrypts to for and decrypts to if and to otherwise, is an authenticated encryption scheme: it is CPA-secure and INT-CTXT-secure — BN00. Encrypt-then-MAC is -correct for a -correct and a -correct , by a union bound, with the message space of — standard.

Sketch

A CPA adversary against samples and tags the ciphertexts it receives. A pair that verifies and was not output by the encryption oracle is a message–tag pair that the tag oracle never returned, which is a strong forgery.

Notes

  • With strong unforgeability defined through a verification oracle, the forger forwards every verification query, and the INT-CTXT advantage is at most the SUF-CMA advantage at verification queries — BN00; passing from that notion to the single-forgery one costs the factor — BGM04.
  • With a MAC that is only UF-CMA-secure, Encrypt-then-MAC can fail INT-CTXT security and CCA security — BN00.