2
$\begingroup$

Let $G:\{0,1\}^n \leftarrow \{0,1\}^{2n}$ be a PRG. Establish whether the following PRG candidates $$G^{'},G^{''}:\{0,1\}^n \leftarrow \{0,1\}^{3n}$$ are secure or not:

  • $G^{'}(s)=(x⊕y,u,v)$ where $(x,y)=G(s)$ and $(u,v)=G(y)$;
  • $G^{''}(s)=(x,y ⊕ u,v)$ where $(x,y)=G(s)$ and $(u,v)=G(y)$;

This was in my exam today and I thought the following argument: Suppose $s$ random in $\{0,1\}^n$ then $(x,y)=G(s)$ is random in $\{0,1\}^{2n}$ since $G$ is a PRG. In particular $y$ is random in $\{0,1\}^n$ so $(u,v)=G(y)$ is random in $\{0,1\}^{2n}$ since $G$ is a PRG. Hence, as XOR preserves randomness, $x⊕y$ and $y ⊕ u$ are random too.

Finally both $(x⊕y,u,v)$ and $(x⊕y,u,v)$ are random in $\{0,1\}^{3n}$ and this proofs that $G^{'}$ and $G^{''}$ are both secure PRG.

Now I'm thinking that maybe this argument is wrong because i can't assume that $(x,y)$ random in $\{0,1\}^{2n}$ implies $y$ random in $\{0,1\}^n$.

Maybe I’m just confusing myself. Can you help me?

$\endgroup$

1 Answer 1

1
$\begingroup$

$\newcommand{\str}{\{0,1\}}$When trying to tackle such questions, hybrid argument is your friend.

Let $H_0$ denote the real experiment where the output $(w,u,v)$ is generated according to $G'$ -- i.e., for $s\leftarrow\str^n$, $$(x,y):=G(s),(u,v):=G(x),w:=x\oplus y;$$ let $H_2$ denote the random experiment where $(w,u,v)\leftarrow\str^{3n}$. Now, consider a hybrid experiment $H_1$ where we choose $(x,y)\leftarrow\str^{2n}$ and then set $$(u,v):=G(x),w:=x\oplus y.$$

First, let's prove that $G'$ is a PRG using hybrids. Using pseudorandomness of $G$, it can be shown that $H_0\approx H_1$, where $\approx$ denotes computational indistinguishability: given a challenge $(a^*,b^*)$ from the PRG experiment of $G$, the reduction simply sets $(x,y):=(a^*,b^*)$. In case $(a^*,b^*)$ is real, then the reduction is simulating $H_0$; otherwise, the reduction is simulating $H_1$. Similarly, it can be shown that $H_1\approx H_2$: the reduction now sets $(u,v):=(a^*,b^*)$ (here you need your observation that $\oplus$ preserves uniform randomness). Because indistinguishability is transitive, we get that $H_0\approx H_2$.

Now, when you try something similar with $G''$, you'll see that it doesn't quite go through. Specifically, the reduction for $H_0\approx H_1$ still works, but it is not clear how to show $H_1\approx H_2$ since it requires a "weird-looking" requirement that, for $y\leftarrow\str^n$, $(G_L(y)\oplus y, G_R(y))$ is pseudorandom, where by $G_L$ and $G_R$, I denote the left and right halves of $G$'s output. This should already set your alarm bells ringing and you should start thinking about counter-examples to $G''$ being a PRG. That is, is it possible to design a $G$ such that this property fails? I'll leave that to you (hint: design $G$ such that it leaks the seed).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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