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$
$\endgroup$
1
-
$\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, 2012 at 0:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$)
