Assume we have a pseudorandom function $f(\cdot)$ that maps an input to $\mathbb{F}_p$ where $p$ is a large prime number.

Assume $r_1$ and $r_2$ output of the pseudorandom function using two different keys.

Question: Are $r_1$ and $r_2$ computationally indistinguishable?


1 Answer 1


Computational indistinguishability is transitive, the proof can be found in these lecture notes. Informally speaking:

We have an advantage $\epsilon_1$ to distinguish distributions $X$ and $Y$, and we have an advantage $\epsilon_2$ to distinguish distibutions $Y$ and $Z$, and the triangle inequality gives us an advantage $\leq \epsilon_1 + \epsilon_2$ to distinguish $X$ and $Z$. Since both $\epsilon_1, \epsilon_2$ are negligible (to be more precise, negligible functions in some security parameter), their sum $\epsilon_1 + \epsilon_2$is also negligible.

For a pseudorandom function we know that it's indistinguishable from a random function, which is just a uniform distribution for every possible input. So both functions are indistinguishable from the same distribution, and by transitivity we get that they $f_{k_1}(.)$ and $f_{k_2}(.)$ are also indistinguishable.

Edit: This is only true for independent keys, thanks to Yehuda Lindell for pointing this out. The question states "different keys", which might not fulfill this requirement.

If you have dependent keys, then indistinguishability does not necessarily hold. Specifically, let $F$ be a pseudorandom function. Define $F'$ as follows: if the key $k$ is even then define $F'_k(x)=F_k(x)$; else, if $k$ is odd, then define $F'_k(x)=F_{k+1}(x)$. It is possible to prove formally (by reduction) that if $F$ is a pseudorandom function then so is $F'$. Now, consider the case that you are given $k_1,k_2$ with $k_2= k_1 + 1$. Then, with probability $1/2$ it holds that $k_1$ is even. In this case, it follows that $F'_{k_1}(x)=F'_{k_2}(x)$. Thus, $F'_{k_1}(x)\|F'_{k_2}(x)$ is not a pseudorandom string.

Under some related-key assumptions you could prove something, but this isn't standard. It's also probably beyond the scope of this question anyway.

  • 2
    $\begingroup$ This is only correct for independent keys. If they are not independent (and are just "different") then you cannot prove this. Furthermore, it's easy to come up with a counter-example. $\endgroup$ Commented Oct 5, 2016 at 20:16
  • $\begingroup$ ... but I still assume it's the correct answer to the question. $\endgroup$
    – Maarten Bodewes
    Commented Oct 5, 2016 at 21:57
  • $\begingroup$ @YehudaLindell "Furthermore, it's easy to come up with a counter-example", counter example for which case? for the independent key ? $\endgroup$
    – user153465
    Commented Oct 6, 2016 at 9:31
  • $\begingroup$ Counterexample fora different but not independent key. $\endgroup$ Commented Oct 6, 2016 at 9:33
  • $\begingroup$ @MaartenBodewes I agree that this is the answer but please emphasize that the keys must be independently chosen. $\endgroup$ Commented Oct 6, 2016 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.