Score:2

Let $G$ be a PRG. Establish whether the following PRG candidates $G^{'},G^{''}$ are secure or not

ml flag

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?

Score:1
ag flag

$\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).

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.