1
$\begingroup$

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

$\endgroup$
  • $\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 at 17:07
0
$\begingroup$

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 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, Let's 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$

| improve this answer | |
$\endgroup$
  • $\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 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 at 11:45

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.