Pseudo-Random Function families whose instances have full domain

Question

The GGM construction gives (PRF) pseudo-random function families whose instance's input's are binary strings of a single length.

I've convinced myself that one could get a PRF family whose instances have domain of all finite binary strings by taking a PRF for inputs of length $n$ and an independent PRNG seed, using the PRNG seed to take a value that is indistinguishable from being a primes chosen uniformly from $\; [2^{n-1},2^n) \;$, interpreting the input as a non-negative integer, reducing that integer mod the value from the PRNG, expressing the result as a binary string, and feeding that to the PRF instance.

(The PRF instance and PRNG seed could instead be the output of the PRNG on the key.)

However, looking at the construction, I see what would be much simpler and more efficient, and I think it would still be secure, although I don't understand the proof well enough to figure out if that can be suitably modified.

Does the following give a pseudo-random function family from
a pseudo-random generator that stretches by a factor of 3?

Let $G$ be the generator, and define $H_0,H_\#,H_1$ to return the first,middle,last $n$ bits of $G$'s output. $\;\;$ For all non-negative integers $n$ such that $\: n\lt \text{len}(x) \:$, $\:$ let $b_n$ be the $n$th bit of $x$. $\;\;$ $F_s(x)$ is then defined to equal $\; H_\#(H_{b_{\text{len}(x)-1}}(...(H_{b_2}(H_{b_1}(H_{b_0}(s)))))) \;$.

Answer 1

Here is a proof sketch of the security of your construction.

Let $G: \{0,1\}^k \to \{0,1\}^{3k}$ be the PRG and let $G_0, G_1, G_2$ denote the first, middle, and last third of the output of $G$.

Define the function $F_{x,m}$ as follows:

$\qquad F_{x,m}(y) = \begin{cases} rand & \mbox{ if } y<x \mbox{ in lex order} \\ G_m( rand ) & \mbox{ if } y=\epsilon \\ G_m( F_{x,b}(y') ) & \mbox{ if } y=y'b \\ \end{cases}$

Here $rand$ denotes a value chosen at random for each $(y,m)$, independent of everything else.

Now $F_{\epsilon,2}$ is your GGM construction instantiated with a random seed. Suppose we picture the GGM construction as a labeling of the edges and vertices of a binary tree. Each vertex is associated with a finite binary string. Each vertex labels its two outgoing edges $G_0(\ell), G_1(\ell)$ and labels itself $G_2(\ell)$, where $\ell$ is the value assigned to its incoming edge. Then $F_{x,2}$ is the result of having vertices $y < x$ assign their relevant labels totally randomly.

Fix an adversary $A$ with running time $p(\cdot)$, to which we give oracle access to a function of this form. We'll consider the sequence of hybrids $F_{\epsilon,2}, F_{0,2}, F_{1,2}, F_{00,2}, \ldots, F_{\omega,2}$, where $|\omega| > p(k)$. From $A$'s point of view, $F_{\omega,2}$ has output distributed identically to a totally random function.

If $x$ is the successor of $x'$ in lex order, then $F_{x,2}$ and $F_{x',2}$ differ only in one application of the PRG. Thus, successive hybrids are indistinguishable. However, we've proposed an exponential number of hybrids, so we are not yet done! Intuitively $A$ can only "notice" the changes in a polynomial-sized portion of the tree. We formalize this as follows:

Conditioned on the event that $A$ never queries its oracle on a string beginning with $x$, then $F_{x,2}$ and $F_{x',2}$ give identical output distribution. Let $q_x$ denote the probability that $A$ queries its oracle on such a string, and let $\delta(\cdot)$ denote the negligible security error of the PRG. Then we have:

$\qquad\Big|\Pr[A^{F_{x,2}}(1^k) = 1] - \Pr[A^{F_{x',2}}(1^k) = 1] \Big| \le q_x \delta(k)$

Then by a hybrid argument, we have:

$\qquad\Big|\Pr[A^{F_{\epsilon,2}}(1^k) = 1] - \Pr[A^{F_{\omega,2}}(1^k) = 1] \Big| \le \delta(k)\sum_x q_x$

The first expression involves $A$ with oracle access to the GGM function, and the second expression involves $A$ with oracle access to a random function. Now we bound the sum $\sum_x q_x \le p(k)^2$. Since $\delta(k) p(k)^2$ is negligible, the construction is a PRF.