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

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) ?

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.
• 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. Sep 8 '19 at 11:11