# Almost (epsilon) perfect secrecy - lower bound of keyspace size

As a newcomer to cryptography, I'm working on Exercise 2.12 in the book, Introduction to Modern Cryptography. Using the proof of the theorem that says if $$E$$ is a perfectly secret encryption scheme, then $$\lvert K\rvert \geq \lvert M\rvert$$), I've shown that the lower bound for the size of the keyspace is as below: $$\lvert K\rvert \geq (1-\epsilon)\lvert M\rvert$$

But here's the problem: I proved this under the condition that $$\lvert\Pr[M=m\mid C=c]-\Pr[M=m]\rvert\leq\epsilon$$

So I think I should show that this definition is equivalent to the condition given in the exercise.

My question is whether the two definitions are equivalent, and if so, how can I prove it?

• I'm curious how you proved it. If $|K|$ < $|M|$ there will be an impossible message-ciphertext pair (m, c). Since we can freely choose a distribution for $M$, let $P(m) > \epsilon$. Then $P(m) - P(m | c)$ > $\epsilon$. Mar 16, 2021 at 21:35

Short answer: the two definitions are not equivalent.

• The condition $$|\Pr[M=m\mid C=c]-\Pr[M=m]|\leq\epsilon$$ doesn't allow us to have less keys than messages. 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$$

• The definition of $$\epsilon$$-perfect secrecy given in the book (the one you show in the image) does allow us to have fewer keys than messages. For example:

Suppose the message space $$M$$ contains all 4 English letter words, $$|M|$$ = $$26^4$$. Let's use a one-time-pad encryption scheme without the identity key, thus $$|K|$$ = $$|M| - 1$$.

Any adversary playing a game will choose two messages $$m_0$$, $$m_1$$. If our returned ciphertext $$c=m_0$$ the adversary knows for sure that the encrypted message is $$m_1$$. If our returned ciphertext $$c=m_1$$ the adversary knows for sure that the encrypted message is $$m_0$$. But if we return any other ciphertext, the one-time-pad scheme ensures that the best an adversary can do is to make a random guess. Therefore, the probability for an adversary to win a game is not greater than

$$1 \cdot \Pr(c \in \{m_0, m_1\}) + \frac{1}{2} \cdot (1 - \Pr(c \in \{m_0, m_1\}))$$ = $$\frac{1}{2} + \Pr(c \in \{m_0, m_1\}) \cdot \frac{1}{2} = \frac{1}{2} + \frac{1}{2|K|}$$

Thus, this scheme achieves $$\epsilon$$ perfect secrecy if $$\epsilon \geq \frac{1}{2|M-1|}$$

• Let's find a lower bound for $$\epsilon$$. Suppose an adversary chooses $$m_0$$ and $$m_1$$ uniformly at random. Upon receiving a ciphertext $$c$$ it computes $$M_c = \{ m | \exists k. enc_k(m) = c\}$$ (it might be computationally infeasible to compute $$M_c$$, but we're not concerned about computational resources in this exercise).

Note that at least one of $$m_0, m_1$$ is in $$M_c$$. If some $$m_i \not \in M_c$$ the adversary knows for sure that the encrypted message is the other one. If both messages are in $$M_c$$, the adversary makes a random guess.

The probability of such adversary succeeding is $$\frac{1}{2} \cdot \Pr(m_0, m_1 \in M_c) + 1 \cdot (1-\Pr(m_0, m_1 \in M_c))$$ = $$1 - \Pr(m_o, m_1 \in M_c) \cdot \frac{1}{2}$$

Let's estimate $$\Pr(m_0, m_1 \in M_c)$$ - the probability that both messages are in $$M_c$$. One message will certainly be in $$M_c$$ because we encrypted it to $$c$$, the other message is chosen uniformly at random from $$M$$, so the probability of both being in $$M_c$$ is $$|M_c| / |M| \leq |K| / |M|$$

Thus an adversary can win a game with a probability $$p \geq 1 - |K| / |M| \cdot \frac{1}{2} = \frac{1}{2} + \frac{1}{2} \cdot (|M| - |K|) / |M|$$. If we want $$\epsilon$$ secrecy we must have $$\frac{1}{2} + \epsilon \geq p$$ which implies that:

$$|K| \geq |M| \cdot (1-2\epsilon)$$

note that I have not shown this lower bound is attainable.

• can you please provide the details for the sake of other users reading this interesting question? Mar 17, 2021 at 19:43
• @kodlu I had to revise my knowledge about the $\epsilon$-perfect secrecy and updated my answer now. Mar 18, 2021 at 15:25

This question has been discussed in Beating Shannon requires BOTH efficient adversaries AND non-zero advantage by Yevgeniy Dodis, NYU, 2012/053.

## First, consider the Definition 1 and Remark 2. Remark 2 is as same as $$\Pr[\mathsf{PrivK}^{\mathsf{eav}}_{\mathcal{A},\mathsf{\Pi}}]\leq\frac{1}{2}+\epsilon$$. ## Then consider the second part of the Theorem 1 without decryption error (for exactly being same as the thing that the question wants). ## In the following, the proof is explained. Again, you can omit decryption error (for exactly being the same as the thing that the question wants). 