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?


It seems you have to use some different approach. There is a hint in Arora/Barak's book. From that hint, I got the following solution.

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}

a contradiction!


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.