Can you help with that definition for a CCA?

Question

The following is a definition taken from Introduction to Modern Cryptography by Katz and Lindell.

I'm having a hard time understanding some basic concepts! Can you please help me? $\newcommand{\Gen}{\operatorname{Gen}}\newcommand{\Enc}{\operatorname{Enc}} \newcommand{\Dec}{\operatorname{Dec}}$

Consider the following experiment for any private-key encryption scheme $Π=(\Gen,\Enc,\Dec)$, adversary $A$, and value $n$ for the security parameter. The CCA indistinguishability experiment PrivK:Aan (n) is:

1. A key $k$ is generated by running $\Gen (1^n)$.

2. The adversary $A$ is given input $1^n$ and oracle access to $\Enc_k (·)$ and $\Dec_k (·) $. It outputs a pair of messages $m_0, m_1$ of the same length.

3. A random bit $b\in \{0,1\}$ is chosen, and then a ciphertext $c = \Enc_k(m_b)$ is computed and given to $A$. We call $c$ the challenge ciphertext.

4. The adversary $A$ continues to have oracle access to $\Enc_k (·)$ and $\Dec_k (·)$, but is not allowed to query the latter on the challenge ciphertext itself. Eventually, $A$ outputs a bit $b'$.

5. The output of the experiment is defined to be 1 if $b' = b$, and 0 otherwise.

1. In the second bullet point what does "It outputs a pair of messages" mean? Who and where does it output those messages? Does the adversary output the messages? The oracle?

2. What's the purpose of the random bit b?

Answer 1

In step 2, the adversary outputs two messages. One of these will be selected at random for encryption. You can think of the adversary sending these messages to a "challenger" that also has oracle access (or is the oracle itself). It doesn't really matter who is running the challenge since the challenger doesn't have any "intelligence." All the challenger does is flip a coin to choose a message and remember which message she chose, so she can determine if the adversary guesses correctly or not.

If you think of the adversary as an interactive Turing machine, then the values are put on its output tape (likely why it was phrased that way in the text).

The random bit is just a formalization of flipping an unbias coin. The challenger uses it to pick one of the two messages. If the ciphertext of a given plaintext is indistinguishable from any other ciphertext, then the adversary cannot know which one was chosen any better than predicating the value of the coin flip: which is one half. Therefore, if the adversary can demonstrate the ability to predict better than one half which message was encrypted, it must be the case that the encryption function causes the ciphertexts to leak information about the plaintexts (either by looking at the ciphertext or by submitting related ciphertexts for decryption). In this case, the system is not CCA-secure.

Answer 2

The idea of IND-CCA2 (indistinguishable under an adaptive chosen-ciphertext attack) is that the attacker has no chance to distinguish the ciphertexts of two given plaintext messages, even if it can feed the decryption machine other ciphertexts for decryption.

In the second part of the experiment, the adversary has to chose two messages for the challenge (of equal length, since it is often easy to distinguish different-length messages by their different-length ciphertexts).

The challenger then randomly choses one of these messages (this is the random bit), encrypts it, and gives the result of this encryption as the challenge ciphertext back to the adversary.

The task of the adversary now is to guess which of the two plaintexts was chosen by the challenger. She wins the game if she guesses right.

(Both adversary and challenger are usually not actual persons, but can be thought as randomized algorithms, just like $\Gen$, $\Enc$ and $\Dec$.)

As guessing right occurs with probability $\frac12$ for a random guess, as cryptanalysts we actually want an adversary which will guess right with some probability strictly greater than that, and which doesn't need too long. As designers/users of an algorithm/protocol, we want that no adversary with such a capability exists (or at least, that it is not known to anyone).

All this (other than the first paragraph) actually applies to all these "IND-*" properties - the difference is just what means such an attacker can use to do this.

• In the IND-CCA2 case, the attacker has an decryption oracle available even after seeing the challenge ciphertext (but is not allowed to use it with the challenge ciphertext, to avoid a trivial win).

• With IND-CCA, after seeing the challenge ciphertext, no more decryption oracles are allowed to the adversary (i.e. she can't adapt to the challenge). (It might be that your book doesn't distinguish these two cases.)

• For a ciphertext-only attack, the adversary has neither encryption nor decryption oracle.