# reductions – If there is an algorithm \$A\$ of size \$T\$ that guesses the MSB of an encryption with probability of \$0.6\$, then the encryption is not \$(T, 0.1)\$-secure

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!

Posted on Categories Articles