HW2 Q3(c)

HW2 Q3(c)

student (guest) 24 Jan 2018 16:22

Nir, can you please publish a solution to Q2(c) of HW2 (the bonus question)?
The ref solution you published doesn't have it.
Thanks.

student (guest) 24 Jan 2018 16:23

Sorry for the typo in the subject. I refer to Q2 (not 3).

nbitansky 24 Jan 2018 19:22

Here is one possible counter example. We want to define a generator $G:\{0,1\}^n \rightarrow\{0,1\}^{n+1}$ for which $G(s_0)\oplus G(s_1)$ isn't one-way. Let's focus on values of [$n$] such that $n+1$ is even (make sure you understand why this is enough).

Think about the input $s\in \{0,1\}^n$ for $G$ as $(b,y,s'))$ where $b$ is a bit, $y$ is of length $(n+1)/2$, and $s'$ is the rest (formally, of size $(n-3)/2$). Let $G'$ be any PRG that stretches strings of length $|s'|$ to $n+1$ bits. Define $G$ so that if $b=0$, it would return $y0^{(n+1)/2} \oplus G'(s')$, and if $b=1$, it would return $0^{(n+1)/2}y \oplus G'(s')$.

You can see that $G$ is a PRG, because $G'$ is a PRG and $s'$ is independent of $y$. However, $G(s_1)\oplus G(S_2)$ can always be inverted. Indeed, denote any such strings by its two halves $(u,v)$ and return as the preimage $s_1 = (0,u,s'), s_2 =(1,v,s')$.

Last edited on 25 Jan 2018 06:26 by nbitansky Show more