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$ Commented 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$ Commented 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$ Commented 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$ Commented Sep 21, 2013 at 17:37
  • 1
    $\begingroup$ @J.D. - When you say "subsequent inquiry phase" you imply "continuing oracle access" ? $\endgroup$ Commented Sep 21, 2013 at 18:30

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.