§11 Authenticated Encryption

Authenticated Encryption: Definition

• Definition. Let $(Gen_E, Enc, Dec)$ be an encryption scheme and let $(Gen_M, Mac, Vrfy)$ be a message authentication code. A combination is a tuple of algorithms $(Gen' , EncMac' , Dec', Vrfy' )$

  1. Key Generation $Gen'$: Given input $1^n$, outputs $k_E, k_M \in \{0,1\}^n$.
  2. $EncMac'$: Given $(k_E, k_M)$ and a message $m$, outputs a value $c$ derived by some combination of $Enc_{k_E}( \cdot )$ and $Mac_{k_M}( \cdot )$.
  3. $Vrfy'$: Given input $(k_E, k_M)$ and $c$, outputs $1$ or $0$.
  4. $Dec'$: Given input $(k_E, k_M)$ and $c$, outputs some value $m$.

• Definition. A private-key encryption scheme $\Pi$ is Unforgeable if for all probabilistic polynomial-time adversaries $𝒜$, there is a negligible function $\epsilon$ such that:

  $$\Pr\left[\operatorname{Enc-Forge}_{\mathscr{A}, \Pi}(n)=1\right]\le\epsilon(n)$$

• Definition. A private-key encryption scheme $\Pi = (Gen' , EncMac' , Dec' , Vrfy' )$ is an Authenticated Encryption Scheme if it is CCA-secure and Unforgeable.

The Unforgeable Encryption Experiment $\operatorname{Enc-Forge}_{\mathscr{A}, \Pi}(n)$

• We define, for a private-key encryption scheme $\Pi = (Gen, Enc, Dec)$, an adversary $\mathscr A$, and security parameter $n$, the unforgeable encryption experiment $\text {Enc-Forge}_{\mathscr{A}, \Pi}(n)$ as follows:
  1. Run $Gen(1^n)$ to obtain a key $k$.
  2. The adversary $\mathscr A$ is given input $1^n$ and access to an encryption oracle $Enc_k ( \cdot )$. The adversary outputs a ciphertext $c$.
  3. Let $m := Dec_k(c)$, and let $\mathscr Q$ denote the set of all queries that $\mathscr A$ askes the encryption oracle. The adversary succeeds and the output of the experiment is $1$ if and only if
     1. $m \ne \perp$, and
     2. $m \notin \mathscr Q$.

Encrypt-then-Authenticate construction

• Let $\Pi_E = (Enc, Dec)$ be a private-key encryption scheme and let $\Pi_M = (Mac, Vrfy)$ be a Message Authentication Code, where in each case key generation is done by choosing a uniform $n$-bit key. Define a private-key encryption scheme $(Gen' , Enc' , Dec')$ as follows:
  • $Gen'$: Given input $1^n$, choose independent, uniform $k_E, k_M \in \{0,1\}^n$ and output the key $(k_E, k_M)$.
  • $Enc'$: Given inputs a key $(k_E, k_M)$ and a plaintext message $m$, compute $c \leftarrow Enc_{k_E}(m)$ and $t \leftarrow Enc_{k_M}(c)$. Output the ciphertext $\langle c, t \rangle$.
  • $Dec'$: Given inputs a key $(k_E, k_M)$ and a ciphertext $\langle c, t \rangle$, first check whether $Vrfy_{k_M}(c, t) \stackrel{?}{=} 1$. If yes, then output $Dec_{k_E}(c)$; if no, output $\perp$.

Encrypt-then-Authenticate construction: Security

• Theorem. Let $\Pi_E$ be a CPA-secure private-key encryption scheme and let $\Pi_M$ be a strongly secure message authentication code. Then the Encrypt-then-Authenticate construction is an authenticated encryption scheme.
  • In a Strong MAC, the attacker cannot forge a new valid tag even on a message that he previously queried to the Mac oracle.
  • We define the Mac-sforge experiment, in which the set $\mathscr Q$ of queries to the Mac oracle consists of pairs $(m, t)$, i.e., $(m, t) \in \mathscr{Q}$ if $\mathscr A$ queried $Mac_k(m)$ and received in response the tag $t$. The Mac-sforge experiment succeeds if $\mathscr A$ outputs $(m, t)$ such that $Vrfy_k(m, t) = 1$ and $(m, t) \notin \mathscr{Q}$.

— Mar 3, 2023

§11 Authenticated Encryption by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.