In this note I review a number of technical points pertaining to PRFGs.

The syntax of attacks against function generators

Our definition of pseudorandom function generator aims to formalize the following idea: $\mathcal{F} = \{ F_k \}_k$ is a pseudorandom function generator if no efficient algorithm can distinguish elements of $\mathcal{F}$ from arbitrary functions.

To formalize this task we consider the experiment of giving a (uniform, i.e. Turing Machine) adversary $\mathcal{A}$ access to a function $f$ which is an element of either $\mathcal{F}$ or $\mathcal{H} = \{ f:\bit^n \to \bit^n \}$ and asking it to say which.

Obviously, in order for this distinguishing task to be non-trivial, however the function is provided as input to $\mathcal{A}$ must not disclose it's type. However there are many ways of specifying a function (e.g. apart from as an oracle) that are this generic, however there are important technical reasons to provide the function via an oracle.

A generic interface inappropriate for our setting

One way to fully specify $f$ would be to write out the list of values that define $f$, i.e. the entire set of tuples ${(x, f(x))}_{x \in \bit^n}$ on $\mathcal{A}$'s input tape. Let's consider why we don't take this formulation.

Writing out this complete table of values requires $n2^n$ bits. This introduces the following conflict concerning the runtime of $\mathcal{A}$.

• If we require that adversaries run in time polynomial in $n$, they are restricted to reading but a negligible fraction of their input. This (artificial) restriction rules out attacks that we believe to be possible in practice, and so is a weak notion of security.
• If we allow adversaries to run in time polynomial in the size of their input, this allows $\mathcal{A}$ to run in time exponential in $n$, admitting brute force attacks against the generator, making every function generator trivially insecure.

In the assignment context

Now I can point to bad examples from assignments. If you said

Run $\mathcal{A}$ with function $f$ as input

this can be interpreted as meaning 'write all of $f$ out on $\mathcal{A}$'s input tape', which, as discussed above, is a bad idea as it permits $\mathcal{A}$ to run in time exponential in $n$ (admitting $\mathcal{A}$ to mount brute-force attacks, trivializing the security condition by making all function insecure.

Concerning simulating a random function oracle

The following text appeared amongst many solutions:

Let $A$ be an algorithm that breaks the pseudorandomness as the function generator $F$. Let $A'$ be an algorithm that samples a random function $f:\bit^n \to \bit^n$ and runs $A^{f}(1^n)$.

We have to be careful what we mean about 'sampling a random function'. The natural interpretation of that statement is fix all $2^n$ values of $f$, which takes time $O(2^n)$. Such action is not allowed within a $poly(n)$ time simulation.

What must be done is sample $f$ lazily, i.e. only when $f$ is queried on $x$ do we expose $f(x)$ (which is to say, determine or fix the value of $f(x)$). If $\mathcal{A}'$ samples $f$ lazily, then it's simulation of $\mathcal{A}$ runs in time proportional to $t_{\mathcal{A}}$, and not $2^n$.