If there is an algorithm $A$ that guesses the entire message, given an encryption, with probability of $0.2$, then it's not $(O(A) +O(n), 0.1)$-secure 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\colon \{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.
A cipher $(E,D)$ is called $(T + O(n), 0.1)$-secure if for every two messages $m_1, m_2 \in M$ and every algorithm $B\colon \{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\colon \{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] | &gt; 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 \times 0.5 = 0.1$
However, I don't really know how to do that.
Help or some hint would be very appreciated!
Let $m_1$ be an arbitrary message. We are guaranteed that $P(A(E(k,m_1)) = m_1) = 0.2$. Averaging over all other messages, there is some message $m_2$ such that $P(A(E(k,m_1)) = m_2) \leq 0.8/(2^n-1) \leq 2^{-n}$.
Consider the following algorithm $B$: on input $x$, if $A(x) = m_2$ then output $1$, else output $0$. By assumption, $P(B(E(k,m_1))=1) \leq 2^{-n}$, whereas $P(B(E(k,m_2))=1) = 0.2$. When $n \geq 4$, the difference between the two probabilities is larger than $0.1$.