Proving that a scheme is $\epsilon$-perfectly secret I am currently trying to solve the following problem (2.18) from the book &quot;Introduction to Modern Cryptography (3rd edition)&quot; by Katz and Lindell:
Let $\epsilon &gt; 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?
Thanks in advance.
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&lt;\epsilon&lt;1/2$. Repeat your argument, then note that $2(1-\epsilon)&gt;1$ and so $\epsilon/2(1-\epsilon)&lt;\epsilon$.