better pictures for previously submitted question

The Feistel permutation. Let F:(0,1}n(0,1)n(0,1)n be a pseudorandom function. A natural idea for encrypting messages of length n would be to simply define enc (m)=Fk(m). One problem with this idea is that F might not be injective: there may well be two messages m1 and m2 for which Fk(m1)=Fk(m2), in which case it is hopeless to try to recover m from the "eneryption" Fk(m). In fact, even if F were invertible, there is no guarantee that the inverse could be computed efficiently, so this idea seems to have some problems. There is a remarkable way to approach this problem, which has been used quite successfully in practice: it's called the Feistel permutation. Given an arbitrary function f:{0,1}n{0,1}n, define f:{0,1}2n(0,1)2n by the rule f(x,y)=(y,xf(y)), where we treat (0,1)2n as the product (0,1)n(0,1)n and - by this correspondence-write elements of (0,1)2n as ordered pairs (x,y) (where both x and y are elements of {0,1} ). (a) With F defined as above, define the function :(0,1)n(0,1)2n(0,1) by the rule (k,(x,y))=Fi(x,y)=(y,xFk(y)). Note that for any k{0,1}n, the function F3 is a permutation of the set {0,1}2n. It is clear that if F can be computed in polynomial time, then so can. Prove that if F can be computed in polynomial time, then so can the inverse of . To be precise, show that there is an efficient algorithm I so that I(k,(x,y)) ) outputs the (unique) pair (a,b) so that Fi(a,b)=(x,y). (b) Prove that even if F is a pseudorandom function, is not a pseudorandom function. (c) However, iterating this process a few times does indeed result in a pseudorandom functions that is, moreover, invertible (and hence a permutation). Specifically, consider the permutation obtained by composition as follows: 3:{0,1}3n[0,1}2n{0,1] where 3((k1,k2,k3),(x,y))=Fi1(Fi2(Fk3(x,y))). It is a fact that if F is pseudorandom then is a pseudorandom permutation (and, as pointed out above, the inverse of 3 can be computed efficiently given k1,k2,k3 ). Prove that two iterations are not enough. Prove that the analogous function 2 is not pseudorandom. (Hint: Consider the output of the function on the two inputs (1n,0n) and (0n,0n).) The Feistel permutation. Let F:(0,1}n(0,1)n(0,1)n be a pseudorandom function. A natural idea for encrypting messages of length n would be to simply define enc (m)=Fk(m). One problem with this idea is that F might not be injective: there may well be two messages m1 and m2 for which Fk(m1)=Fk(m2), in which case it is hopeless to try to recover m from the "eneryption" Fk(m). In fact, even if F were invertible, there is no guarantee that the inverse could be computed efficiently, so this idea seems to have some problems. There is a remarkable way to approach this problem, which has been used quite successfully in practice: it's called the Feistel permutation. Given an arbitrary function f:{0,1}n{0,1}n, define f:{0,1}2n(0,1)2n by the rule f(x,y)=(y,xf(y)), where we treat (0,1)2n as the product (0,1)n(0,1)n and - by this correspondence-write elements of (0,1)2n as ordered pairs (x,y) (where both x and y are elements of {0,1} ). (a) With F defined as above, define the function :(0,1)n(0,1)2n(0,1) by the rule (k,(x,y))=Fi(x,y)=(y,xFk(y)). Note that for any k{0,1}n, the function F3 is a permutation of the set {0,1}2n. It is clear that if F can be computed in polynomial time, then so can. Prove that if F can be computed in polynomial time, then so can the inverse of . To be precise, show that there is an efficient algorithm I so that I(k,(x,y)) ) outputs the (unique) pair (a,b) so that Fi(a,b)=(x,y). (b) Prove that even if F is a pseudorandom function, is not a pseudorandom function. (c) However, iterating this process a few times does indeed result in a pseudorandom functions that is, moreover, invertible (and hence a permutation). Specifically, consider the permutation obtained by composition as follows: 3:{0,1}3n[0,1}2n{0,1] where 3((k1,k2,k3),(x,y))=Fi1(Fi2(Fk3(x,y))). It is a fact that if F is pseudorandom then is a pseudorandom permutation (and, as pointed out above, the inverse of 3 can be computed efficiently given k1,k2,k3 ). Prove that two iterations are not enough. Prove that the analogous function 2 is not pseudorandom. (Hint: Consider the output of the function on the two inputs (1n,0n) and (0n,0n).)