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 Aug 3 '16 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 Aug 3 '16 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 Aug 3 '16 at 22:31
  • $\begingroup$ @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. $\endgroup$ – 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$.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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