# 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] | > 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!

• What is "$(T + O(n),0.1)$-secure"? – Yuval Filmus Nov 13 '20 at 20:31
• Can you give us a citation to the source where you originally encountered this problem, and provide chapter and exercise number? For instance, this helps provide context, and helps others with a similar question to find this page via search. – D.W. Nov 13 '20 at 22:22
• What is $k$ in the definition of $(\cdot,\cdot)$-secure? – xskxzr Nov 14 '20 at 4:11

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$$.