Switching Lemma

Consider \(Enc_{k}(m) = \langle r, F_k(r)\oplus m\rangle\) and \(Dec_{k}(\langle r,s\rangle)=F_{k}(r)\oplus s\)

• Real world: Nonces \(r_1, \ldots, r_q\in \{0,1\}^\lambda\) picked randomly.
  • Equivalent view: \(r_i=f(i)\) where \(f\) is a truly random function
• Ideal world: \(r_{i}=f(i)\) where \(f\) is a truly random permutation
  • No nonce collisions in Ideal world
• Switching lemma states that an attacker can distinguish between real/ideal world (in both directions) with probability at most \(\frac{{q\choose 2}}{2^{\lambda}}\le \frac{q^{2}}{2^{\lambda+1}}\) \(\vert Pr\mathcal{[A}^{P(\cdot)}=1] - Pr[\mathcal{A}^{F(\cdot)}=1]\vert \in O(q^{2}/N)\)
• In other words, an attacker can distinguish between truly random permutation and truly random function
• E.g., AES-GCM uses a PRP instead of PRF
• We can again apply Switching lemma to use AES-GCM as a PRF