# Epsilon Perfect Secrecy: Size of Key Space

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?

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

## 1 Answer

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.

• can you assume $K$ is uniform? or is the question more general? Mar 20 at 21:11
• 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| Mar 20 at 21:19
• true, put that as a statement in the answer so it is complete... Mar 20 at 21:56