Are two outputs of a PRF computationally indistinguishable when using two different keys? 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?
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.