(One-time pad provides perfect secrecy) Recall that for the one-time pad, we have M = C = K = {0,1}n, encryption is dened via EK(M) = M K (bit-wise x-or), and decryption is given via DK(C) = C K.

i. (3 marks) Prove that one-time pad encryptions are bijections (i.e. one-to-one and onto). Use this result to describe the set EK(M).

ii. (6 marks) Prove that for any ciphertext C, the map C : K M dened by C(K) = DK(C) = C K is a bijection. Conclude that X KK p(DK(C)) = 1 .

iii. (6 marks) Assume that each one-time pad key is chosen with equal likelihood. Use the denition p(C) = X KK with CEK(M) p(K)p(DK(C)) to prove that each ciphertext occurs with equal likelihood (regardless of the probability distribution on the plaintext space).

iv. (3 marks) Prove that for every plaintext M and ciphertext C, there exist exactly one key K such that EK(M) = C, namely K = M C. Use this result to describe for any message M the set {K K| EK(M) = C}.

v. (2 marks) Assume again that each one-time pad key is chosen with equal likelihood. Use the results of parts (b) iii and iv as well as the denition p(C|M) = X KKE K(M)=C p(K) to prove that the one-time pad provides perfect secrecy.