FC08 Assignment 3

From Theory
Jump to: navigation, search

Back to CS 8803FC - Foundations of Cryptography. Spring 2008.

Problem 1: Indistinguishability.

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

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

Problem 2: Pseudo-random Generators.

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

(1) The function <math>G_A(s) = f(g(s))</math> is a PRG, where <math>n=m'</math>.

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

(3) The function <math>G_C(s,s') = s,f(s')</math>, where <math>|s| = |s'| = n</math> is a PRG.

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

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

Problem 3: Pseudo-random functions.

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

(1) <math>F_s(x) = f_s(x) || f_s(x+1)</math>

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

(3) <math>H_{s_1,s_2}(x) = f_{s_1}(x) || f_{s_2}(x+1)</math>

(4) <math>I_s(x) = f_s(x)\oplus s</math>


Problem 4: Encryption.

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

<math>|Pr[D(Enc(m_0) = 1] - Pr[D(Enc(m_1)) = 1]| \leq \epsilon(n)</math>

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