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

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?

• Two options: Either there are no invalid ciphertexts that you could find with non-negligible probability or you'd get $\perp$ (ie "invalid ciphertext") if some checksum / MAC failed. – SEJPM May 6 '17 at 11:44
• Yes, $A$ knows that the challenge ciphertext is invalid and must reply accordingly. This is part of the security notion: no adversary can guess $b$ even by knowing that certain ciphertexts are not valid. As SEJPM mentions, if the set of such ciphertexts has negligible cardinality, then we can simply ignore this situation. – Daniel May 6 '17 at 11:50
• So suppose that I want to use $A$ to distinguish messages and I am able to construct invalid ciphertexts. What you are saying is that, if I give $A$ an invalid ciphertext, I will get information about that ciphertext (if it is valid or not). Right? – P.B. May 6 '17 at 11:59
• What do you mean with "use $A$ to distinguish messages"? – Daniel May 6 '17 at 12:05
• My question is: Suppose that I have two messages $m_0,m_1$ given by $A$. I do some operations on one of the messages to get a ciphertext $c$ but I am not sure if $c$ is valid or not. If I send the ciphertext $c$ to $A$, I will know if it is valid or not (if it is invalid, $A$ will answer accordingly). Right? – P.B. May 6 '17 at 12:21

$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$?

• And if I want to use $A$ to break something else? If I give $A$ an invalid ciphertext $c$, the fact that $A$ outputs something that tells me that $c$ is invalid can give me very useful information about $c$. But, you say that $A$ always output a bit $b$ even if it is able to detect that $c$ is invalid, right? – P.B. May 6 '17 at 12:47
• If $A$ can detect that you have given it an invalid ciphertext instead of an encryption of $m_0$ or $m_1$ it will know that you are cheating. So it can do whatever it wants and will not necessarily help you break anything. (expanded the answer a bit) – Elias May 6 '17 at 12:52

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.

• Well, if you challenge the adversary with a ciphertext that has no information regarding the input message (as OP says), then it is impossible that the adversary "distinguish" the message, no matter what strategy he uses. So you at least know something about the adversary (i.e., he cannot distinguish messages in this case, because it's impossible). – cygnusv Jul 6 '17 at 13:41
• @cygnusv OP only says the challenge is not the encryption of $m_0$ or $m_1$, not that it does not contain any information about it. It could be, for example, the bitwise complement of the encryption of $m_0$... – fkraiem Jul 6 '17 at 13:56

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.

• Proofs don't assume that the advantage is $0$, they prove it (or at least justify it), and this does not require assuming anything about what the behaviour of the adversary is on any particular ciphertext, which is what I understand the question asks. – fkraiem Jul 6 '17 at 15:39