# Proving that a scheme is $\epsilon$-perfectly secret

I am currently trying to solve the following problem (2.18) from the book "Introduction to Modern Cryptography (3rd edition)" by Katz and Lindell:

Let $$\epsilon > 0$$ be a constant. Say an encryption scheme is $$\epsilon$$-perfectly secret if for every adversary $$A$$ it holds that $$Pr[PrivK^{eav}_{A,\Pi}] \leq 1/2 + \epsilon$$.

Consider a variant of the one-time pad where $$M = \{0, 1\}^l$$ and the key is chosen uniformly from an arbitrary set $$K \subseteq \{0, 1\}^l$$ with $$|K| = (1-\epsilon) \cdot 2^l$$. Encryption and decryption are otherwise the same.

Prove that this scheme is $$\epsilon$$-perfectly secret.

I've tried the following:

$$Pr[PrivK^{eav}_{A, \Pi} = 1]$$ = $$1/2 \cdot Pr[PrivK^{eav}_{A,\Pi} | b = 0]$$ + $$1/2 \cdot Pr[PrivK^{eav}_{A,\Pi} | b = 1]$$

Assuming that the adversary is deterministic we can fix $$m_0$$ and $$m_1$$ generated by $$A$$. In addition, let $$C_{m}$$ be the set of possible ciphertexts derived from any given $$m \in M$$.

Then

$$Pr[PrivK^{eav}_{A,\Pi} | b = 0]$$ = $$\sum_{c \in C_{m_0}} Pr[Priv^{eav}_{A, \Pi} = 1 | C = c] \cdot Pr[C = c]$$

= $$1/|K| \cdot \sum_{c \in C_{m_0}} Pr[Priv^{eav}_{A, \Pi} = 1 | C = c]$$

For any $$c \in C_{m_0}$$, let $$M(c)$$ be the set of messages that can be encrypted to $$c$$. Therefore

$$Pr[Priv^{eav}_{A, \Pi} = 1 | C = c] = 1 \cdot Pr[m_1 \notin M(c)] + 1/2 \cdot Pr[m_1 \in M(c)]$$

Because if $$m_1$$ is not in $$M(c)$$, $$A$$ knows for sure that $$m_0$$ was encrypted. Otherwise, $$A$$ can only give a random guess.

Now, what is $$Pr[m_1 \notin M(c)]$$? In the best case, $$A$$ selects $$m_0, m_1$$ such that $$|C_{m_0} \setminus C_{m_1}| = |C_{m_1} \setminus C_{m_0}| = 2^l - |K|$$

As a consequence, $$Pr[m_1 \notin M(c)] = Pr[c \in C_{m_0} \setminus C_{m_1}] \leq \frac{2^l - |K|}{|C_{m_0}|} = \frac{\epsilon}{1 - \epsilon}$$

Thus, $$Pr[Priv^{eav}_{A, \Pi} = 1 | C = c] = 1/2 + 1/2 \cdot Pr[m_1 \notin M(c)] \leq 1/2 + \frac{\epsilon}{2 \cdot (1 - \epsilon)}$$

This implies that $$Pr[PrivK^{eav}_{A,\Pi} | b = 0] \leq 1/2 + \frac{\epsilon}{2 \cdot (1 - \epsilon)}$$.

Since the same holds for $$Pr[PrivK^{eav}_{A,\Pi} | b = 1]$$, $$Pr[PrivK^{eav}_{A,\Pi}] \leq 1/2 + \frac{\epsilon}{2 \cdot (1 - \epsilon)}$$

Can someone point me out where my mistake in this reasoning is?

• Since $|C_{m_1} \setminus C_{m_0}| <= |K|$, the argument above works only for $\epsilon \leq 1/2$ – eee3 Apr 19 at 21:53

There is no mistake.

Just prefix your work with the observation that any scheme is secure for $$\epsilon\ge 1/2$$ because all probabilities are less than or equal to 1.

Then consider the case $$0<\epsilon<1/2$$. Repeat your argument, then note that $$2(1-\epsilon)>1$$ and so $$\epsilon/2(1-\epsilon)<\epsilon$$.

• Thanks for the analysis, I was indeed missing this important point. – eee3 Apr 19 at 21:04