• 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?


  • $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.

  • $\begingroup$ 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 $\endgroup$
    – Steven
    Commented Oct 2, 2023 at 18:22
  • $\begingroup$ 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? $\endgroup$
    – kelalaka
    Commented Oct 2, 2023 at 18:24
  • $\begingroup$ 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 $\endgroup$
    – Steven
    Commented Oct 2, 2023 at 18:28
  • $\begingroup$ Proof by contrapositive. $\endgroup$
    – kelalaka
    Commented Oct 2, 2023 at 18:29
  • $\begingroup$ Got it! I appreciate your guidance! $\endgroup$
    – Steven
    Commented Oct 2, 2023 at 18:30


Your Answer

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