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$.


$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.

  • $\begingroup$ Since $|C_{m_1} \setminus C_{m_0}| <= |K|$, the argument above works only for $\epsilon \leq 1/2$ $\endgroup$
    – 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.