<p>@mikero mentioned Bellare &amp; 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 <a href="http://eprint.iacr.org/2004/332.pdf" rel="nofollow">Sequences of Games: A Tool for Taming Complexity in Security Proofs</a>, which, IMHO, is a much easier read. </p>

<p>The basic idea is a to show a sequence of 3 games:</p>

<ol>
<li>In game 0, adversary A is given oracle access to a random permutation $\pi$. </li>
<li>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").</li>
<li>Finally, in game 2, the stateful random function is replaced with a "stateless" (of "forgetful") one.</li>
</ol>

<p>Shoup shows how these games are connected, and thus proves the following:</p>

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

CC BY-SA 3.0
2012-07-12T18:21:35.177Z
2012-07-12T18:21:35.177Z
Sadeq Dousti
<p>A good reference is 
<a href="http://eprint.iacr.org/2004/331">Code-Based Game-Playing Proofs and the Security of Triple Encryption</a> by Bellare &amp; Rogaway. The statement that you are asking about is called the <strong>PRF/PRP switching lemma</strong>. 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.</p>

<p>Here is another paper (<a href="http://eprint.iacr.org/2008/078">A Short Proof of the PRP/PRF Switching Lemma</a>, Chang &amp; Nandi) that claims a short self-contained proof as well.</p>

CC BY-SA 3.0
2012-07-11T19:47:04.620Z
2012-07-11T19:47:04.620Z
mikero
<p>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 <em>Introduction to Modern Cryptography</em>.</p>

<hr>

<p>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.</p>

<p><strong>Proof idea</strong>: $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$.</p>

<p>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</p>

<p>$$(2^n)^{2^n-q(n)}$$</p>

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

<hr>

<p>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>

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

<p>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.</p>

CC BY-SA 3.0
2012-07-09T20:27:38.237Z
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
CC BY-SA 3.0
2012-07-10T13:34:38.723Z
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
CC BY-SA 3.0
2012-07-10T13:45:55.857Z
I do not think that this is a research-level question, and voted to close it as off topic.
Tsuyoshi Ito
CC BY-SA 3.0
2012-07-10T14:53:01.103Z
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
CC BY-SA 3.0
2012-07-10T20:14:31.283Z
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
<cr.crypto-security><randomized-algorithms><query-complexity><pseudorandomness>
Rigorous proof that a random function and a random permutation cannot be distinguished in polynomial time
eof
# Rigorous proof that a random function and a random permutation cannot be distinguished in polynomial time

(Asked by: username_0 on 2012-07-09)

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.

**Tags:** cr.crypto-security, randomized-algorithms, query-complexity, pseudorandomness
> **Comments:**
> **username_0**: 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.  
> **username_1**: 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)!  
> **username_1**: I do not think that this is a research-level question, and voted to close it as off topic.  
> **username_0**: 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).  
> **username_2**: 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....  

---

## 2 answers

### Answer by username_4 on 2012-07-11. Score: 7 | Accepted answer

A good reference is
[Code-Based Game-Playing Proofs and the Security of Triple Encryption](http://eprint.iacr.org/2004/331) 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](http://eprint.iacr.org/2008/078), Chang & Nandi) that claims a short self-contained proof as well.


---

### Answer by username_3 on 2012-07-12. Score: 4

@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](http://eprint.iacr.org/2004/332.pdf), 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}$.


---

