This question is related to my previous question “Are two outputs of a PRF computationally indistinguishable when using two different keys??”, but in this question the keys are related.

Assume $c_i$ is a counter: $c_i \in \{0,1,..., n\}$. Also, let $k$ and $k'$ be two independent keys. Let $f(.)$ be a pseudorandom function. Let $x$ be an input (or fix value).

  • When $c_i=0$ : $\ z_i=f(k,x)$

  • When $c_i \in \{1,2,... n\}$: $\ z'_i=f(k+k'_i,x)$, where $k'_i=f(k',c_i)$.

Question: Are $ z_i$ and $z'_i$ computationally indistinguishable?


They are indistinguishable because the keys are related only by a value that random from the distinguisher's point of view. More formally, you can argue that your distribution is indistinguishable from one in which all PRF keys are chosen independently. Note that this is very sensitive to the fact that the distinguisher can't query $f(k',\cdot)$.

What you described is this distribution induced by the following process (I will rename $k$ to $k_0$). It is easier to assume that the $x_i$'s are just some arbitrarily fixed values. Even if they are chosen adaptively, it doesn't substantively change the nature of the argument.

Process 0:

  • $k_0,k' \gets \{0,1\}^\lambda$
  • for $i \in \{1,\ldots,n\}$: set $k_i = k_0 + f(k',i)$
  • output $f(k_0, x_0), f(k_1, x_1), \ldots, f(k_n, x_n)$

This process uses $k'$ only as a key to $f$, and nowhere else. The PRF security guarantee is that it has a negligible effect on the output to replace distinct outputs of $f(k',\cdot)$ with randomly chosen values. The resulting process is:

Hybrid process 1:

  • $k_0 \gets \{0,1\}^\lambda$
  • for $i \in \{1,\ldots,n\}$: choose $r_i \gets \{0,1\}^\lambda$
  • for $i \in \{1,\ldots,n\}$: set $k_i = k_0 + r_i$
  • output $f(k_0, x_0), f(k_1, x_1), \ldots, f(k_n, x_n)$

Observe that this hybrid process uses $r_i$ only as a one-time pad to mask $k_0$ (here I'm assuming "+" refers to a group operation like XOR). Since each $r_i$ is used only once in this way, and nowhere else, it means each $k_i$ is distributed uniformly. So we can simplify (with no effect on the output distribution):

Hybrid process 2:

  • $k_0 \gets \{0,1\}^\lambda$
  • for $i \in \{1,\ldots,n\}$: choose $k_i \gets \{0,1\}^\lambda$
  • output $f(k_0, x_0), f(k_1, x_1), \ldots, f(k_n, x_n)$

Now each $k_i$ is chosen uniformly/independently, and used only as a PRF seed. From here you can apply the PRF security and replace each term $f(k_i, x_i)$ with a random value. Technically speaking you would perform $n+1$ hybrids to do this, one for each $k_i$ to which you are applying the PRF security guarantee. The final result will be a process that outputs $n+1$ uniformly chosen values.

For an exercise, think carefully about what step of the argument goes wrong when the adversary is also able to query $f(k',\cdot)$.

  • $\begingroup$ Thank you very much for the answer. Is that a strong assumption that the adversary cannot query $f(k',.)$? $\endgroup$ – user153465 Oct 6 '16 at 22:38
  • $\begingroup$ It is not an "assumption" -- it is part of the system that you are trying to model. Is is true that the only place $k'$ is used in your system is as a PRF key in the specific context of your question? In my answer, $k'$ is a "locally scoped" variable to this process. Does that match up with the system you have in mind? $\endgroup$ – Mikero Oct 6 '16 at 22:53
  • $\begingroup$ Yes, that's right. $k'$ is used only as a key to generate some pseudorandom values and it's picked independently. $\endgroup$ – user153465 Oct 6 '16 at 22:56

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.