2
$\begingroup$

How to construct a pseudorandom function $PRF$ with the following property:

Probability that $PRF(k_1,i)=PRF(k_2,i)$ is negligible, for all keys $k_1,k_2$ such that $k_1\neq k_2$

Does the PRF with the above property have to be Pseudorandom function tribe ensembles mentioned here or it can be any PRF with sufficiently large output range.

$\endgroup$
  • $\begingroup$ You have to clarify the situation. You want the probability to be negligible: probability over what random event? It seems like all the inputs to the PRF are fixed arbitrarily and can presumably depend on the choice of PRF. In that case the probability that the outputs are equal is either 0 or 1. $\endgroup$ – Mikero Feb 2 '17 at 16:57
2
$\begingroup$

A dual PRF is one in which either arguments to the PRF can be interpreted as the key. In other words, for random $k$, the function $F(k,\cdot)$ is indistinguishable from a random function. And for random $x$, the function $F(\cdot,x)$ is indistinguishable from a random function.

If $F : \{0,1\}^\kappa \times \{0,1\}^\kappa \to \{0,1\}^\ell$ is a dual PRF then the following is true:

For all $k_1 \ne k_2$, $\displaystyle\Pr_{i \gets \{0,1\}^\kappa}\Big[ F(k_1,i) = F(k_2,i) \Big]$ is negligibly close to $1/2^\ell$.

In line with my comment above, something has to be chosen randomly if you want a deterministic function to satisfy some security property (without a random oracle assumption). This property remains true even if $i$ becomes public, but it does need to be chosen uniformly.

To see this, just apply the PRF property of $F(\cdot,i)$ (here instantiated with a random key $i$) and observe that $\Pr[ R(k_1) = R(k_2) ] = 1/2^\ell$ for a random function $R$ when $k_1 \ne k_2$.

Of course, dual PRF is not a completely standard assumption. But it is the basis for HMAC, so if you're comfortable with HMAC then you must be comfortable with assuming certain hash functions to be dual PRFs.

Also, if $k_1, k_2$ are chosen independently/uniformly, and $i$ is chosen adversarially, you get a low probability of collisions just from the regular PRF property.

$\endgroup$
  • $\begingroup$ Thank you very much for the answer. Regarding the last paragraph of the answer, would anything change if we define $F$ as : $F: \{0,1\}^{k}\times \{0,1\}^m \rightarrow F_p$, where $p$ is a large prime number and $|p|=l$ and $l$ is security parameter. $\endgroup$ – user153465 Feb 5 '17 at 15:28
  • $\begingroup$ Nothing should depend on how the output domain is interpreted. Only property of output domain that was used in this argument is its size. $\endgroup$ – Mikero Feb 5 '17 at 18:55
2
$\begingroup$

Depending on what you consider an acceptable approach, you could get there by having a random-looking function from your PRF domain to a prime-order cyclic group, and then use the permutation $x \mapsto x^k$ on the group.

Under reasonable assumptions and choice of group, this is a PRF. And since the key-dependent part is a permutation, two keys will never map the same $i$ to the same function value.

So this construction satisfies your requirements, but it is not a tribe ensemble.

$\endgroup$

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.