Task (a) – Properties of Computational Indistinguishability
(6 points)
Let $\left{X_{n}\right},\left{Y_{n}\right}$ and $\left{Z_{n}\right}$ be distribution ensembles satisfying the following: (1) for every $n \in \mathbb{N}$, distributions $X_{n}, Y_{n}$ and $Z_{n}$ are over domain ${0,1}^{n}$ and are efficiently samplable, and (2) $\left{X_{n}\right} \approx$ $\left{Y_{n}\right}$ and $\left{Y_{n}\right} \approx\left{Z_{n}\right}$, where ” $\approx$ ” denotes computational indistinguishability.

Decide whether the following pairs of distribution ensembles are computationally indistinguishable or not.
(i) $\left{X_{n} \oplus 1^{n}\right}$ and $\left{Y_{n} \oplus 1^{n}\right}$.
Here $\oplus$ is the $X O R$ opeartion and $1^{n}$ is the $n$-bit all 1 string.
(ii) $\left{X_{n} | Y_{n}\right}$ and $\left{Y_{n} | Z_{n}\right}$.
Here, $A_{n} | B_{n}$ is the distribution of $a | b$, when sampling $a$ from $A_{n}$ and $b$ from $B_{n}$ independently.
(iii) $\left{M\left(X_{n}, Y_{n}\right)\right}$ and $\left{M\left(Y_{n}, Z_{n}\right)\right}$.
Here, $M$ is a randomized algorithm that on input $(a, b)$, samples a random bit $i \stackrel{5}{\leftarrow} U_{1}$, and outputs $a$ if $i=0$ and $b$ if $i=1$. Moreover, $M\left(A_{n}, B_{n}\right)$ is the distribution of $M(a, b)$, when $a$ is sampled from $A_{n}$ and $b$ is sampled from $B_{n}$ independently.
For each of the above questions,

• (1 pts) Answer Yes, they are computationally indistinguishable, or No.
• (1 $\mathbf{~ p t s})$ If you answer is Yes, argue why the ensembles are indistinguishable, using the two properties “closure under efficient computation” and “transitivity” introduced in class. If your answer is No, describe a distinguisher that can distinguish the two ensembles.

Task (b) – An alternative definition fo PRG.
(6 points)
Given an efficiently-computable function $G$ with $|G(x)|=l(|x|)$, consider the following experiment $\operatorname{Exp}{n}^{A}$ defined for an adversary $A$ and parameter $n$ : Experiment $\operatorname{Exp}{n}^{A}$ : Proceed in the following three steps.

• Sample a random bit $b \stackrel{L}{\leftarrow}^{\$}$.
• If $b=0$, sample a random $x \stackrel{\$}{\leftarrow} U_{n}$ and set $y=G(x)$.
  If $b=1$, sample a random $y \leftarrow U_{l(n)}$.
• Output $b^{\prime} \stackrel{\$}{\leftarrow} A(y)$
  Say that $G$ is a $P R G$ if for every non-uniform PPT adversaries $A$, there is a neligible function $\varepsilon$, such that,
  $$
  \operatorname{Pr}\left[b=b^{\prime}\right] \leq 1 / 2+\varepsilon(n)
  $$
  (i) (2 pts) Describe formally the definition of PRG introduced in class.
  (ii) (2 pts) Argue informally why the above definition is equivalent to the definition introduced in class.
  (iii) (2 pts) Prove formally this equivalence.

Task (b) – From PRF to PRG
(6 points)
Let $F:{0,1}^{n} \times{0,1}^{n} \rightarrow{0,1}^{n}$ be a PRF. Construct a PRG $G$, such that, for all input $x$, the output length $|G(x)|=100|x|$ (i.e, on input an $n$-bit $x$, the output $y=G(x)$ has $100 n$ bits).
(i) (2 pts) Describe your candidate PRG G.
(ii) (2 pts) Argue informally why your candidate function $G$ is a PRG, given that $F$ is a PRF.
(iii) (2 2 ts) Prove formally the security of your candicate function $G$, by arguing contra-positive and giving security reduction.
Task (c) – From PRF to PRF
(10 points)
Suppose we have constructed a PRF function $F:{0,1}^{k} \times{0,1}^{m} \rightarrow{0,1}^{l}$, where the input and output length $m=m(k)$ and $l=l(k)$ are polynomial in $k$. Show that now, for any polynomial $l^{\prime}(k)$, we can construct a PRF $F^{\prime}$ with the same key and input lengths $m=m(k) l=l(k)$, but with output length $l^{\prime}=l^{\prime}(k)$.
(i) (2pts) Case 1: If $l^{\prime}(n) \leq l(n)$, how to construct $F^{\prime}$ from $F$ ?
(ii) (2pts) Case 2: If $l^{\prime}(n)>l(n)$, how to construct $F^{\prime}$ from $F$ ? You may use PRG in your construction
(iii) (4pts) Argue informally why your function $F^{\prime}$ is a PRF.
(iv) (2pts) Prove fomally that your construction $F^{\prime}$ for Case 2 is a PRF, by arguing contra-positive and giving security reduction.