A Short Proof of the PRP/PRF Switching Lemma.
Donghoon Chang, Mridul Nandi · 2008
Abstract. In Eurocrypt 2006, Bellare and Rogaway [2] gave a proof of the PRP/PRF switching Lemma using their game-based proof technique. In the appendix of the same paper, they also gave an proof without games. In this paper, we give another proof of the switching lemma, which is simple and mathematically-clear and easy to uderstand. Our proof is based on the strong interpolation theorem. Keywords: PRF, PRP, Switching Lemma. 1 Some Notations and Results This section is almost same as that of [3]. Counting. Let F: = Func(n, n), the set of all functions f: {0, 1} n → {0, 1} n. And let P: = Perm(n, n), the set of all permutations f: {0, 1} n → {0, 1} n. It is easy to see that |F | = 2n2n and |P | = 2n!. Now, for any distinct ai’s and any distinct zi’s, the number of functions f such that f(a1) = z1, · · · , f(aq) = zq is exactly 2 n(2n −q) because, the outputs of q elements are fixed and the rest (2 n − q) many outputs can be chosen in (2 n) (2n −q) many ways. Similarly, for any distinct ai’s and any distinct zi’s, the number of permutations f such that