# Is a PRF pairwise independently and uniformly distributed

The notation of a strongly universal function was introduced by Wegman and Carter here and it states, that such a function has to be pairwise independently and uniformly distributed. I would like to know if a PRF also has this property and how the relation looks like. I would argue, that a random function has those properties by definition, and because a prf can only be distinguished from a random function with negligible probability, it therefore also has those properties, but I am unsure, whether the reasoning is correct.

• Pseudorandom functions are computationally indisintuighable from truly random functions. A random function will satisfy unifomity and pairwise independence. So those properties also hold (compuationally) for PRFs, i.e. if one could efficiently tell if they hold or not, then one could distinguish the PRF from a random function. Dec 12, 2023 at 19:57

If what you mean is to consider a set of independently chosen PRFs $$f_i:\{0,1\}^n\rightarrow \{0,1\}^m,$$ $$i=1,\ldots,M$$ and ask whether the pairwise independence and uniformity will hold, yes it will by definition for any $$i\neq j.$$ All you need to do is to assume each $$f_i$$ is uniformly chosen from the collection of all functions between the domain and the range and use properties of independence.
If the $$f_i$$ are not independently and uniformly chosen, this won't hold.
• A PRF can be a family or a single function in the same way a universal hash can be a family or a single function. Either they are functions that take 2 arguments, or else the first argument (key) indexes a particular element of the family (of 1-input functions). I don't understand the relevance of comparing two different PRFs. The OP is clearly asking about the distribution of $(F(K,X), F(K,X'))$, with $X \ne X'$ and over random choice of $K$, as in the definition[s] of [strong] universality. Dec 12, 2023 at 17:17