# 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? Aug 3, 2016 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? Aug 3, 2016 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. Aug 3, 2016 at 22:31

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
• @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$ Mar 18, 2021 at 20:53