(Im)perfect Secrecy: |K| < |M|

Question

I have a basic understanding of perfect secrecy. In the case where |K| == |M|, I see that there is only one key to encrypt a given m to a given c. Therefore each m is equally likely with same probability 1/|K|.

For the case of |K|<|M|, I have some intuition that it is not possible to map a random variable on set x to be a random variable on set y if |x| < |y|. But I'd like a formal proof of this. Or maybe this is the wrong way to look at this problem - I just want to see how we can prove that |K|<|M| result in non perfect secrecy.

This case of |K|<|M| is not a homework question; it is briefly mentioned in Boneh's Cryptography I, but not proved.

Answer 1

This is done in Theorem 2.5 of Boneh and Shoup's under-construction textbook.

In short, suppose $|K| < |M|$. Pick some $k \in K$, $m \in M$, and let $c = E(k, m)$. Now, for all possible keys $k' \in K$, there is a set of plaintexts $\{ D(k', c) : k' \in K \} $. But because $|K| < |M|$, there will be some $m'$ not in this set, such that $\mathbf{Pr}[E(k, m) = c] > 0$ and $\mathbf{Pr}[E(k, m') = c] = 0$. But by definition of perfect security, we should have $\mathbf{Pr}[E(k, m) = c] = \mathbf{Pr}[E(k, m') = c]$ for any $m, m'$.

In other words, there are not enough keys to make every possible ciphertext from a message, or every possible message from a ciphertext. This breaks perfect security.