2
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ I think you're misreading the question. The proposition is $\forall i, 0\leq i \leq n: PRF(k_1, i)\neq PRF(k_2,i)$; note the universal quantifier. In English (as a logically equivalent negated existential): "there exists no message such that the two two randomly selected members of the family produce the same result for that message." $\endgroup$ – Luis Casillas Jan 26 '17 at 18:30
  • $\begingroup$ Perhaps. I've taken the liberty of interpreting the question as intending to express whether the inequality holds for any choice of i, instead of every choice. Clearly the probablity is nearly $e^{-x}$ in the case you describe (assuming x is the codomain size factor), and any deviation from this results in something that is not a PRF at all. $\endgroup$ – Selfless Sociopath Jan 26 '17 at 21:21
  • $\begingroup$ @LuisCasillas Thanks, I've updated my answer to address this issue. $\endgroup$ – Selfless Sociopath Jan 26 '17 at 23:05
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It might be worth noting explicitly that, if the probability of observing a collision between two randomly chosen instances of the PRF differs from $\left(1-\frac1t\right)^n$ by a non-negligible amount, then the PRF is trivially distinguishable from a random function (by comparing it with another random instance of the same PRF) and thus not a secure PRF in the first place. $\endgroup$ – Ilmari Karonen Jan 26 '17 at 19:50

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.