# Show that CPA-security implies security against plaintext recovery

Consider the following experiment:

1. $$k = Gen(1^n)$$
2. $$m \stackrel{u}{\in} \{0,1\}^{l(n)}$$
3. $$c = Enc_k(m)$$
4. $$m' = B(1^n,c)$$

Define the winning event as $$m' = m$$. I would like to show that if the encryption scheme $$Enc$$ is CPA-secure thn every PPT-algorithm $$B$$ can only succeed with negligible probability in the above experiment.

Proposal

This is the solution I have come up myself with:

• Could be useful to think of it this way: Assume the adversary can recover the plaintext with non-negligible probability using $B$. What would this say about the CPA-Security of the scheme? Commented Feb 13, 2019 at 23:09
• The last probability doesn't need to be $2^{-l(n)}$. It could be anything as long as the sun of probabilities of $B$ over the set of messages is 1. The key is, no matter that value, it's negligible and so your new distinguished $A$ as a non negligible advantage in the CAP game. Commented Feb 17, 2019 at 9:04
• An alternative could be to consider the ind-rch game where the attacks sends one message instead of 2 in the case of ind-cpa. Then the challenger selects the bit $b$ uniformly and if m is 0, it encrypts the message, otherwise the challenger selects another message of the same length at random and encrypts it. This might be easier since you only have one $m$ to 'worry' about. Finally, you can show that you can construct an efficient efficient attacker for ind-cpa from an attacker for ind-rch with the same advantage. Commented Feb 17, 2019 at 16:12

Your solution is almost correct. Just don't forget to consider the following two cases: 1) $$m_0$$ and $$m_1$$ may be the same, then $$A$$ will have to guess the secret bit $$b$$ blindly; 2) $$B$$ may return the other message, e.g., $$B$$ happens to return $$m_1$$ when given $$E_k(m_0)$$, then $$A$$'s output will be wrong. Note that 1) and 2) occur with only negligible probabilities.