One-time pad and zero key I'm doing some exercises before my exam, and I am stuck with task number 4 in this file: http://www.cs.umd.edu/~jkatz/crypto/f10/hw1.pdf

Could you help me with this task?


  When using the one-time pad encryption scheme, it can occur that $k=0^l$ and then the ciphertext is equal to the plaintext! It has been suggested to improve the one-time pad by only choosing non-zero keys. What do you think of this improvement? In particular, is it still perfectly secret? If yes, prove it. If no, reconcile this with the fact that encryption with the all-0 key completely reveals the plaintext.
In few words:


OTP has perfect secrecy;
For a cipher to have perfect secrecy, it is required that $|K| \ge|M|$.


Let $K=M=C=\{0,1\}^n$ be the set of keys, messages and ciphertexts. If you apply the "improvement", ie, if you remove $0^n$ from the keyspace, then you've created a cipher that cannot show perfect secrecy (because now $|K| = |M| - 1 &lt; |M|$).

Therefore, the "improvement" completely breaks perfect secrecy, which makes this modified OTP worse than the original.



In many more words, with illustrating examples.

As you should know, the one-time pad has the perfect secrecy property, which is defined as follows: let $M,C,K$ be the sets of messages, ciphertexts and keys; $\forall k \in K, \forall c \in C, \forall m \in M: P[E(k,m)=c] = P[k \,\,xor\,\,m = c] = \alpha$, for some (tiny) positive real number $\alpha$.

In words, you have absolutely no information about the original message if you're given only the ciphertext. Suppose the cipher text reads:

The password of my bank account is my wife's birthday


What's the most probable original message?

The password of my bank account is my wife's birthday
The password of my bank account is my aunt's birthday
The password of my bank account is: b4nk-P4ssw0rd1234
Love of my life you've hurt me You've broken my heart


See? The "improvement" can't possibly improve this cipher. Actually, it makes it worse: by reading the ciphertext, the attacker can be sure that your password is anything but your wife's birthday -- he could get some information from the ciphertext!!!