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$
$\endgroup$
1
-
$\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$ – Luis Casillas Apr 14 '20 at 17:07
Add a comment
|
$\begingroup$
$\endgroup$
3
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$
-
$\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
