15.1 Preliminaries
Before diving into the details of authenticated encryption, we must first introduce some security concepts that we will need later on for an in-depth understanding and comparison of different authenticated encryption schemes.
15.1.1 Indistinguishability under a chosen-plaintext attack
Recall that our intuitive understanding of secure encryption is captured in the formal notion of indistinguishability in the presence of an eavesdropper. The key idea of indistinguishability is captured in the game – sometimes referred to as an experiment in cryptographic literature – played by Eve and some other party, let’s say, Owen:
Eve chooses a pair of equal-size messages m0,m1.
Owen generates a random secret key k and chooses a bit b ←{0,1} at random.
Owen then computes the ciphertext c = ek(mb) – referred to as the challenge ciphertext – and gives it to Eve. (Note that we use ek instead of fk here to denote encryption because the...