Switching Lemma

For any distinguisher $A$ issuing $q$ queries to its oracle, $\left|\mathrm{Pr}[A^R=1]-\mathrm{Pr}[A^{\pi }=1]\right|\le O\left(\frac{q^2}{|\mathcal{D}|}\right),$ where $R$ is a random function and $\pi$ is a random permutation, both from $\mathcal{D}$ to $\mathcal{D}$.

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}$.