For the given construction not all secure PRG gives a secure PRG

Megha

12/24/23, 2:21 PM

Let $G:\{0, 1\}^n \to \{0, 1\}^m$ be a PRG. We define another PRG $G_0 : \{0, 1\}^n \to \{0, 1\}^m$ as follows: $G_0(s) = G(s) \oplus (0^{m−n}\mathbin\|s)$. Can there exists a secure PRG $G$ for which $G_0$ is insecure?

The question asks me to prove that such a PRG exists. But I am not sure how. Primarily I was thinking if the PRG $G$ keeps last $m-n$ bits of its output constant, the $G_0$ will not be secure. But in such case $G$ is not secure as well, when $m-n > 1$. Can someone please give me any hint on this problem? Thank you.

0 + 7

pseudo-random-generator

fgrieu

12/24/23, 3:37 PM

Perhaps a counterexample $G$ can be built as a Feistel/Luby–Rackoff cipher with key $s$ applied to a constant, and crafted such that the $\oplus (0^{m−n}\mathbin\|s)$ undoes the last round.

Maeher

12/24/23, 7:54 PM

Remember that it's perfectly fine for a PRG to output part of the seed in plain, as long as it's not otherwise used.

Megha

12/25/23, 8:40 AM

@fgrieu - I could not catch your hint properly. In $\oplus (0^{m-n}||s)$, s is the seed of the PRG. If I take the Luby-Rackoff cipher with key s, as the PRG G, then the seed s in the XOR is not same as the key of the PRP. Then how can this XOR undo the last round?

Megha

12/25/23, 8:46 AM

@Maeher - I have one thing to be clarified. A PRG can remain secure even if it outputs a part of the seed in plaintext. But if it outputs the entire seed in plaintext, then it is not secure - right? Because in that case, the seed can be stripped off and G can be calculated on that. Thereby it can be distinguished from a TRG with probability 1. Am I correct?

Maeher

12/25/23, 4:02 PM

Yes, that is correct.

Geoffroy Couteau

12/27/23, 10:23 PM

You do not need to output the full seed as part of the PRG output to build a counter-example: in fact, adding a single bit of the seed to the output suffices to get a counter example. I'll let you work out the details :)

Megha

12/29/23, 9:01 PM

Thanks for all the hints. I have solved the problem.

Elon Musk

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

EN: For the given construction not all secure PRG gives a secure 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.