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.


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.

  • 1
    $\begingroup$ 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\}$. $\endgroup$ – Sasho Nikolov Oct 18 '12 at 17:23
  • $\begingroup$ This is probably one of the most helpful pieces of guidance I've gotten for this kind of issue. Thank you very much! $\endgroup$ – gfppaste Oct 19 '12 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.