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)=koplus 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
