1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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?

Improve this answer
$\endgroup$
5
  • $\begingroup$ Pr(M=c|C=c)=0 I guess? But can we just choose for c to be in M and in C? $\endgroup$
    – stefanbschneider
    May 21, 2014 at 21:26
  • $\begingroup$ @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. $\endgroup$
    – Maeher
    May 22, 2014 at 4:35
  • $\begingroup$ 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. $\endgroup$
    – stefanbschneider
    May 22, 2014 at 11:58
  • $\begingroup$ 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. $\endgroup$
    – Maeher
    May 22, 2014 at 13:51
  • $\begingroup$ Yes, that is what I meant! $\endgroup$
    – stefanbschneider
    May 22, 2014 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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