# How can we prove that the following theorem is valid for almost perfect secrecy?

We have the following theorem:

Let $\Pi$ be a perfectly-secret scheme over message space $M$, and let $K$ be determined by $Gen$. Then $|K| ≥ |M|$.

How can we prove that the above theorem is valid for almost perfect secrecy? The definition for almost perfect secrecy is as follows:

The encryption scheme $\Pi = (Gen,Enc,Dec)$ over a message space $M$ is almost perfectly secret or $\varepsilon$-perfectly secret if for every probability distribution over $M$, $\forall m \in M$ and $\forall c \in C$ for which $Pr[C = c] > 0$ and for a constant $\varepsilon < 1$:

$$|Pr[M = m|C = c] - Pr[M = m]| < \varepsilon$$

EDIT

• Did you look at the proof of the original statement and try to adapt it? – SEJPM Aug 3 '16 at 12:03
• The definitions seem to be missing some details. What is K? What is C and c, and how can M = m if m is an element in M? – Guut Boy Aug 3 '16 at 22:28
• ... my point is that we can of course try to guess, but it might be easier to answer your question if you are a bit more precise. – Guut Boy Aug 3 '16 at 22:31
• @GuutBoy it is ambiguous... But you have to think of $M$ as a random variable when it is inside the $Pr$ function, so $Pr(M = m)$ is the probability of picking $m$ from (the set) $M$ following some distribution. – Hilder Vitor Lima Pereira Aug 6 '16 at 19:40

You cannot prove that because it is not true.

Chapter two of the book Introduction to Modern Cryptography explains about perfect secrecy and defines this $\varepsilon$-perfectly secret notion. In exercise 2.12 you are asked exactly to

[...] Show that $\varepsilon$-perfect secrecy can be achieved with $|K| < |M|$ when $\varepsilon > 0$.

• The exercise 2.12 has a different definition of $\epsilon$ perfect secrecy than the one written here. For the OP's definition, the statement is correct. – mercury0114 Mar 18 at 17:26
• @mercury0114 I checked the definitions again and they really seem different. But I don't understand your answer, unfortunately. Please, see my comment on your answer. – Hilder Vitor Lima Pereira Mar 18 at 19:39

Encrypt an arbitrary message to get a ciphertext $$c$$, then use all keys to decrypt $$c$$. If $$|K| \lt |M|$$, there exists a message $$m$$ which can not be decrypted from $$c$$ using any key.

Then $$|\Pr[M=m\mid C=c]-\Pr[M=m]| = \Pr[M=m]$$ and since we can assign an arbitrary distribution to our message space, we can make $$\Pr[M=m] > \epsilon$$. This violates your definition of $$\epsilon$$-perfect secrecy, thus we must have $$|K| \geq |M|$$.

Note that there is a different definition of an $$\epsilon$$-perfect secrecy, the one requiring that an adversary playing a game could not succeed with a probability higher than $$\frac{1}{2} + \epsilon$$. Such definition allows to have fewer keys than messages. For more information, have a look at Almost (epsilon) perfect secrecy - lower bound of keyspace size

• Hi @mercury0114. So you fixed a message $m$ such that $Enc_k(m) \not = c$ for all key $k \in K$. But why does it imply that $\Pr[M = m | C = c] = 0$? Let $D_c := \{ x \in M : Dec_k(c) \text{ for some } k \in K \}$. Then, you fixed some $m$ in $M \setminus D_c$. So, it seems that $\Pr[M = m | C = c] = \sum_{x \in M \setminus D_c}\Pr[M = x]$. – Hilder Vitor Lima Pereira Mar 18 at 19:40
• @HilderVitorLimaPereira Why should the last statement of your comment be true? Each term in a sum is not conditioning on c anymore. $Pr(m | c)$ indicates the probability that a message m was encrypted to the observed ciphertext c. I chose a message m that can not be encrypted to c. So if I observe a ciphertext c, then I know for sure that the plaintext message is not m, i.e. $P(m | c) = 0$ – mercury0114 Mar 18 at 20:53
• Things are not clear because the distributions are not explicitly defined. I don't know how you can interpret $\Pr[m | c]$ as the probability that m was encrypted to c. I would say that you first have to define a sampling method for the messages (distribution M), a distribution $K$ and a distribution $C$ (which might be totally determined by M and K...). From your comment, it seems that the distribution M is something like "$c \leftarrow C, \, k \leftarrow K$, output $m = Dec_k(c)$". That could work. – Hilder Vitor Lima Pereira Mar 19 at 8:01
• And yes, each term of the sum is not bound to $c$, but that is not necessarily a problem. Just like "probability of rolling a dice and getting an even number given that we already got a number smaller than 5", i.e, $\Pr[D = 2k | D < 5]$, is simply $\Pr[D = 2] + \Pr[D = 4]$. – Hilder Vitor Lima Pereira Mar 19 at 8:03
• @HilderVitorLimaPereira For a fair dice Pr(D=2) + Pr(D=4) is 2/6, but Pr(D=2k | D<5) is 1/2 – mercury0114 Mar 19 at 9:34