# Construct a specific length-doubling pseudorandom generator from a length-doubling pseudorandom

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}$$?

• 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. 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):

$$|Pr_{s\leftarrow\{0,1\}^n}[D(H(s))=1]-Pr_{r\leftarrow\{0,1\}^n}[D(r)=1]|>1/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)$$

$$\blacksquare$$

• Welcome to Cryptography. As our current policy, we provide hints to homework questions and that is usually given in the comments. Apr 15 '20 at 11:17
• @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. Apr 15 '20 at 11:45
• 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 Apr 10 at 17:10