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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – lamontap
    Dec 12, 2023 at 19:57

1 Answer 1


A PRF is a single function. The definition of strongly universal has to do with a family of functions.

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.

  • $\begingroup$ Thank you! If the PRFs are keyed and the keys are chosen uniformly random and independently, then are the PRFs also independently and uniformly chosen? $\endgroup$
    – Titanlord
    Dec 12, 2023 at 16:49
  • 4
    $\begingroup$ 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. $\endgroup$
    – Mikero
    Dec 12, 2023 at 17:17
  • $\begingroup$ @Mikero Exactly. The difference between universal and strongly universal is based on the number of elements considered. But for strongly universal, I can't quite see the difference to a PRF, where an adversary has multiple oracle calls per definition. Can you explain it better? $\endgroup$
    – Titanlord
    Dec 13, 2023 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.