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.


1 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.


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.