# FC08 Assignment 3

### Problem 1: Indistinguishability.

Let $\{X_0\}_{n\in N}$ and $\{X_1\}_{n\in N}$ be computationally indistinguishable. Show that for all non-uniform p.p.t. distinguishers $D$, there exists a negligible function $\epsilon$ such that

$\Pr_{b\in_R\{0,1\},x\leftarrow X_b}[D(x)=b] < \frac{1}{2} + \epsilon(|x|)$

### Problem 2: Pseudo-random Generators.

Let $f:\{0,1\}^n\rightarrow\{0,1\}^m$ and $g:\{0,1\}^{n'}\rightarrow \{0,1\}^{m'}$ be two pseudo-random generators, where $m$ and $m'$ are respectively polynomial in $n$ and $n'$. Prove or disprove the following:

(1) The function $G_A(s) = f(g(s))$ is a PRG, where $n=m'$.

(2) The function $G_B(s) = f(s) \oplus g(s)$ is a PRG, where $n=n'$ and $m=m'$.

(3) The function $G_C(s,s') = s,f(s')$, where $|s| = |s'| = n$ is a PRG.

(4) The function $G_D(s,s') = s,f(s,s')$, where $|s| = |s'| = \frac{n}{2}$ is a PRG.

(5) The function $G_E(s,s') = s,f(s,s')$, where $|s| = O(1)$ and $|s'| = n-|s|$ is a PRG.

### Problem 3: Pseudo-random functions.

Let $F = \{f_s : \{0,1\}^{|s|} \rightarrow \{0,1\}^{|s|}\}_{s\in\{0,1\}^*}$ be a PRF. Determine if the following are always/sometimes/never a PRF.

(1) $F_s(x) = f_s(x) || f_s(x+1)$

(2) $G_s(x) = f_0(x) || f_s(x)$ (i.e., use a fixed key $0$ for the first evaluation of $f$)

(3) $H_{s_1,s_2}(x) = f_{s_1}(x) || f_{s_2}(x+1)$

(4) $I_s(x) = f_s(x)\oplus s$

### Problem 4: Encryption.

An encryption scheme $(Gen,Enc,Dec)$ is next-message secure, if for every two messages $m_0$ and $m_1$ of the same length, with Hamming distance $H(m_0,m_1)=1$, the encryptions of $m_0$ and $m_1$ are computationally indistinguishable (where the Hamming distance $H(m_0,m_1)=1$ is the number of bits in which $m_0$ and $m_1$ differ). Formally, for all non-uniform p.p.t. distinguishers $D$ there exists a negligible function $\epsilon(n)$, such that $\forall m_0,m_1$, where $|m_0|=|m_1|$ and $H(m_0,m_1)=1$,

$|Pr[D(Enc(m_0) = 1] - Pr[D(Enc(m_1)) = 1]| \leq \epsilon(n)$

Does next-message security imply single-message private-key security? Prove or disprove by giving a counterexample.