In practice, a common use of SHA$3$ is to assume that it is a PRG$.$ Let$$s consider

$\{0,1\}128$ as the input domain and $\{0,1\}256$ as the output domain of to SHA$3-$

$256,$ as the following

SHA$3$ G: $\{0,1\}128->\{0,1\}256.$

I.e$.,$ we denote SHA$3()$ as G$().$

Now we want to use this to generate more pseudorandom bits as G$$ :

$\{0,1\}128->\{0,1\}512.$ Particularly, G$$ on input r in $\{0,1\}128$ works as follows:

$$ First compute r$1\backslash |$ r$2=$ G$($r$),$ where r$1$ in $\{0,1\}128,$ r$2$ in $\{0,1\}128$ and $\backslash |$

denotes concatenation.

$$ Then compute r$=$ G$($r$1)\backslash |$ G$($r$2)$ in $\{0,1\}512.$

$$ Output r$.$

Our goal is to show that the output of G$()$ is also pseudorandom, i$.$e$.,$

G$($U$128)$ is computationally indistinguishable from U$512,$ where Um denotes the

uniform distribution of m bits. Below we divide this into the following subtasks.

$1$

Subtasks: Consider the following hybrids distributions:

$$ H$0$: this is the output distribution of G$$ given a random input in U$128,$

i$.$e$.,$ G$($r$)=$ G$($r$1)\backslash |$ G$($r$2),$ where r$1\backslash |$ r$2=$ G$($r$)$ and r $$ U$128.$

$$ H$1$: this is a modified version of H$0.$ The output of H$1$ is G$($r$1)\backslash |$ G$($r$2)$

where both r$1$ U$128$ and r$2$ U$128,$ i$.$e$.,$ they are both truly uniform

strings. This is the only difference between H$1$ and H$0.$

$$ H$2$: this is a modified version of H$1.$ The output of this variant is r$$

$1\backslash |$ G$($r$2)$

where r$$

$1$ U$256$ is truly random, and r$2$ U$128.$

$$ H$3$: this is a truly uniform string, i$.$e$.,$ U$512.$

Show that each adjacent hybrids are computationally indistinguishable, un$-$

der the assumption that G is a secure PRG$.$ That is$,$ you need to prove H$0$c

H$1$c H$2$c H$3.$ Then argue why this suffices to show our overall goal