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.


This is the solution I have come up myself with:

enter image description here

  • 2
    $\begingroup$ 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? $\endgroup$ Commented Feb 13, 2019 at 23:09
  • $\begingroup$ 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. $\endgroup$ Commented Feb 17, 2019 at 9:04
  • $\begingroup$ 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. $\endgroup$ Commented Feb 17, 2019 at 16:12

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.