This is probably a silly question, and similar question was asked before; but I can not figure out what actually is PRP/PRF. For example, it is commented that:

A Pseudo Random Function is a function that is indistinguishable from a function selected at random from the set of all functions with the same domain and value set.

Now, does that mean, everytime we speak of a PRF; we randomly choose a new function from all such possible functions? Or, after we have chosen the function, we use it for sometime?


1 Answer 1


A PRF is indistinguishable from a function sampled at random from the set of all functions with the same domain and range. But that does not means that you need to pick a function at random across all possible functions to get a PRF. That can clearly not work: a random function has, with very high probability, a circuit of exponential size. So you cannot sample such a function in polynomial time, yet alone actually evaluate it on an input.

Sampling a PRF will be done by sampling it from a much smaller set, that contains only functions with a bounded polynomial size. Think of a PRF as a family of functions $\{f_k\}_{k \in \{0,1\}^\lambda}$, and sampling a function from this set is done by simply sampling its index $k$ - i.e., the key of your PRF. Note that even though they are easy to sample, there are $2^\lambda$ such $f_k$, so it is not implausible that an adversary that runs in polynomial time cannot distinguish a sample from this "small" (but still exponential-size) family, from a sample from the set of all functions. Note also that the adversary does not get the functions themselves when he tries to distinguish the set they have been sampled from - rather, he gets black-box access to the input-output behavior of the function.

Then, once you sample a single PRF key, you can use the same function for arbitrary polynomially many evaluations, since the function remains indistinguishable from a random function for the adversary, even if he gets to see an arbitrary polynomial number of evaluations of the function.


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.