Epsilon Perfect Secrecy: Size of Key Space

Question

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?

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.