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?

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

| improve this answer | |
  • $\begingroup$ What will the adversaries adaptive query be? is it x+k? $\endgroup$ – user28792 Nov 2 '15 at 4:33
  • $\begingroup$ 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. $\endgroup$ – Mikero Nov 2 '15 at 4:37
  • $\begingroup$ same key k is used twice for x and y? you get x+k and y+k. I am looking for something adaptive $\endgroup$ – user28792 Nov 2 '15 at 4:41
  • 1
    $\begingroup$ 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) $\endgroup$ – poncho Nov 2 '15 at 4:52
  • $\begingroup$ @poncho I tried that for something explicit but unsuccessful could you elaborate your writeup? $\endgroup$ – user28792 Nov 2 '15 at 4:53

Your Answer

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