# A generalisation of Shannon's theorem of perfect secrecy

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?

• For perfect secrecy, $|K| \ge |M|$, which means there must be at least one key per message. If there isn't perfect secrecy, how many keys must there be per message? – Aman Grewal May 23 '20 at 15:06
• There must be less than one key per message. I don't understand, however, how the exact amount of keys per message follows directly from the semantic security advantage. – user80306 May 23 '20 at 15:12
• I've edited my question to define the semantic security advantage. – user80306 May 24 '20 at 9:02

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.