# Pseudo-Random Function families whose instances have full domain

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)))))) \;$.

-
I'm not sure exactley about how your construction works. But when I've read "infinite" (I mean about the tree size) I've seen some kind of error, the error is that in the GGM construction's proof they use the hybrid argument in order to prove the PRF property. The loss in the security factor is proportional respect to the size of the tree (this is the weakness of the hybrid argument). –  AntonioFa Dec 26 '11 at 20:28
I just edited to explain the construction. $\;\;$ I would imagine that one would show that for all positive integers $c$, the function's restriction to inputs of length at most $\: c+n^c \:$ was pseudo-random. $\;\;$ It would follow that the function itself its pseudo-random, since an efficient algorithm can only generate polynomially long inputs for the function. –  Ricky Demer Dec 27 '11 at 7:05

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.

-
(Sorry for taking so long to respond.) $\:$ How do we "bound the sum"? $\:$ Each $q_x$ is defined by giving $A$ access to a different oracle, so $A$ could conceivably find $x$ and query the oracle on it. –  Ricky Demer Dec 28 '11 at 23:45
$\sum_x \Pr[A \mbox{ queries an extension of } x]$ is at most the expected combined length of all the oracle queries. So the sum is at most $p(k)^2$ regardless of the oracle. You're right that the $q_x$ values depend on the oracle. To very formally address that issue, I think you'd have to more carefully define only a polynomial number of hybrids. –  mikero Dec 29 '11 at 2:33