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

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.

• BTW, I'm posting it in the TCS forum, since I asked a few (practically oriented) CS people I know, but they weren't able to give a proof that I would consider rigorous as a mathematician... The book I'm reading omits the proof. – eof Jul 9 '12 at 20:27
• When you post a question next time, please try to use a more descriptive title. In the original title, you had omitted the most important piece of information (proof of what)! – Tsuyoshi Ito Jul 10 '12 at 13:34
• I do not think that this is a research-level question, and voted to close it as off topic. – Tsuyoshi Ito Jul 10 '12 at 13:45
• The problem itself is not particularly research-level, but it seems like the required proof technique is at the graduate level, which was OK according to the FAQ. I do not really care about this particular problem, but more about the general proof technique. My original hunch was that this is tricky, since there does not seem to be any reduction here to another obvious problem and in general quantifying over all algorithms seems to be tricky in computer science (which is why I would guess P vs. NP is still open). – eof Jul 10 '12 at 14:53
• think this is research level. if not then what is a reference that has a proof? yes based on razborov/rudich "natural proofs", P vs NP is similar to breaking hard RNGs & is closely related to conjectures about "hard" RNGs not being breakable. another proof idea-- convert the permutation fn to another function that refers to the n'th permutation. one observation is that any proof would seem to require a concept of discriminating "hard" vs "easy" functions, which your proof sketch above does not.... – vzn Jul 10 '12 at 20:14

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.

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