A generalisation of Shannon's theorem of perfect secrecy

Question

The proof I'm struggling with is the following:

Let $\mathcal{E}$ be a cipher defined over $(K, M, C)$. Suppose that $SSadv[A, \mathcal{E}] ≤ \epsilon$ for all adversaries $A$, even including computationally unbounded ones. Show that $|K| \geq (1 − \epsilon)|M|$.

The semantic security advantage, $SSadv[A, \mathcal{E}]$ of an adversary $A$ (in a standard attack game) over cipher $\mathcal{E}$ is defined as:

$SSadv[A, \mathcal{E}] := |Pr[φ(E(k, m_1))] − Pr[φ(E(k, m_0))]|$

Where $φ$ is a binary predicate on the ciphertext space $C$ (and the associated probability is the probability of the binary predicate evaluating to $1$), $k$ is a random variable uniformly distributed over the key space $K$, and $m_0, m_1 \in M$ (message space) are chosen by the adversary $A$, although the inequality $SSadv[A, \mathcal{E}] ≤ \epsilon$ should hold for all $m_0, m_1 \in M$.

Thus, what we are trying to prove is:

$|Pr[φ(E(k, m_1))] − Pr[φ(E(k, m_0))]| ≤ \epsilon \implies |K| \geq (1 − \epsilon)|M|$

How would I approach this?

Answer 1

Assume for the sake of contradiction that $|K|<(1-\epsilon)|M|$. We will define an adversary which has semantic advantage greater than $\epsilon$. Let $S=\{D(k,c)|k\in K\}$, where D is the decryption function of our cipher $\mathcal{E}$. We define our adversary A with the following characteristics:

1. $m_0,m_1\in M$ are chosen randomly
2. The predicate $\phi$ is chosen randomly with equal probability from either $\phi_1$ and $\phi_2$, which we define below
3. If $m_0\in S$ and $m_1\not \in S$, then $\phi_1(c)=\phi_2(c)=0$.
4. If $m_0 \not \in S$ and $m_1 \in S$, then $\phi_1(c)=\phi_2(c)=1$.
5. If both $m_0$ or $m_1$ are in S, then $\phi_1(c)=1$ and $\phi_2(c)=0$

(Note that while such a predicate function exists, it might not be an efficient one, ergo the part of the problem statement allowing for computationally unbounded adversaries.)

We have the following:

$$Pr[φ(E(k, m_1))]=Pr[\phi=\phi_1]Pr[m_0 \in S\; \text{and } m_1\in S]+Pr[m_0\not\in S \text{ and } m_1\in S]$$ $$Pr[φ(E(k, m_0))]=Pr[\phi=\phi_2]Pr[(m_0 \in S\; \text{and } m_1\in S)]$$

Note that both probabilities are implicitly conditioned on S, which depends on the message the challenger encrypts and sends to the adversary. Also, $Pr[\phi=\phi_1]=\frac{1}{2}$, since we chose our predicate function randomly. Moreover, in the first case $E(k,m_1)\in S$ trivially, and in the second case $E(k,m_0)\in S$, yielding that $$Pr[φ(E(k, m_1))]=\frac{1}{2}Pr[m_0 \in S]+Pr[m_0\not\in S]=\frac{1}{2}\frac{|S|}{|M|}+1-\frac{|S|}{|M|}$$ $$Pr[φ(E(k, m_0))]=\frac{1}{2}Pr[(m_1\in S)]=\frac{1}{2}\frac{|S|}{|M|}$$ So that $SSadv[A, \mathcal{E}] = 1-\frac{|S|}{|M|}$. Now $|S|\leq |K|$ by definition, and so by our assumption at the beginning $|S|<(1-\epsilon)|M|$. Therefore, $SSadv[A, \mathcal{E}]>\epsilon$, which is a contradiction, meaning that $|K|\geq (1-\epsilon)|M|$ as desired.