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. 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) Nov 2 '15 at 4:52