Switching Lemma

Let $\mathcal{D}$ be a finite nonempty domain, $R\stackrel{\$}{\leftarrow }\mathrm{Funcs}(\mathcal{D},\mathcal{D})$, and $\pi \stackrel{\$}{\leftarrow }\mathrm{Perms}(\mathcal{D})$. For any possibly randomized distinguisher $\mathcal{A}$ making at most $q$ adaptive forward queries,

$$\left|\mathrm{Pr}[{\mathcal{A}}^R=1]-\mathrm{Pr}[{\mathcal{A}}^{\pi }=1]\right|\le \min \left\{1,\frac{q(q-1)}{2|\mathcal{D}|}\right\}.$$

Repeated queries return the same answer; neither experiment provides inverse queries — standard.

Proof

Couple the lazy-sampled oracles until their answers first differ. On the $j$th distinct input, draw the function’s answer uniformly from $\mathcal{D}$. If it is unused, give the permutation the same answer; otherwise give the permutation an independent uniform unused answer and stop coupling. Before divergence the permutation’s answer is uniform among unused values, and divergence on this query has probability $(j-1)/|\mathcal{D}|$. A union bound over at most $q$ distinct inputs gives $q(q-1)/(2|\mathcal{D}|)$; repeated inputs add no chance of divergence. Identical transcripts give identical outputs when the adversary’s coins are coupled — standard. See BR06 for a game-playing treatment.

Memory bounded version

This has been subsequently improved by Din20 for streaming distinguishers with $m$ bits of memory to $\left|\mathrm{Pr}[A^R=1]-\mathrm{Pr}[A^{\pi }=1]\right|\le O\left(\frac{mq}{|\mathcal{D}|}\right),$ where $R$ is a random function and $\pi$ is a random permutation, both from $\mathcal{D}$ to $\mathcal{D}$.

Participates in

Used via Switching Lemma

• PRP ⇒ iPRF (large domains)
• PRP ⇒ PRF