Authenticated encryption aims to satisfy both *secrecy (encryption)* and *integrity (authentication)* simultaneously. Let’s define the experiment:

$Pr[Enc-Forge_{A,Π}(n)=1]≤negl(n)$unforgeable encryption experiment $Enc-Forge_{A,Π}(n)$:

- key $K$ is generated
- adversary $A$ is given access to encryption oracle $Enc_{k}(⋅)$.
- $A$ outputs $c$. Let $m←Dec_{k}(c)$, then
- $A$ succeeds if $m=⊥$ and $m∈Q$.

A private key encryption is AE scheme if it satisfies both CCA security and unforgeability. Let’s define two oracles:

- $Enc_{k}(⋅)$: sends encryption of $0_{∣m∣}$ for any message $m$
- $Dec_{⊥}(⋅)$: sends decryption error $⊥$ for any ciphertext $c$

Our goal is to not let adversary distinguish between correct oracle response and above two oracles. This guarantees that adversary can’t distinguish between encryption of $0_{∣m∣}$ and valid message $m$, ensures secrecy and also can’t decrypt any valid ciphertext, ensures integrity.

AE experiment $PrivK_{A,Π}(n)$:

- key $K$ is generated
- uniform bit $b∈{0,1}$ is chosen
- adversary is given access to oracles:

- if $b=0$, $Enc_{k}(⋅),Dec_{k}(⋅)$
- if $b=1$, $Enc_{k}(⋅),Dec_{⊥}(⋅)$
- $A$ outputs bit $b_{′}$
- $A$ succeeds if $b=b_{′}$.

$Pr[PrivK_{A,Π}(n)=1]≤21 +negl(n)$

- AE with AD (associated data) is possible when some data is public is needed to be sent with integrity only.
- CCA security and AE are separate notions, with an encryption that is CCA secure, we want secrecy but not integrity, AE targets both.
- with any encryption that is CCA secure and MAC that is strongly secure, AE scheme can be constructed.

Three constructions are possible when designing an AE:

- encrypt and authenticate: $c←Enc_{K_{e}}(m)$ and $t←Mac_{K_{m}}(m)$
- TODO: prove this is not AE secure

- authenticate then encrypt: $t←Mac_{K_{m}}(m)$ and $c←Enc_{K_{e}}(m∥t)$
- TODO: prove this is not AE secure

- encrypt then authenticate: $c←Enc_{K_{e}}(m)$ and $t←Mac_{K_{m}}(c)$
- to forge a mac, adversary needs pair $⟨c,t_{′}⟩$ for original $c$, but strong security of MAC, makes this negligible, thus decryption oracle for AE scheme is useless and CCA security of AE reduces to CPA security of $Π_{E}$.

AE construction:

- $Gen’(1_{n})→(K_{m},K_{e})$: outputs two keys $K_{m},K_{e}$
- $Enc_{′}(m)$: outputs $⟨c,t⟩$ where, $c←Enc_{K_{e}}(m)$ and $t←Mac_{K_{m}}(c)$
- $Dec_{′}(c,t)$: verifies $t?Vrfy(c)$, and outputs $m←Dec_{K_{m}}(c)$.

Prove that if $Π_{e}$ is CPA secure ENC scheme and $Π_{m}$ is strongly secure MAC scheme, then above construction is AE scheme.

- you begin by first proving that if $Π_{m}$ is a strongly secure MAC, then probability of forgeability is negligible, i.e. probability of event that any new, valid pair $⟨c,t⟩$ is accepted is negligible.
- This renders the decryption oracle useless, as only error will be sent to the adversary for any other pair for which it hasn’t already queried the encryption oracle.
- This turns the CCA security of encryption scheme to CPA security.
- denote this by $Pr[ValidQuery]≤negl(n)$
- create adversary $A_{m}$ which is running $Mac-sforge$ experiment by attacking $Π_{m}$ and runs $A$ as subroutine
- Now, our goal is to prove that $Pr[Mac-sforge_{A_{m},Π_{m}}=1]≤Pr[ValidQuery]$, i.e. if $A$ is successful in outputting a new, valid $⟨c,t⟩$, then $A_{m}$ will be able to succeed in sforge experiment.

- Now, since $Pr[ValidQuery]$ is negligible, then we prove that $Π$ is CCA-secure (CPA security), i.e. $Pr[PrivK_{A,Π}=1]≤Pr[ValidQuery]+Pr[PrivK_{A,Π}∧ValidQuery ]$
- again run CPA experiment with adversary $A_{e}$ running $A$ as subroutine, answering encryption oracle queries and outputting errors for decryption oracle queries.
- when $A_{e}$ outputs $m_{0},m_{1}$ then, $A$ outputs exactly those message, get the challenge ciphertext $c$, and calculate $t←Mac_{K_{m}}(c)$.
- $A$ output the same bit $b_{′}$ as output by $A$.
- then $Pr[PrivK_{A_{e},Π_{e}}=1]≥Pr[PrivK_{A,Π}∧ValidQuery ]$