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 supposed to prove that OTP without the zero key $k=0^n$ is not perfectly secret anymore. I understand that it's not because an attacker learns something by looking at the plaintext and ciphertext. But I don't know how to prove it formally.

I was thinking about using Shannon. But to do so $|K|$ needs to be equal to $|P|=|C|=|{0,1}^n|$, which is not the case if I define $K={0,1}^n$ \ $0^n$. So my idea was to include the zero key to the key space K, but set the probability for $p(k=0^n)=0$. Doing so would allow me to have $|K|=|P|=|C|$ and to use Shannon.

PS: I'm aware of the somewhat similar question (One-time pad and zero key), but we didn't have any rule for $|K|>=|P|$ in order to achieve perfect secrecy. Also I am interested in my question about Shannon.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Well, for perfect secrecy, we require that for all message distributions over $\mathcal{M}$, all messages $m\in\mathcal{M}$, and all (possible) ciphertexts $c$ it holds that

$$Pr[M=m\ |\ C = c] = Pr[M=m]$$

In particular, that means, if we can find a single counterexample, i.e. a distribution over $\mathcal{M}$, a message $m\in\mathcal{M}$, and a ciphertexts $c$ such that

$$Pr[M=m\ |\ C = c] \neq Pr[M=m]$$

then, by our definition, the encryption scheme does not offer perfect secrecy.

So, let's take the uniform distribution over $\mathcal{M}$. For this distribution, we obviously have $$Pr[M=c]=1/|\mathcal{M}|.$$ Now, given that $0^n$ is not a valid key, what is the probability $$Pr[M=c\ |\ C = c]?$$ Are the two probabilities equal?

share|improve this answer
    
Pr(M=c|C=c)=0 I guess? But can we just choose for c to be in M and in C? –  CGFoX May 21 at 21:26
    
@CGFoX Well, we are talking about the OTP here (except that the all zero key is not allowed), so by definition, $\mathcal{M}=\mathcal{C}=\{0,1\}^n$. But even if they are some other sets. If the set of keys has an element less that the messages, then for any ciphertext $c$, there exists at least one message $m$ that cannot possibly result in $c$ no matter which key is chosen. –  Maeher May 22 at 4:35
    
Ok, but would it be possible to prove it using Shannon as I suggested? Modifying K such that it includes 0^n but set P(k=0^n)=0. That way |M|=|C|=|K| and according to Shannon it's not perfectly secret since P(k)=1/|K| doesn't apply for all k. –  CGFoX May 22 at 11:58
    
By "using Shannon" you mean applying Shannon's theorem? Sure, you can define your key-generation algorithm to pick the all zero key with probability 0 and all others with probability $1/(|\mathcal{M}|-1)$. That's exactly your encryption scheme. Then apply the theorem which states that the scheme is perfectly secret if and only if two condition hold. One of those conditions is that every key is chosen with the same probability, which obviously does not hold. –  Maeher May 22 at 13:51
    
Yes, that is what I meant! –  CGFoX May 22 at 13:54

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.