Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
3  
Hint: if an all-zero key was impossible, and the attacker intercepted a ciphertext consisting of the three characters "Yes", can he deduce any information about the plaintext (and if so, what)? –  poncho Oct 8 '12 at 21:36
3  
Hint 2: if any key is possible (including $k=0^l$), and the attacker intercepted a ciphertext consisting of the six characters "Attack", is it more likely that the plaintext was "Attack" or "Defend"? What about "Rabbit"? –  Stephen Touset Oct 8 '12 at 23:55
    
How about $l=1$? –  j.p. Oct 12 '12 at 5:58
    
Please be so kind to accept the perfectly valid answer by Bruno, Nick. –  owlstead Oct 27 '12 at 22:33

1 Answer 1

In few words:

  1. OTP has perfect secrecy;

  2. 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 < |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!!!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.