# 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 Vítor Lima Pereira Aug 6 '16 at 19:40

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