Recall that in the one-time pad, plaintexts, ciphertexts and keys are n-bit blocks for some ne N. For any key K, plaintext block M and ciphertext block C, the encryption of M with key K is Ek(M) = M 2 K and decryption of C with key K is DK(C) = CAK, where e denotes bitwise x-or (or equivalently, bitwise addition modulo 2). Assume as always that keys are chosen with equal likelihood. When using the one-time pad with the key K = 0" consisting of n zeros, we have Ek(M) = MOK = M for every paintext M, i.e. M is left unencrypted. It has been suggested to improve the security of the one-time pad by only encrypting with non-zero keys, i.e. removing 0" from the key space. a. (4 marks) Use either the definition of perfect secrecy, p(M) = P(MC) for all plaintexts M and ciphertexts with p(C) >0 or its equivalent characterization p(C) = P(C|M) for all plaintexts M with p(M) > 0 and ciphertexts C with p(C) > 0 to formally prove that this modification of the one-time pad does not provide perfect secrecy. Specifically, you will need to give a counterexample, i.e. exhibit a pair (M,C) that violates the definition or the above characterization of perfect secrecy. Answers that argue informally or do not use this characterization will receive very little if any credit. b. (2 marks) Explain (informally) why allowing K =0" does not weaken the security of the one-time pad, even though using that key does not hide the plaintext when encrypting. (Note: the assertion that choosing K =0" happens so rarely that we don't have to worry about it is not a valid answer and will not receive any credit.) Recall that in the one-time pad, plaintexts, ciphertexts and keys are n-bit blocks for some ne N. For any key K, plaintext block M and ciphertext block C, the encryption of M with key K is Ek(M) = M 2 K and decryption of C with key K is DK(C) = CAK, where e denotes bitwise x-or (or equivalently, bitwise addition modulo 2). Assume as always that keys are chosen with equal likelihood. When using the one-time pad with the key K = 0" consisting of n zeros, we have Ek(M) = MOK = M for every paintext M, i.e. M is left unencrypted. It has been suggested to improve the security of the one-time pad by only encrypting with non-zero keys, i.e. removing 0" from the key space. a. (4 marks) Use either the definition of perfect secrecy, p(M) = P(MC) for all plaintexts M and ciphertexts with p(C) >0 or its equivalent characterization p(C) = P(C|M) for all plaintexts M with p(M) > 0 and ciphertexts C with p(C) > 0 to formally prove that this modification of the one-time pad does not provide perfect secrecy. Specifically, you will need to give a counterexample, i.e. exhibit a pair (M,C) that violates the definition or the above characterization of perfect secrecy. Answers that argue informally or do not use this characterization will receive very little if any credit. b. (2 marks) Explain (informally) why allowing K =0" does not weaken the security of the one-time pad, even though using that key does not hide the plaintext when encrypting. (Note: the assertion that choosing K =0" happens so rarely that we don't have to worry about it is not a valid answer and will not receive any credit.)
