[SOLVED] CS6260 Homework 1-Understanding perfect secrecy and its limitations

Objectives: Understanding perfect secrecy and its limitations.
Problem 1.1 (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. He decides to remove the all-zeros 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.2 (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.3 (15 points)
Alice and Bob have a good scheme to use (described above), but they don’t share any secrets.
Alice shuffles a deck of 52 cards and deals them face down to herself and Bob (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 N (the size of the set the messages chosen from) possible for perfect secrecy?
Lecturer: Sasha Boldyreva 1