Invalid challenge-ciphertext in IND-CPA and IND-CCA games

Question

Consider the IND-CPA game between a challenger $C$ and an adversary $A$ for a given public-key encryption scheme $PKE$:

1. $C$ generates a key pair $(pk,sk)$ based on some security parameter $n$, and publishes $pk$ to $A$. $C$ retains $sk$.
2. $A$ may perform a polynomially bounded number of encryptions or other operations.
3. Eventually, $A$ submits two distinct chosen plaintexts $m_0,m_1$ to the challenger $C$.
4. $C$ selects a bit $b \in \{0, 1\}$ uniformly at random, and sends the challenge-ciphertext $c=E(pk,m_b)$ (the encryption of $m_b$ using the public-key $pk$) back to $A$.
5. $A$ is free to perform any number of additional computations or encryptions. Finally, it outputs a guess $b'$ for the value of $b$.

The advantage of $A$ is $Pr(b=b')-1/2$.

The IND-CCA2 game is the same except that, in phases 2 and 5, $A$ has access to a decryption oracle, with the condition that $A$ can not ask for the decryption of the challenge-ciphertext.

My question is: Suppose that there is an adversary $A$ that has a non-negligible advantage in one of these games. Suppose that, in phase 4, the challenger $C$ sends an invalid ciphertext to $A$ (i.e., $C$ sends a ciphertext that is not the encryption of $m_0,m_1$ or any other message $m$). In this situation, what does $A$ answer? Does $A$ knows that the challenge ciphertext is invalid?

Thanks in advance!

Answer 1

$A$ outputs a bit depending on whether it thinks you gave it an encryption of $m_0$ or $m_1$.

If you cheat and give it something completely different it has no usable information but still needs to output a bit.

If your PKE scheme has invalid ciphertexts $A$ might be able to detect that or not depending on the specifics.

So if you want to exchange your encryption of $m_0$ or $m_1$ for something else in a proof you have to show that $A$ cannot distinguish between these two situations.

Intuitively you can think about it this way: If $A$ had some way to distinguish between the real security game and your simulation it means that your simulation looks different. So how do you know that whatever $A$ did to attack the original game will work on your simulation if it doesn't look the same to $A$?

Answer 2

As an analogy, consider the following:

Let $x$ be a complex number such that $x^4 = 1$, show [something about $x$].

In my proof, I cannot assume that $x$ is real, because this is not given in the text of the question. Of course, any particular $x$ is either real or not real, and given any $x$ it is trivial to find out which is the case. But my proof must work for all $x$ such that $x^4 = 1$, not just those that are real. (It may be that all those $x$ happen to be real; but then I must show that fact before I can use it.)

The definition of an algorithm must include its behavior on every possible input (i.e., string), from which its output can be easily derived. Otherwise the definition is incomplete. So if you have a complete definition of $A$, the answer is to look at it.

But in many cases you do not work with a well-defined algorithm; all you know is that the algorithm possesses some property, usually of the form "algorithm $A$ breaks system $S$". You do not know the full definition of $A$, and this is for a reason: when we assume that a system is "breakable", we don't want to make any assumption about the specific attack strategy that an adversary uses. Indeed, if we did assume that $A$ behaved in some particular way and used that assumption to prove the security of a system, the system would only be proven secure against adversaries using that same strategy.

So you cannot assume anything about the adversary other than what is given, and since nothing is said about what the adversary does when given an invalid ciphertext, you cannot assume anything about it. Of course, any particular $A$ will output something, just like any particular $x$ will be either real or not real, but you cannot assume anything about what it is, unless you can show that it is implied by what you know.

Answer 3

In fact, the challenger sends invalid challenge ciphertexts in many proofs, and in this situations the adversary simply does not have any advantage. The important thing here is that the adversary cannot detect such situation, since then your proof would not be valid as the adversary "will not necessarily help you" (as phrased by @Elias in a comment to his answer).

Let me give you an example, in the proof of IND-CPA security of ElGamal (which is basically a reduction to the DDH problem), there is a probability of $\frac{1}{2}$ that the challenge ciphertext is not valid. This happens because, to construct the challenge ciphertext, the challenger takes a DDH tuple $(g^x, g^y, g^z)$ and creates the ciphertext $C^* = (g^y, m_b \cdot g^z)$, where $pk^* = g^x$. It can be seen that, when it holds that $z=x\cdot y$ in the DDH tuple (which happens with probability $\frac{1}{2}$), then the challenge ciphertext is perfectly valid since it is the encryption of $m_b$ under $pk^*$. However, when $z \neq x\cdot y$ (which happens with probability $\frac{1}{2}$), then the challenge ciphertext is basically garbage because the input message is information-theoretically hidden by the random value $g^z$, and the adversary cannot distinguish the message in this situation, so the proofs assume that adversary's advantage is 0 here. In any case, the adversary cannot distinguish that this ciphertext is garbage, but you can see that this is allowed in some proofs.