Existence of 99% successful unbounded adversary against randomized secret key encryption scheme with short keys
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.