Increasing the stretch of a PRG

fgrieu

6/21/24, 3:31 PM

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 (3^rd 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.

1 + 1

pseudo-random-generator

fgrieu

6/22/24, 10:30 AM

The [Expansion of a PRG](https://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf#page=92) 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.

Score:1

Crypto

Hhan

6/22/24, 4:31 AM

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.

+ 3

fgrieu

6/22/24, 10:03 AM

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.

Hhan

6/22/24, 2:06 PM

@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.

Hhan

6/22/24, 2:09 PM

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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Increasing the stretch of a PRG

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.