Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Assume we have a pseudorandom function: PRF(.)
We want the following property holds with a high probability:
$\forall i, 0\leq i \leq n: PRF(k_1, i)\neq PRF(k_2,i)$
where $k_1$ and $k_2$ are two random keys picked independently.
Question 1: What is the pseudorandom function with the above property called in the literature?
Question 2: Is there any paper using the above pseudorandom function?
The question seems that it could be implying that you actually intended to ask about probability of any given index not colliding, as opposed to the probability of every index simultaneously not colliding. If this is the case, then the answer is trivial: Two outputs of any PRF, even at the same index, are independent random variables by definition and therefore collide with probability $\frac{1}{n}$.
However, in the case that you really do mean the universal notion, the situation is just slightly more involved: Any PRF with an output size $a$ (in bits) and an input size $b$ has this property with probability approximately $1-2^{a-b}$.
To see this, let $\rho$ denote the probability that the desired property holds, and take the codomain to be of size $\alpha n$ where $\alpha$ is a constant.
$$\rho = \Pr(\forall i \in [0, n]: PRF(k_1, i)\neq PRF(k_2,i))$$ Assuming the values are i.i.d: $$\rho = \Pr(PRF(k_1,i) \neq PRF(k_2,i))^{n+1}$$ Assuming the values are uniform: $$\rho = \left(1-\frac{1}{\alpha n}\right)^{n+1}$$ Taking the limit as $n\to\infty$: $$\rho \approx e^{-1/\alpha}$$ Which is within 5% of the true value when $n \geq 32$ and $\alpha \geq 1$. We assume $\rho = 1-\frac{1}{z}$ and solve for $\log_2\alpha$, which is by definition the number of output bits minus the number of input bits: $$e^{-1/\alpha} = 1-\frac{1}{z}$$ $$\alpha = \left(\log\frac{z}{z-1}\right)^{-1}$$ $$\log_2\alpha = -\log_2\log\frac{z}{z-1}$$ Which is always within half of one bit to the true value, as long as $z \leq e^n$. We simplify again with another convenient approximation: $$\log_2\alpha \approx \log_2 z$$ Which is at worst one half bit below the true value. Since the probability of your condition holding is determined by $z$, and $\alpha$ is the ratio between the cardinalities of the output and input domains, the probability of your condition holding is approximately proportional to the size of the output domain divided by the size of the input domain. $\square$
We want the following property holds with a high probability:
$\forall i, 0\leq i \leq n: PRF(k_1, i)\neq PRF(k_2,i)$
You don't specify the sizes of the key space or codomain of the PRF. The latter in particular is relevant; let's call $t$ (for "tag") the size of the PRF's codomain. Modeling the PRF family as random functions, for any specific choice of $i$, the probability that the two functions collide is:
$$Prob\big[PRF(k_1, i) = PRF(k_2,i)\big] = {1\over{t}}$$
Negating this proposition, we get:
$$Prob\big[PRF(k_1, i) ≠ PRF(k_2,i)\big] = {1 - {1\over{t}}}$$
Now the problem is your universal quantifier: you're asking that there be no collision for any choice of $i \in [0, n]$. This means that we just need to find one colliding choice of $i$ to falsify it. So you're asking for the probability of this conjunction of independent events:
$$PRF(k_1,i_0) ≠ PRF(k_2,i_0) \land \dots \land PRF(k_1,i_n) ≠ PRF(k_2,i_n)$$
...which is the product of the probabilities of the conjuncts. Therefore:
$$Prob\big[\forall i, 0\leq i \leq n: PRF(k_1, i)\neq PRF(k_2,i)\big] = \left({1 - {1\over{t}}}\right)^{n+1}$$
This probability obviously falls exponentially as $n$ gets bigger. But you want a "pseudorandom" function that "maximizes" that probability. You didn't specify precisely what you mean by maximize, but I'd suggest that a function for which the probability doesn't go down exponentially with $n$ may not be pseudorandom. A function like what you're looking for does not behave like a random function, at least not for large values of $n$.
For small values of $n$, on the other hand, you may well find the probability high enough to your liking that a pseudorandom function is OK.
