# Rigorous proof against pseudo random function

I have the following problem:

Deﬁne 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.

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.
• some details for the benefit of OP: algorithm A has to be efficient, and all you need is that it always (or with high probability over the choice of a random $k$) answers 1 given oracle access to $f_k$ (i.e. it does not have a description of $f_k$ but can query it for any $x$), and answers 1 with probability close to 0 when given access to a function $f$ picked uniformly at random from all functions $f: \{0, 1\}^n \rightarrow \{0, 1\}$. – Sasho Nikolov Oct 18 '12 at 17:23