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:

1. Eve chooses a pair of equal-size messages m₀,m₁.

2. Owen generates a random secret key k and chooses a bit b ←{0,1} at random.

3. Owen then computes the ciphertext c = e_k(m_b) – referred to as the challenge ciphertext – and gives it to Eve. (Note that we use e_k instead of f_k here to denote encryption because the...