# reductions – 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:{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!

Posted on Categories Articles