Difference between Pseudorandom Function vs randomly chosen function

Question

I am currently going through a course in cryptography. In this, I stumbled upon Pseudorandom Functions. I got a little idea of Pseudorandom Generators which map an input string (key) to an extended string. However, I do not understand the pseudorandomness in case of a function.

In the book Introduction to modern cryptography by Katz and Lindell, I found this:

Since the notion of choosing a function at random is less familiar than the notion of choosing a string at random, it is worth spending a bit more time on this idea. From a mathematical point of view, we can consider the set $\operatorname{Func}n$ of all functions mapping $n$-bit strings to $n$-bit strings; this set is finite (as we will see in a moment), and so randomly selecting a function mapping $n$-bit strings to $n$-bit strings corresponds exactly to choosing an element uniformly at random from this set.

How large is the set $\operatorname{Func}n$? A function $f$ is exactly specified by its value on each point in its domain; in fact, we can view any function (over a finite domain) as a large look-up table that stores $f(x)$ in the row of the table labeled by $x$. For $f_n\in\operatorname{Func}n$, the look-up table for $f_n$ has $2^n$ rows (one for each point of the domain $\{0,1\}^n$) and each row contains an $n$-bit string (since the range of $f_n$ is $\{0,1\}^n$). Any such table can thus be represented using exactly $n\cdot2^n$ bits.

Moreover, the functions in $\operatorname{Func}n$ are in one-to-one correspondence with look-up tables of this form; meaning that they are in one-to-one correspondence with all strings of length $n\cdot2^n$.

We conclude that the size of $\operatorname{Func}n$ is $2^{n\cdot2^n}$ . Viewing a function as a look-up table provides another useful way to think about selecting a function $f_n\in\operatorname{Func}n$ uniformly at random. Indeed, this is exactly equivalent to choosing each row of the look-up table of $f_n$ uniformly at random. That is, the values $f_n(x)$ and $f_n(y)$ (for $x\neq y$) are completely independent and uniformly distributed.

Coming back to our discussion of pseudorandom functions, recall that we wish to construct a keyed function $F$ such that $F_k$ (for $k\gets\{0, 1\}^n$ chosen uniformly at randomly) is indistinguishable from $f_n$ (for $f_n\gets\operatorname{Func}n$ chosen uniformly at random). Note that the former is chosen from a distribution over (at most) $2^n$ distinct functions, whereas the latter is chosen from a distribution over all $2^{n\cdot2^n}$ functions in $\operatorname{Func}n$. Despite this, the "behavior" of these functions must look the same to any polynomial-time distinguisher.

Can anyone please explain me this concept in easier terms?

Answer 1

Random function -- function $F$, that is selected randomly from the set $Func$ of all possible functions (with given domain and range).

Pseudo-random function --- family $\{F_k\}$ of functions, that is indexed by the parameter $k$ (which serves as a number). It is pseudo-random, because if someone picks $k$ secretly and lets you interact with $F_k$, it should look like you are working with a random function, whereas in fact it is chosen from a much smaller set, not from the set of all possible functions.

Answer 2

The main conceptual point is: Ideally, in cryptography, one would often like to use a random function as a building block. However, these are very unhandy (as the text you copied elaborates), since generally, the only way to store an arbitrary function is as a lookup table, which becomes huge very quickly. Therefore, one tries to find a more practical method to obtain somewhat random functions that are effectively just as good and require far less effort to generate and transmit. This is formalized in the concept of a pseudorandom (family of) functions, which requires that an attacker can not efficiently observe any significant difference between a function taken at random from either this family or the set of all functions. Such families are designed in a way that permits easy generation, transmission and use of any specific member, for example as a single keyed function.

Answer 3

I assume you're already familiar with pseudorandom generators. A PRG takes a short random seed and generates a long pseudorandom string. You can extend a PRG using a simple output-feedback construction, to achieve a PRG with any polynomial output length.

But can you ask for even more? Can you take a short random seed and generate an exponentially long pseudorandom string? At this point, we must clarify what it means for a polynomial-time computation to "generate" an exponentially long string, and for a polynomial-time distinguisher to take such a long string as input. Polynomial time is not enough for either of these activities.

In light of those problems, perhaps it would make more sense to provide random access to this exponentially long string. When you generalize the definition of PRGs to a random-access setting, you get exactly the PRF definition. Given a short random seed $k$, we don't explicitly generate a long pseudorandom string; instead, we need to provide only random access to it. Think of the PRF syntax $F(k,i)$ as computing the $i$th block of the huge string induced by $k$ via $F(k,0)\| F(k,1) \| \cdots$. This huge object should be indistinguishable from a huge truly random string, when accessed through this random access interface.

Answer 4

Random function: (Pseudo)randomly pick a function from the set of all possible functions mapping an input to an output, where the input and output are the lengths/types you want.