Let $(E,D)$ be a cipher with message space $M = {0,1}^n$ and key space $K = {0,1}^n$.

Assume that there is an algorithm $A:{0,1}^n to {0,1}^n$ of size $T$ that given an

encryption of a message can guess the entire message with probability $0.2$. Namely, for a message $m in M$ it satisfies $$P(A(E(k,m)) = m) = 0.2$$

I want to prove that $(E,D)$ is not $(T + O(n), 0.1)$-secure.

It means that for every two messages $m_1, m_2 in M$ and every algorithm $B: A:{0,1}^n to {0,1}$ of size at most $T + O(n)$, it follows that:

$$| P(B(E(k,m_1)) = 1) – P(B(E(k,m_2)) = 1) | le 0.1$$

My idea was to assume on the contrary that $(E,D)$ is $(T+O(n), 0.1)$-secure, and then find an algorithm $B:{0,1}^n to {0,1}$ of size $T+O(n)$ that uses $A$ to break this encryption.

Namely I need to show that for any two messages $m_1, m_2 in M$ it satisfies:

$| P(B(E(k,m_1)) = 1) – P(B(E(k,m_2)) = 1) | > 0.1$

Basically I need to describe such $B$ and two messages $m_1, m_2$ that satisfy this inequality.

My idea was to pick two random messages $m_1, m_2 in M$. Then, somehow use $A$ to get the probability $P(B(E(k,m_1)) = 1) = 0.2$, and use randomness somehow to get the probability $P(B(E(k,m_2)) = 1) = 0.2 * 0.5 = 0.1$

However, I don’t really know how to do that.

Help or some hint would be very appreciated!