Problem 1.1, 10 points. Alice wants to securely send Bob an arbitrary number

M from the set f0; 1; : : : ;N 1g for some positive integer N. She wants to have a

scheme with perfect secrecy. She 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 f0; 1; : : : ;N 1g. 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, 15 points. Alice and Bob have a good scheme to use (described

above), but they don't share any secrets. Alice shues 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?

Problem 1.3, 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 denition of perfect secrecy.