# Proof that perfect privacy implies that the number of keys is at least the number of messages

I was reading a proof to the statement:

Perfect privacy implies that $|K| = |M|$

where I am pretty sure that $K$ is the set of keys and $M$ is the set of messages.

The proof is the following, but I don't understand it (maybe because of the notation).

Assume not, i.e., assume we have fewer keys than messages. Given a ciphertext $c$, there is a message $m$ and a key $k$ such that:

$e(k, m) = c$, and $p_{k \in K}[e(k, m) = c] > 0$

Let $P_c = \{ m \in M$ such that $e(k, m) = c$ for some $k \}$

Since every $k$ maps exactly one message $m$ to $c$, and since we have fewer keys than messages, then there is an $m'$ not in $P_c$ such that no key $k$ maps $m'$ to $c$.

Therefore $P_{k \in K}[e(k, m') = c] = 0$, which violates the perfect-secrecy condition that for all m and $m'$, $P_{k \in K}[e(k, m) = c] = P_{k \in K}[e_k(k, m'). = c]$.

where $k \in K$ means that $k$ is a key in the set $K$.

The first thing that I don't understand is the following notation: $p_{k \in K}[e(k, m) = c] > 0$. What exactly does this mean? Does $p$ refer to the probability?

I understood the following statement:

Since every $k$ maps exactly one message $m$ to $c$

It makes sense that a function should just output one result for the same inputs.

Therefore $P_{k \in K}[e(k, m') = c] = 0$

Does this mean that the probability that we encrypt $m'$ using $k$ results in the cipher $c$ is equal to $0$ because, as said before in the proof, $m'$ is a message that has no key $k$ that transforms it into $c$? If yes, I am still not 100% convinced.

which violates the perfect-secrecy condition that for all m and $m'$, $P_{k \in K}[e(k, m) = c] = P_{k \in K}[e_k(k, m'). = c]$

If we assumed at the beginning that $p_{k \in K}[e(k, m) = c] > 0$, that the statement above makes also sense.

Again, I don't get the part of assuming $p_{k \in K}[e(k, m) = c] > 0$ (apart from the fact that I am not sure if $p$ should be $P$, i.e. if it is just a typo, and if $P$ (or $p$) refer to probabilities, as I was wondering above).

Moreover, I think the proof is not showing the case when the number of keys is greater than those of the messages.

• "I think the proof is not showing the case when the number of keys is greater than those of the messages." That is correct, and in fact, the statement being proved is incorrect in that case. It could be modified to |K| = n|M| for some integer n, or equivalantly |K| = 0 mod M; that would make it a true statement – poncho Jan 6 '16 at 14:35
• My guess is that the perfect-secrecy states that, by seeing a ciphertext, we should be totally unable to reduce the key space so we should not be able to escape a brute force attack in the full key space in other to decipher it. In this sense, seeing a ciphertext should not allow us to guess which keys were more likely used to produce the observed cipher text. – Ailton Andrade de Oliveira Jan 24 '16 at 14:36
• If we want to look at what happens when $|K| > |M|$, it is important to know $|C|$ as well. Whether we can have perfect secrecy depends on it. For example if $|C| = |M|$ then it is necessary that $|K|$ is a multiple of them. On the other hand, if $|C| = |K|$ we can have perfect secrecy for any $|K|$. – fkraiem Jul 9 '16 at 12:41

Let $$K$$ be the set of all possible keys (for AES-256, this set has $$2^{256}$$ elements.)
Let $$M$$ be the set of all possible messages (for AES, it has $$2^{128}$$ elements).
Let $$C$$ be the set of all possible cipher texts (for AES, again $$2^{128}$$ elements).

I was reading a proof to the statement:

Perfect privacy implies that $$|K|=|M|$$

Actually this is $$|K| \ge |M|$$.

Perfect privacy condition is:
that for all $$m$$ and $$m′$$, $$P_{k \in K}[e(k,m)=c]=P_{k \in K}[e(k,m′).=c]$$
the probability that a cipher text $$c$$ is decrypted as $$m$$ is the same as being decrypted in $$m'$$.
Or in other words:
you can't find a difference between $$m$$ and $$m'$$.

In order to prove such statement you use reductio ad absurdum. Here you assume $$|M| > |K|$$.

The first thing that I don't understand is the following notation: $$p_{k \in K}[e(k,m)=c]>0$$. What exactly does this mean ?

Yes the $$p$$ is a typo and should be $$P$$. It means that there exists $$k$$ and $$m$$ such as $$e(k,m)=c$$ (which is trivial because we need a working algorithm...). Therefore the probability that given a $$c$$, $$m$$ is the plain text is at least $$\frac{1}{|M|}$$ (assuming a uniform distribution), hence $$> 0$$.

Therefore $$P_{k \in K}[e(k,m′)=c]=0$$

Does this mean that the probability that we encrypt $$m′$$ using $$k$$ results in the cipher $$c$$ is equal to $$0$$ because, as said before in the proof, $$m′$$ is a message that has no key $$k$$ that transforms it into $$c$$? If yes, I am still not 100% convinced.

The first thing you must think of is that the $$c$$ is fixed. In order to encrypt a message $$m$$ to this $$c$$ you need a key $$k$$. Because $$|M|$$ is greater than $$|K|$$ (assume $$|M| = 5$$ and $$|K| = 3$$), there exists messages that won't have a mapping to $$c$$ (in this case $$5 - 3 = 2$$). Therefore there exists $$m'$$ such as there is no $$k$$ so that $$e(k,m) = c$$. Hence $$P_{k \in K}[e(k,m′)=c]=0$$

Because the statement of perfect secrecy is for all $$m$$ and $$m'$$ you can't have at the same time all probabilities being $$> 0$$ and $$= 0$$. Therefore you have a contradiction.

• "Therefore the probability that given a c, m is the plain text is at least 1/|M| (assuming a uniform distribution), hence >0. " Why is it 1/|M| and not 1/|K| ? – user2253546 Jan 11 '20 at 9:27

As far as I know the statement is not correct. perfect secrecy implies $|K|\geq |M|$ (as you can see in Theorem 2.10 in Introduction to Modern Cryptography) and does not implies $|M|=|K|$ necessarily. Your mentioned proof works well for $|K|>|M|$ (and yes I believe $p$ refers to probability) .

also here is Katz and Lindell proof for this theorem (this proof is basically same as your proof just with different notations which may help you):

Assume $|K|<|M|$, consider uniform distribution over $M$ and let $c\in C$ be ciphertext that occurs with non-zero probability. let $M(c)$ be the set of all possible messages that are possible decryption of c; that is $$M(c)=\{m|m=Dec_k(c) \text{ for some } k\in K\}$$ Clearly $M(c)\leq |K|$. (Recall that we may assume Dec is deterministc). If $|k|<|M|$, there is some $m'\in M$ such that $m'\notin M(c)$. But then: $$Pr[M=m'|C=c]=0\neq Pr[M=m']$$ and so the scheme is not perfectly secure.