Why perfectly secrecy needs the key space to be as large as the message space?

I think the definition (1)

$\Pr[M=m\mathrel|C=c]= Pr[M=m]$ still holds.

Let $M(c)$ be the set of messages that can be decrypted from $c$. We know that $|M(c)| \leq |K| < |M|$ where $K$ and $M$ are the key and message space, and we can infer that some message, say $m'$ can never be the plaintext of $c$, but how does that violate the definition (1) ?


how does that violate the definition (1) ?

Let's assume $|K|<|M|$. Then there exist $c\in C$ and $m\in M$ such that for all $k\in K$, you cannot get $c=E_k(m)$ ($c$ encrypts $m$ under the key $k$).

Now expand the conditional probability of your definition (1): $$\Pr[M=m|C=c]=\frac{\Pr[M=m\;\&\;C=c]}{\Pr[C=c]}$$ but since $|K|<|M|$, we already have a pair $(m,c)$ that you cannot get under any encryption key, therefore $\Pr[M=m\;\&\;C=c]=0$. Your definition is violated.

You could get to the same conclusion by using entropy -- to get perfect secrecy (i.e. no information about the plaintext is yielded from the ciphertext), entropy of the key space must be at least as big as the message space entropy.

| improve this answer | |
  • $\begingroup$ The thing that confuses me is, for the attacker, how can he know the message m is that one that doesn't fall into the M(c) space? The only thing he knows is that, there exist some messages that are not in M(c). $\endgroup$ – FunkyBaby Sep 6 '19 at 8:59
  • $\begingroup$ Don't confuse theory and practice :-) Perfect secrecy means that even an attacker with unlimited computing power cannot infer any information about the plaintext from the ciphertext. Finding (and exploiting) the information that is contained in the ciphertext in not-perfectly-secure ciphers is a whole different story. Modern ciphers are designed such that this exploit is (hopefully) computationally infeasible. $\endgroup$ – zajic Sep 6 '19 at 9:34
  • $\begingroup$ I was saying, how can we claim Pr[𝑀=𝑚&𝐶=𝑐]=0. For the message m, the attacker can never know if m is in M(c) where M(c) is the set of possible plaintext of c, though he does know that some messages are not in M(c). $\endgroup$ – FunkyBaby Sep 7 '19 at 7:37
  • $\begingroup$ Again, the attacker is allowed to have unlimited computing power - i.e. he can try all possible keys to see whether $m\in M(c)$. Anyway, the definition must hold for all pairs $(m,c)\in M\times C$ and proving existence of some pair $(m,c)$, that does not have this property, is enough. $\endgroup$ – zajic Sep 8 '19 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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