# If G is a PRG, is G' necessarily a PRG?

Given:

• A function $$G: \{0,1\}^{3n} \to \{0,1\}^{6n}$$ which is known to be a secure Pseudorandom Generator (PRG).
• A derived function $$G'(x_1 \| x_2) = G_b(x_1\|0^n\|x_2), \text{ where } x_1, x_2 \in \{0,1\}^n.$$

Question: Can we assert that $$G'$$ is also a PRG?

Observations:

• $$G'$$'s output maps to a specific subset of $$G$$'s outputs, specifically when the input has the predictable form $$x_1\|0^n\|x_2$$.
• A PRG's output should be indistinguishable from truly random strings, even with structured input.
1. Constructive argument: If ( G ) is secure, its output should be indistinguishable from a random string, even with the ( 0^n ) segment in the seed.
2. Counterexample: The introduction of the ( 0^n ) structure might make ( G' )'s input distribution not uniformly random, which is a requirement for a PRG

What are your thoughts? Is ( G' ) still a PRG given our knowledge of ( G )? Or does the predictable seed invalidates it being a PRG? I've explored both angles but haven't reached a definitive stance. Would love to hear your thoughts on this.

• Thank you for the warm welcome to Crypto.SE and the edits. I've gone through them and truly appreciate the use of LaTeX to enhance the clarity of the mathematical notation Oct 2 at 18:22
• Your observations are good and direct showing is usualy hard way. Assume $G'$ is not a secure PRG and write a distinguisher and use it to show that $G$ is also not a secure PRG? I leave some of the edits as an exercise for you :). Is this some HW? Oct 2 at 18:24
• Proof by reduction, is that what you're saying? But wouldn't introducing the 0^n make the distribution not random and hence it won't be a PRG? And yes, it is a part of a HW assignment Oct 2 at 18:28
• Proof by contrapositive. Oct 2 at 18:29
• Got it! I appreciate your guidance! Oct 2 at 18:30