1.  (2 points) Suppose that the probability that someone wakes up before 6 am is 1/3, the probability that someone is a jogger is 2/3, and that the probability that someone is a jogger given that they wake up before 6 am is 3/5. Then what is the probability

that someone wakes up before 6 am given that they are a jogger?

Show your work.

2.  (3 points) Yet Another One Time Pad

Consider the following variant of the one-time pad.  Let the key space K, message space M and ciphertext space C be {0, 1, . . . , 25}n .  The one-time pad is defined as follows:

• Setup chooses a uniformly random key K ← K.

•  Enc(K,M) takes as input a key K ∈ K and a message M ∈ M. Let K[i] and M[i] denote the ith  component of the key and message respectively.  The encryption algorithm computes C[i] = (M[i] + K[i])  mod 26 for all 0 ≤ i < n.  It outputs C = (C[0],C[1], . . . ,C[n − 1]).

•  Dec(K,C) takes as input a key K ∈ K and a ciphertext C ∈ C .  It computes M[i] = (C[i] − K[i])  mod 26 and outputs M = (M[0],M[1], . . . ,M[n − 1]).

(a) For any c ∈ C,m ∈ M, compute Pr[Enc(K,M) = c|M = m], where the proba-

bility is over the choice of K .

(b) Let C = Enc(K,M) and C\ = Enc(K,M\ ). Express M\  in terms of M,C and C\

only (not involving K).

3.  (6 points) A function f is polynomially bounded if there exists a polynomial p(·) and an integer N such that for all integers n > N it holds that f(n) < p(n).

(An equivalent definition you may use is that a function f is polynomially bounded if there exist constants c and N such that for all integers n > N it holds that f(n) < nc .)

A function f is negligible  if for all polynomials p(·), there exists an integer N such that for all n > N , f(n) < 1/p(n).

Using the above definitions prove or disprove each of the following statements. State if they are true or false and give a short proof.  In some cases the proof can be a counterexample.

(a) If the functions f(n) and g(n) are negligible then h(n) = f(n)/g(n) is a negligible function.

(b)  f(n) = 1/2(lg n)2   is a negligible function.

(c) If the function f(n) is polynomially bounded then h(n) = 1/2f(n)  is a negligible function.

(d) g(n) = nlg(lg n)  is a polynomially bounded function.

(e) If the functions f(n) and g(n) are polynomially bounded then h(n) = f(n)f(4) ·

g(n)g(6)  is a polynomially bounded function.

(f)  h(n) = 1/nlgn  is a negligible function.

4.  (7 points) Equivalent Definition for Perfect Secrecy  In class, we saw the following definition for perfect secrecy:

Definition 1  A  symmetric  encryption scheme  (Setup, Enc, Dec) over message  space M is  said  to  be perfectly  secret  iff for  every  distributions  over M,  every  ciphertext c ∈ C, messages m,m\  ∈ M,

Pr[Enc(K,M) = c|M = m] = Pr[Enc(K,M) = c|M = m\]

where  the probabilities  are  computed  over  the  choice  of message  m,  key K  and  the randomness used by Enc .

Definition 2  A symmetric encryption scheme (Setup, Enc, Dec) is said to be perfectly secret iff for every distribution over M, every message m ∈ M, ciphertext c ∈ C such that Pr[Enc(K,M) = c] > 0,

Pr[M = m|Enc(K,M) = c] = Pr[M = m]

where  the probabilities  are  computed  over  the  choice  of message  m,  key K  and  the randomness used by Enc .

Prove that these two definitions are equivalent; that is, show the following:

(a) If a symmetric encryption scheme (Setup, Enc, Dec) satisfies Definition 1, then it satisfies Definition 2.

(b) If a symmetric encryption scheme (Setup, Enc, Dec) satisfies Definition 2, then it satisfies Definition 1.