# Perfect Probabilistic Encryption still requires key length about as long as message

Let $$(E,D)$$ be a probabilistic encryption scheme with $$n$$-length keys (given a key $$k$$, we denote the corresponding encryption function by $$E_k$$) and $$n+10$$-length messages. Then, show that there exist two messages $$x_0, x_1 \in \{0,1\}^{n+10}$$ and a function $$A$$ such that

$$\mathrm{Pr}_{b \in \{0,1\}, k \in \{0,1\}^n}[A(E_k(x_b)) = b ] \geq \frac{9}{10}.$$

(This is problem 9.4 from Arora/Barak Computational Complexity.)

My gut intuition says that the same idea from the proof in the deterministic case should carry over. WLOG let $$x_0 = 0^{n+10}$$, and denote by $$S$$ the support of $$E_{U_n}(0^{n+10})$$. We will take $$A$$ to output $$0$$ if the input is in $$S$$. Then, assuming the condition stated in the problem fails to hold for all $$x \in \{0,1\}^{n+10}$$, we conclude that $$\mathrm{Pr}[E_{U_n}(x) \in S] \geq 2/10$$ for all $$x$$. This implies that there exists some key so that $$E_k$$ maps at least $$2/10$$ of the $$x$$ into $$S$$ (the analogue of this statement in the deterministic case suffices to derive a contradiction), but now I don't really see how to continue. Is my choice of $$A$$ here correct, or should I be using a different approach?

Again we set $$x_0=0^{n+10}$$. The algorithm $$A$$ works as follows. Let $$y=E_k(x_b)$$ be its input. Let $$Y_{x_1}$$ denote the set of ciphtertexts $$y$$ such that there exists some $$k$$ satisfying $$D_k(y)=x_1$$ ($$D$$ is the decryption algorithm). The algorithm $$A$$ outputs $$1$$ if and only if $$y\in Y_{x_1}$$ (so $$A$$ runs in polynomial time if P = NP). Then we have
$$\mathrm{Pr}_{b \in \{0,1\}, k \in \{0,1\}^n}[A(E_k(x_b)) = b ]=\frac{1}{2}\left(1-\mathrm{Pr}_{k\in\{0,1\}^n}[E_k(x_0)\in Y_{x_1}]\right)+\frac{1}{2}.$$
If this probability is less than $$9/10$$ for all $$x_1\in \{0,1\}^{n+10}$$, then we have $$\mathrm{Pr}_{k\in\{0,1\}^n}[E_k(x_0)\in Y_{x_1}]>1/5$$. This means $$\mathrm{Pr}_{k\in\{0,1\}^n,k'\in\{0,1\}^n}[D_{k'}(E_k(x_0))=x_1]>2^{-n}/5$$. Note this inequality holds for all $$x_1\in \{0,1\}^{n+10}$$, which means
\begin{align} 1&=\mathrm{Pr}_{k\in\{0,1\}^n,k'\in\{0,1\}^n}[D_{k'}(E_k(x_0))\in\{0,1\}^{n+10}]\\ &=\sum_{x_1\in\{0,1\}^{n+10}}\mathrm{Pr}_{k\in\{0,1\}^n,k'\in\{0,1\}^n}[D_{k'}(E_k(x_0))=x_1]\\ &>\frac{2^{n+10}\cdot2^{-n}}{5}, \end{align}