Suppose I want to prove that a given symmetric encryption scheme is not IND-CPA secure. The first thing I do is to define a specific adversary that attacks the scheme. How can I proof neatly, (using the game where A chooses two messages and is given a ciphertext $c$) that the adversary indeed almost always can determine which of the two messages is encrypted? So the result must be $Pr[$Game$_A^{CPA}(n)=1]-\frac{1}{2}$ is non-negligible. I get stuck in using the probabilities. Like what exactly does $Pr[$Game$_A^{CPA}(n)=1]$ (where $n$ is a security parameter)mean? Is it $Pr$[A outputs 1 and $c$ is the encryption of message1] + $Pr$[A outputs 0 and $c$ is the encryption of message0]? The output of A (guessing the right message) depends on the ciphertext so I am a bit confused.

  • $\begingroup$ I think the answer will depend upon the particular textbook you are using, and how they define $\text{Game}^CPA_A$. It sounds to me like your question could be paraphrased as: please help me understand what the definition of IND-CPA security means, and help me work through the details. That's probably going to depend upon the precise formulation of IND-CPA that your textbook or instructor happens to be using. $\endgroup$ – D.W. Nov 1 '12 at 0:42

Seems like you're getting confused between two different notations. Generally, in the experiment, adversary $A$ will output a bit $b'$. So, we have the following notations which refer to the bit $b'$ output by $A$: $$Pr[A(n)=1]$$ and $$Pr[A(n)=0]$$

Now, $A$ is said to have won the experiment if $b'=b$ and that is captured by the following notation. Here, we are interested in the outcome of the experiment. $$Pr[Game_A^{CPA}(n)=1]$$

The $=1$ in the above should not be confused with $A$'s output. Rather $1$ means $A$ wins (i.e. $b'=b$) and $0$ means $A$ loses (i.e. $b' \neq b$)

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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