FC08 Assignment 1

From Theory

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

1 Problem 1: Discrete Probability.
2 Problem 2.
3 Problem 3.
4 Problem 4.
5 Problem 5.

Problem 1: Discrete Probability.

(1) Read the following notes on discrete probability due to Luca Trevisan ps notes

We assume that the range of all the random variables below is contained in the reals.

(2) Let $X, Y$ be finite random variables. Prove that $E [X + Y] = E [X] + E [Y]$ . (This equality can be generalized to $n$ random variables.)

(3) Let $X, Y$ be independent finite random variables. Prove that $E [X Y] = E [X] E [Y]$ . (This equality can be generalized to $n$ mutually independent random variables.)

(4) Optional: Let $X$ be a finite random variable, and let $a, b$ be reals. Prove that $V a r [a X + b] = a 2 V a r [X]$ .

(5) Optional: Let $X 1,..., X n$ be pairwise independent finite random variables (i.e, $X i, X j$ are independent for every $i\neq j$ ).

Prove that $V a r [X 1 + ... + X n] = V a r [X 1] + ... + V a r [X n]$

(6) Give an example for two random variables $X, Y$ such that $E[XY] \neq E[X]E[Y]$ .

(7) Give an example for two random variables $X, Y$ such that $Var[X+Y] \neq Var[X]+Var[Y]$ .

(8) Let $E 1, E 2$ be two events. Prove that $Pr[E_1\cup E_2]\leq Pr[E_1]+ Pr[E_2]$ . (This inequality can be generalized to $n$ events, and is known as the union bound.)

[edit]

Problem 2.

Prove that Shannon secrecy implies perfect secrecy. (The other direction was proved in class. The proof for both direction appears in the lecture notes, though I strongly encourage the students to try to write the proof on their known. You can check the notes for assistance; however, avoid mere copying.)

[edit]

Problem 3.

Let $f:\{0,1\}^*\rightarrow\{0,1\}$ be a boolean function, let $p(\cdot)$ be a polynomial, and let $A$ be a probabilistic polynomial time algorithm such that for every $x\in\{0,1\}^*$ ,

$Pr[A(x)=f(x)]\geq\frac12+\frac{1}{p(|x|)}$ .

Prove that there exists a probabilistic polynomial time algorithm $A'$ such that for every $x\in\{0,1\}^*$ ,

$Pr[A'(x)=f(x)]\geq 1-2^{-|x|}$ .

Hint: Use Chernoff's Inequality, given in the appendix of the lecture notes.

[edit]

Problem 4.

Prove that there exists a collection of OWFs if and only if there exists a single strong OWF. (The highlevel idea of the proof was given in class, and appears in the lecture notes. Here the students are required to formalize this highlevel idea, and in particular, prove that the construction given in class works.)

[edit]