I am solving a homework problem which defines $(1-\epsilon)$-perfect secrecy as the secrecy satisfied by the encryption scheme when the following inequality holds

$\Pr[M=m\mathrel|C=c]\leq (1+\epsilon)\Pr[M=m]$

Then the problem asks us to prove that $|K|\geq \frac{1}{1+\epsilon}|M|$ where $K,M$ are the key and message spaces, respectively. I believe this problem is essentially the same as problem 2.12 in "Introduction to Modern Cryptography".

I have read the proof for Shannon Secrecy's key space limitation (which says $|K| \geq |M|$). I don't really see how this is connected to that proof, and I can't find any other way to approach. Can someone please give me a few hints?

  • $\begingroup$ define $(1-\epsilon)$perfect secrecy before asking the question $\endgroup$
    – kodlu
    Feb 15, 2018 at 20:54
  • $\begingroup$ Oops, I am so sorry about it, updated now. Thanks. $\endgroup$
    – steve6617
    Feb 16, 2018 at 1:13
  • $\begingroup$ Tiniest addendum: I believe that "Epsilon-Perfect Secrecy" should be hyphenated $\endgroup$ Apr 21, 2021 at 22:43

1 Answer 1


Choose a uniform distribution over the message space $M$. Suppose we observe a ciphertext $c$. Let $M_c = \{ m | \exists k. dec_k(c) = m \}$ be a set of all messages that could have been encrypted to $c$.

Choose a message $m \in M_c$ for which $\Pr[m|c] \geq \frac{1}{|K|}$ (such message exists, because the set $M_c$ has at most $|K|$ elements). Without knowing $c$, the probability of $m$ being chosen is $\Pr[m] = \frac{1}{|M|}$. Thus, we conclude that $\frac{1}{|K|} \leq \Pr[m|c] \leq (1+\epsilon)\Pr[m] = (1+\epsilon)\frac{1}{|M|}$, from which your desired inequality follows.

  • $\begingroup$ can you assume $K$ is uniform? or is the question more general? $\endgroup$
    – kodlu
    Mar 20, 2021 at 21:11
  • 2
    $\begingroup$ In the private key cryptography it is usually assumed that the distribution for keys is uniform. But even if it isn't, this proof can be modified to choose m such that Pr(m|c) is maximised and thus it will still be $geq$ 1/|K| $\endgroup$ Mar 20, 2021 at 21:19
  • 1
    $\begingroup$ true, put that as a statement in the answer so it is complete... $\endgroup$
    – kodlu
    Mar 20, 2021 at 21:56

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.