Existence of 99% successful unbounded adversary against randomized secret key encryption scheme with short keys It can be shown that if $E$ is a deterministic encryption with key of length $n$ and messages of length
$l\geq n + 10$ then there exist two messages $m_0$, $m_1$ and a strategy for Eve so that
given an encryption $c = E_{k}(m_b)$ for random $k$ and $b \in \{0, 1\}$, Eve can output
$m_b$ with probability at least $0.99$. (Eve is computationally unbounded)

Proof is shown here (in the last page): http://www.boazbarak.org/cs127/chap01-introduction.pdf

Now, I would like to prove the exact same thing for random encryption algorithms that use, say n, random bits.
The problem is that the set of all possible encryptions of a certain message can be much larger. Let's say $E$'s random bits are $r\gets\{0,1\}^n$ drawn uniformly, then the set $\{E(m;r)\}_{k,r}$ can have size $2^{2n}$ which might be (much) larger than $2^l$ where $l$ is the length of messages.

Comparing to the deterministic proof, it is not hard to show that if we still choose $m_0$ arbitrarily and use the same kind of decision rule for $A$ the adversary, there exists a randomized $E$ and some $m_0$ such that for every $m_1$ the probability for $A$ to be correct is bad. So in order to deal with the randomized case, we must not choose $m_0$ arbitrarily or come up with a new decision rule for $A$.

Our only assumption is that $D_k(E_{k}(m;r))=m$ for all $r,m,k$. (The decryption algorithm cannot "miss")

I was wondering if anyone could offer a useful observation or any hints.
Eventually, I was able to solve this question.
For anyone wondering, my problem was (mainly) the generalization of the deterministic adversary decision rule to the randomized case.

Originally, the deterministic decision rule was $$A(ct)=\begin{cases}m_0 &amp; ct\in\{E_{sk}(m_0)\mid sk\in\{0,1\}^n\}\\m_1 &amp; otherwise\end{cases}$$
And I generalized it to
$$A(ct)=\begin{cases}m_0 &amp; ct\in\{E_{sk}(m_0;r)\mid sk\in\{0,1\}^n,r\in\{0,1\}^n\}\\m_1 &amp; otherwise\end{cases}$$
But the good generalization would be
$$A(ct)=\begin{cases}m_0 &amp; m_0\in\{D_{sk}(ct)\mid sk\in\{0,1\}^n\}\\m_1 &amp; otherwise\end{cases}$$

Also, this time around you fix $m_1$ and check out random $m_0$'s.
Well, the names do not really matter, but the point is that the decision rule depends on the random message, not the fixed one.