1
$\begingroup$

Consider a function $G:\{0,1\}^*\to\{0,1\}^*$ with output size double it's input size, that is $\forall x\in\{0,1\}^n,\ |G(x)|=\ell(n)=2n$. Assume $G$ is a PRG in the sense of Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography (3rd edition); that is meeting the Pseudorandomness criteria:

For any PPT Algorithm $D$, there is a negligible function $\mathsf{negl}$ such that $$\bigl|\Pr[D(G(s))=1]-\Pr[D(r)=1]\bigr|\le\mathsf{negl}(n)$$ where the first probability is taken over uniform choice of $s\in\{0,1\}^n$ and the randomness of $D$, and the second probability is taken over uniform choice of $r\in\{0,1\}^{\ell(n)}$ and the randomness of $D$.

Now define $G':\{0,1\}^*\to\{0,1\}^*$ by $G'(x)=G(x)_{[0,n)}\mathbin\|G(G(x)_{[n,2n)})$, where $y_{[u,v)}$ is the substring of bitstring $y$ starting at bit $u$ and ending before bit $v$. Otherwise said, $G'$ runs $G$, then replaces the second half of it's output by the output of a second run of $G$ with input said second half. If follows $\forall x\in\{0,1\}^n,\ |G'(x)|=\ell'(n)=3n$.

Can It be proven that $G'$ is a PRG, and how?


Intuitively, that holds for PRGs used in practice. Perhaps the proof is by contraposition, constructing $D$ to break $G$ from hypothetical $D'$ that breaks $G'$, and from $G$, as $D(y)=D'(y_{[0,n)}\|G(y_{[n,2n)})$ where $n=|y|/2$. But the probability computation bugs me.

Inspired by this more complex question.

$\endgroup$
1
  • $\begingroup$ The Expansion of a PRG section in Rafael Pass and Abhi Shela's a Course in Cryptography deals with this (except for expansion by 1 bit, rather then doubling). It uses the hybrid argument (and I struggle with that). I wonder if the construction of $D$ from $D'$ in the question's butlast paragraph can be proven rigorous. $\endgroup$
    – fgrieu
    Jun 22, 2023 at 10:30

1 Answer 1

1
$\begingroup$

I believe the standard hybrid argument can resolve this; we may use the contraposition to show this, but I think the direct hybrid argument is more intuitive. Indeed, this iterative application of PRGs is the primary motivation of the GGM PRF construction. Let me describe the security proof.

For simplicity, we write $G(x)=G_0(x)\|G_1(x)$ where each $G_b$ denotes the first or last $n$ bits of the PRG output. We can write $G'(x)=G_0(x)\|G(G_1(x))$. Also, we fix $n$ and write $\epsilon(G)$ be the advantage of the PRG $G$ that is ${\sf negl}(n)$.

In the first hybrid $H_0$, the adversary is given $$H_0:G_0(x)\|G(G_1(x))$$ for random $n$-bit string $x$, which is exactly the $G'(x)$ in our real PRG security game.

In the next hybrid $H_1$, the adversary is given $$H_1:y\|G(z)$$ for two random $n$-bit strings $y,z$. In the adversary's view, the difference between $H_0$ and $H_1$ is bounded by $\epsilon(G)$ that is the advantage of the original PRG $G$, since we changed $G(x)=G_0(x)\|G_1(x)$ into random $y\|z$.

Finally, we consider the hybrid $H_2$ where the adversary is given truly random $3n$-bit string $$H_2:y\|w$$ for $n$- and $2n$-bit strings $y,w$, respectively. Between $H_1$ and $H_2$, we changed $G(z)$ into $w$ so that the adversary only can notice the difference with probability $\epsilon(G)$.

In summary, the adversary notices the difference between $H_0$ and $H_2$ with probability at most $2\epsilon(G)$ that is negligibly small. I think the original question also can be proven similarly.

$\endgroup$
3
  • $\begingroup$ The part I have some trouble with is going from $H_0$ to $H_1$. In "the difference between $H_0$ and $H_1$ is bounded by $\epsilon(G)$ that is the advantage of the original [outer] PRG $G$", we have to invoke that the inner $G$ in $y\mathbin\|G(z)$ that an adversary receives can not increase the achievable advantage compared to receiving $y\mathbin\|z$. Which seems to require a theorem, or another ad absurdum reasoning that if the inner $G$ increased the achievable advantage, we could make that inner $G$ part of a better adversary. Also the "hybrid argument" is not per K&L's formalism. $\endgroup$
    – fgrieu
    Jun 22, 2023 at 10:03
  • 1
    $\begingroup$ @fgrieu-onstrike I also struggled with that part long ago, but I got used to it and forgot this subtlety. Suppose you have an efficient algorithm $A$ that distinguishes $F(G(x))$ for uniform $x$ from $F(y)$ for uniform $y$ for an arbitrary efficiently computable function $F$ (that can be randomized). In that case, you can distinguish $G(x)$ from $y$ by another algorithm $B_A$ that given input $a$, computes $F(a)$ and then runs $A$ on it. You can easily see that the advantage of $B_A$ is exactly the same as one of $A$, and $B_A$ is efficient as long as $A$ and $F$ are. $\endgroup$
    – Hhan
    Jun 22, 2023 at 14:06
  • 1
    $\begingroup$ This says that as long as we apply an efficient computation to two distributions, the advantage of distinguishing them only decreases. (cf. the statistical distance decreases by an arbitrary computation, without the requirement of efficiency) In our case, $F(a\|b)=a\|G(b)$, which is efficiently computable. $\endgroup$
    – Hhan
    Jun 22, 2023 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.