# PRP, PRF change at next selection?

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

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.