# Pseudorandom functions: how are functions stored?

I am wondering about the setup for testing if a function family is pseudorandom. We step into a room, and query the black box with $x$, which yields $f(x)$, etc... We don't know if $f$ is a random function, or if it comes from some preset function family $F$. In the latter case, what assumptions are made about the functions in $F$? Is it enough for each $f$ in $F$ to be listed as a table in the black box, so that $f: \{0,1\}^n \to \{0,1\}^n$ is listed as a table with $2^n$ entries? What if $f$ is described by some function of a polynomial with coefficients that are exponential in $n$? What are the restrictions on the functions in the function family $F$, if any?

For the definition of pseudorandomness, the family $F$ of functions can be any set of functions at all. But typically we take it to be a set where each function can be described by a rather short key/seed, and where one can efficiently compute the function output given the input (and the key). This is because we want the family $F$ to represent functions that we can randomly choose from and use in real life.
For example, $F$ could be the set of functions AES$_k$, taken over all 128-bit strings $k$ (where AES$_k$ denotes the AES block cipher with key $k$). Notice that there are "only" $2^{128}$ functions in this family, which is much less than the number of functions mapping 128 bits to 128 bits (which is $(2^{128})^{2^{128}}$).
PS: Often random functions will just generate a random sequence based on an initial seed value; you don't have to pass a parameter $x$ each time you call the function. While such random functions do exist, the box in your description somehow reminds me of a hash function (or a random oracle).