Objectives: Understanding perfect secrecy and its limitations.
Problem 1.1 (10 points)
Alice wants to securely send Bob an arbitrary number M from the set {0,1,…,N − 1} for some positive integer N. She wants to have a scheme with perfect secrecy. She’s heard of the One Time Pad (OTP), but OTP is for bitstrings, not numbers. She decides to use the following scheme. The key space is {0,1,…,N −1}. A ciphertext C for M is computed as (M +K) mod N and decryption performs (C − K) mod N.
Prove that this scheme is perfectly secure.
Problem 1.2 (10 points)
Your colleague observed that when the all-zeros key is used with One Time Pad scheme, the message is sent in the clear. In addition, when the all-ones key is used with One Time Pad the ciphertext is simply the complement of the message. He decides to remove the all-zeros key and the all-ones key from the key space.
Have a convincing argument of why this is not a good idea, without referring to the impossibility result (optimality of the OTP) we studied. You can use the definition of perfect secrecy.
Problem 1.3 (10 points)
Alice and Bob have a good scheme to use (described in 1.1), but they don’t share any secrets. Alice has a deck of cards but lost all of the Aces. So she shuffles the remaining deck of 48 cards and deals them face down to herself and Bob i.e. each of them gets a half. No one else can see what cards they get. In order to send a secret message to Bob, Alice explains to Bob (publicly) how to get the key. This does not involve any further exchange of cards. After that, and without the use of cards, Alice is able to send Bob a message with perfect secrecy.
What is the maximum size of N possible for perfect secrecy?
Lecturer: Sasha Boldyreva 1
