1
$\begingroup$

Following are steps to conduct Chosen Plaintext Attack (CPA) indistinguishibility experiment $PrivK_\mathcal{A,E}^{eav}(n)$.

$\mathcal{A}$ is the adversary $\mathcal{E}$ is the encryption scheme (Gen, Enc, Dec), $n$ is the length of the input.

  1. a secret key SK is generated using Gen($1^n)$
  2. $\mathcal{A}$ is given input of $1^n$ and oracle access to $Enc_{sk}(.)$ and outputs a pair of messages $m_0$ and $m_1$ of the same length.
  3. A random bit $b$ is chosen. $Enc_{sk}(m_b)$ is computed to form $challenge$ ciphertext $C$ given to $\mathcal{A}$.
  4. $\mathcal{A}$ continues to have oracle access to $Enc_{sk}(.)$ and outputs another bit $b'$.
  5. If $b'== b$ then $\mathcal{A}$ succeeded, otherwise $\mathcal{A}$ lost the game.

To better understand the experiment above, I decided to run it with simple values of my choosing:

  1. secret key SK 10101010 generated with length n=8 by defender (one who wants security)
  2. $\mathcal{A}$ is given an input $1^n$ = 11101110 by defender. Using the length of this input, $\mathcal{A}$ comes up with $m_0 = 11111111 $ and $m_1$ = 00000000
  3. Defender randomly selects $b$ = 0 and encrypts $Enc_{sk}(m_b)$ = $Enc_{sk}(m_0)$ = $Enc_{sk}(11111111)$ = 10111011 = $C$ challenge and given to $\mathcal{A}$
  4. Using $C$ = 10111011 $\mathcal{A}$ tries to guess if it came from $m_0$ or $m_1$. Guesses $b'$ = 1. This means $\mathcal{A}$ lost the game.

My understanding is the adversary continues to pick different $m_0$ and $m_1$ values and has the defender encrypt them until he starts guessing correctly over 1/2 the time.

Is this a correct understanding or am I missing something?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

There are a surprisingly large number of subtly different definitions of CPA indistinguishability. What you describe in points 1 through 5 is one that I have heard of, though at the end of your post you make it 'iterative', in the sense that $\mathcal{A}$ can play the game over and over with $\mathcal{E}$ using the same secret key but fresh, independently-random values for $b$ for each game. I have not heard of the IND game being set up iteratively like that -- usually $\mathcal{A}$ only gets one bite at the apple in terms of guessing $b$. Are you sure you meant to define it that way?

You also don't really define what it means for $\mathcal{A}$ to "continue to have access to the oracle" in point 4. Do you mean $\mathcal{A}$ can make more chosen plaintext queries before it has to guess $b$? If so, do they have to be of the form $(m_0, m_1)$ where only the encryption of $m_b$ is returned to it, or can they be individual messages?

Granting $\mathcal{A}$ up to $q_e$ queries of the form $(m_0, m_1)$ (i.e. so that every query is a 'challenge') before it has to make its guess for the value of $b$ is the more common Left Or Right (LOR) notion of IND-CPA. BDJR'97 defines LOR IND-CPA (as well as several other notions of CPA security): http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.4734

Improve this answer
$\endgroup$
8
  • $\begingroup$ I think you are right. Looking back at my notes there isn't any iteration. But then I also do not know what "continue to have access to oracle" would mean. If the adversary has continued access then he can keep querying it right? $\endgroup$
    – user1068636
    Sep 21, 2013 at 2:47
  • $\begingroup$ Yes, and why are you concluding from from that that the adversary can get more $challenge$ ciphertexts? $\endgroup$
    – user991
    Sep 21, 2013 at 4:45
  • 1
    $\begingroup$ @user1068636 - Sometimes CPA games are defined in 'phases', such that phase 1 is the 'Challenge' phase (i.e. the adversary submits a single pair of messages and gets the bth message encrypted in response), and phase 2 is an adaptive query phase where the Adversary can directly query the oracle on any individual message for up to $q_e$ queries. The only restriction is the Adversary cannot request the encryption of either of the challenge messages (otherwise the game is trivial to win). Perhaps that sort of multi-phase game is what is meant by 'continued access'. $\endgroup$
    – J.D.
    Sep 21, 2013 at 17:07
  • 1
    $\begingroup$ @user1068636 -- Well, sort of ... the main point is to determine whether the adversary has a better than 50/50 chance of distinguishing between the encryption of $m_0$ and the encryption of $m_1$ where the challenge is either $E_k(m_0)$ or $E_k(m_1)$ and the adversary doesn't know which one it is. If there is a subsequent inquiry phase then $\mathcal{A}$ is permitted to ask for the encryption of any message besides $m_0$ and $m_1$. $\endgroup$
    – J.D.
    Sep 21, 2013 at 17:37
  • 1
    $\begingroup$ @J.D. - When you say "subsequent inquiry phase" you imply "continuing oracle access" ? $\endgroup$
    – user1068636
    Sep 21, 2013 at 18:30

Your Answer

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

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