[Solved]: Rigorous proof against pseudo random function

Problem Detail: 

I have the following problem:

Define the keyed function F as follows: On input k ∈ {0, 1}$^n$ and x ∈ {0, 1}$^n$ , Fk(x) = k ⊕ x.Rigorously prove that F is not a pseudorandom function.

How do I approach a proof against pseudorandomness for a keyed function? I don't know where to start with this one.

Asked By : gfppaste

Answered By : Ran G.

How to approach it? It's always the same answer - go back to the definitions.

the definition of PRF, talks about a family of functions $\{f_k\}$. The key $k$ just selects one specific function out of this big family.

Next, for $\{f_k\}$ to be a PRF family,the definition requires that any PPT algorithm $A$ will not be able to distinguish a member of the that family, from a really-random function (that is, a function sample randomly from all-the-possible-functions).

Since all the functions in your family have a very specific structure, you can easily built an algorithm $A$ that will always answer '1' if it's input function has the structure $f_k(x)=k\oplus x$, or otherwise, it outputs '0' (I let you complete the details). This $A$ is a distinguisher for that family-- for functions from this family it always answers 1, and for a random-function, it will answer '0' most of the times (say, it will answer '0' for at least half of those functions). Since such a distinguisher exists, the given family of functions is not pseudo-random.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6144