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

  • $\begingroup$ 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. $\endgroup$ – mercury0114 Mar 18 at 17:26
  • $\begingroup$ @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. $\endgroup$ – 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

  • $\begingroup$ 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]$. $\endgroup$ – Hilder Vitor Lima Pereira Mar 18 at 19:40
  • $\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$ – mercury0114 Mar 18 at 20:53
  • $\begingroup$ 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. $\endgroup$ – Hilder Vitor Lima Pereira Mar 19 at 8:01
  • $\begingroup$ 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]$. $\endgroup$ – Hilder Vitor Lima Pereira Mar 19 at 8:03
  • $\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$ – mercury0114 Mar 19 at 9:34

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.