Rigorous proof that a random function and a random permutation cannot be distinguished in polynomial time

Question

I have a background in number theory and I'm trying to learn how to reason rigorously about algorithms. I'm reading chapter 2 of Katz and Lindell's Introduction to Modern Cryptography.

---

Show that no probabilistic polynomial-time algorithm $A$ can distinguish between a random function $f:\{0,1\}^n\to \{0,1\}^n$ and a random permutation $g:\{0,1\}^n\to \{0,1\}^n$ when in each case $A$ is given oracle access to the tested function. Distinguish here is of course except with a negligible probability.

Proof idea: $A$ can make at most $q(n)$ queries to the oracle for some polynomial $q(n)$. The chance that $A$ will find out that the given function is not injective is at most whatever probability comes out of the birthday problem of probability theory, but this is negligible in terms of $n$.

If $A$ does not find a collision among the $q(n)$ queries, then $A$ can't know where the $2^n-q(n)$ remaining elements are mapped, so the function can be any function out of

$$(2^n)^{2^n-q(n)}$$

possibilities of which $(2^n-q(n))!$ are permutations, which is a negligible fraction.

---

Now fix the algorithm and assume it's been given the function $F$ as an oracle. Say $A^F$ returns $1$ if $F$ is determined to be a random permutation by $A$ and $0$ if not. The problem is that I can't know anything about the strategy that $A$ uses and in order to rigorously prove the problem, I would need to show that

$$|P(A^f(n)=1)-P(A^g(n)=1)|\leq \epsilon(n),$$

where $\epsilon$ is a negligible function. How is this done in a mathematically precise way? Where (even though the book is very vague about this), the probability of each term is taken over the choice of $f$ and $g$ and whatever coin flips $A$ does.

Answer 1

A good reference is Code-Based Game-Playing Proofs and the Security of Triple Encryption by Bellare & Rogaway. The statement that you are asking about is called the PRF/PRP switching lemma. This paper goes into significant detail about "standard" proofs of this lemma and the subtleties therein. It uses the switching lemma as an illustrative example to advocate for a "game-playing" paradigm for cryptographic proofs that is the "real" purpose of the paper.

Here is another paper (A Short Proof of the PRP/PRF Switching Lemma, Chang & Nandi) that claims a short self-contained proof as well.

Answer 2

@mikero mentioned Bellare & Rogaway's paper, which gives a full proof. It's a rather advanced one, which is hard to digest. I suggest reading section 5.1 of Victor Shoup's Sequences of Games: A Tool for Taming Complexity in Security Proofs, which, IMHO, is a much easier read.

The basic idea is a to show a sequence of 3 games:

1. In game 0, adversary A is given oracle access to a random permutation $\pi$.
2. In game 1, the random permutation $\pi$ is replaced with a "stateful" random function, which preserves the "permutation" property. (In Bellare-Rogaway terminology, this is called "lazy sampling").
3. Finally, in game 2, the stateful random function is replaced with a "stateless" (of "forgetful") one.

Shoup shows how these games are connected, and thus proves the following:

Any oracle machine that makes at most $q$ queries to its oracle, its RF/RP-advantage is at most $\frac{q^2}{2} \cdot 2^{-\ell}$.