# PRF that can be distinguished after $k$ queries?

In adaptive attacks, if we design poorly, adversary can modify his queries and break the given pseudo random function (that is being able to distinguish it from uniform randomness).

Is there a poor way to design a PRF such that in one round of query, the adversary cannot distinguish but in two rounds the adversary can?

How about adversary failing to break at $k-1$ queries but breaking at $k$th query?

• "generator (that" $\: \mapsto \:$ "function family (that" $\;\;\;$ ? $\;\;\;\;\;\;\;\;$ – user991 Nov 2 '15 at 4:23
• ???? what are you saying? – user28792 Nov 2 '15 at 4:32
• Should $\:$ "generator (that" $\:$ be replaced with $\:$ "function family (that" $\;\;\;$ ? $\;\;\;\;\;\;\;\;$ – user991 Nov 2 '15 at 4:34
• should it be? I dont know but I am thinking this formulation is valid but why do you say so? – user28792 Nov 2 '15 at 4:42
• What would "queries" mean for a pseudo random generator? $\;$ – user991 Nov 2 '15 at 4:44

A $k$-wise independent hash family has the property that the joint distribution of $h(x_1), h(x_2), \ldots, h(x_k)$ is uniform when $h$ is chosen uniformly from the family (and $x_i$'s are distinct). Such families exist unconditionally (for fixed $k$), are efficient, and satisfy the condition you give.
The simplest example of a 1-universal function is $F(k,x) = x \oplus k$. Clearly the output of $F$ on one point is uniform (it's a one-time pad) but with two queries $F$ can be easily distinguished from a random function.
• Do you know how to break one-time pad when the same key is used twice? This is the same problem. For the general case, you don't need adaptive queries to distinguish a $k$-wise independent function (family) from random. Any $k+1$ distinct (static) queries will do. – Mikero Nov 2 '15 at 4:37
• If you are looking for a function that is strong against nonadaptive queries and single adaptive queries (whatever a single adaptive query means), but weak against two adaptive queries, how about a random involulation (that is, a function that is constrained by $F(k, F(k,x)) = x$. For functions that can take $k-1$ adaptive queries, generalize this to a function for which $F^k(x) = x$ (mostly, if $k$ isn't a divisor of the range, we can do this only most of the time) – poncho Nov 2 '15 at 4:52