Let $G$ be a length-doubling pseudorandom generator (i.e., for any $n\in \mathbb{N}$ and for any $s\in\{0, 1\}^n$ it holds that $G(s)\in\{0, 1\}^{2n}$). Can you construct a length-doubling pseudorandom generator $H$ such that $H(0^n)= 0^{2n}$ for any $n\in \mathbb{N}$?

  • $\begingroup$ Hints: (1) What's the simplest construction you could make out of $G$ that would satisfy the additional $H(0^n) = 0^{2n} $ condition? (2) Can you prove that if $G$ is a pseudorandom generator, that construction of $H$ must be one as well? The heart of the problem seems to be to demonstrate that you know how to write such a proof. $\endgroup$ Apr 14 '20 at 17:07

Define $\forall s\in \{0,1\}^{n} \ : H(s)=G(s)\oplus G(0^n)\implies H(0^n)=G(0^n)\oplus G(0^n)=0^{2n}$

now, we'll prove by contradiction that $H$ is indeed a pseudo-random generator.

assuming that it's not we get that there exist an adversary D (PPT algo) such that for every polynomial p(n):


Now, define the adversary $D'(v):=v\oplus G(0^n)$ for the PRG "$G$", and we're almost done: $|Pr_{s\leftarrow\{0,1\}^n}[D'(G(s))=1]-Pr_{r\leftarrow\{0,1\}^n}[D'(r)=1]|=$ $|Pr_{s\leftarrow\{0,1\}^n}[D(G(s)\oplus G(0^n))=1]-Pr_{r\leftarrow\{0,1\}^n}[D((r)\oplus G(0^n)=1]|=$ $|Pr_{s\leftarrow\{0,1\}^n}[D(H(s))=1]-Pr_{r\leftarrow\{0,1\}^n}[D(r)=1]|>1/p(n)$


  • $\begingroup$ Welcome to Cryptography. As our current policy, we provide hints to homework questions and that is usually given in the comments. $\endgroup$
    – kelalaka
    Apr 15 '20 at 11:17
  • 1
    $\begingroup$ @kelalaka that's my post though, and I've found the answer, thought I might as well post it to the use of someone in the future, if you can improve my answer you're welcome to do so. $\endgroup$
    – MercyDude
    Apr 15 '20 at 11:45
  • $\begingroup$ In case anyone else reads this and has trouble figuring out the last equality: XORing a given number (in this case G(0^n)) with the group of all numbers {0,1}^2n results in the same group $\endgroup$
    – yuvgin
    Apr 10 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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