Let $(E,D)$ be an encryption system 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}$ that can guess the MSB (most significant bit) of the encryption with probability of 0.6. Namely, for a message $m in M$ it satisfies $P(A(E(k,m)) =

MSB(m)) = 0.6$

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

My idea was to assume in contrary that (E,D) is $(T, 0.1)$-secure, and then find an algorithm $B$ of size $T$ 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.

It’s clear I need to use $A$ but I am not sure how. I thought maybe make $B$ run $E(k,m)$ and then return 1 if $A$ returns 1 or something like that, but I am stuck.

Help would be very appreciated!