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


enter image description here

  • 2
    $\begingroup$ Did you look at the proof of the original statement and try to adapt it? $\endgroup$
    – SEJPM
    Commented Aug 3, 2016 at 12:03
  • $\begingroup$ 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? $\endgroup$
    – Guut Boy
    Commented Aug 3, 2016 at 22:28
  • $\begingroup$ ... 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. $\endgroup$
    – Guut Boy
    Commented Aug 3, 2016 at 22:31

1 Answer 1


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

  • $\begingroup$ @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$ $\endgroup$ Commented Mar 18, 2021 at 20:53
  • $\begingroup$ @HilderVitorLimaPereira For a fair dice Pr(D=2) + Pr(D=4) is 2/6, but Pr(D=2k | D<5) is 1/2 $\endgroup$ Commented Mar 19, 2021 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.