Why does Encrypt-Then-Sign not yield a CCA-secure public-key encryption scheme?

Question

In symmetric cryptography, combining an IND-CPA secure symmetric encryption scheme with a secure MAC with the encrypt-then-MAC method yields a IND-CCA secure symmetric encryption scheme.

I am trying to understand why this does not hold in the asymmetric case. Suppose you have an IND-CPA secure public-key encryption scheme and a EUF-CMA (or sEUF-CMA) secure signature scheme. When you combine them via encrypt-then-sign the resulting scheme is not CCA-secure.

I know that there are some related questions on this site (e.g. this one or this one). So I understand that the problem is that, when Alice sends a message to Bob, Mallory can intercept it, remove the signatue, sign it again with her own signature and forward it to Bob. Bob then successfully verifies and decrypts the ciphertext and gets the message, thinking that it came from Mallory (since it has a valid signature from Mallory).

But why does this imply that it is not IND-CCA secure? How can an adversary use this property to win the IND-CCA security experiment?

My own thoughts up to now: I am not sure how the IND-CCA experiment in this case works. I would assume that all keys are fixed by the challenger and the adversary only gets the public encryption key and the public verifikation key. Is this assumption correct? Because in this case I do not see how the above attack by Mallory helps the adversary - since all the keys are fixed.

Appendix: How encrypt-then-sign works (or at least how I understood it works):

1. Suppose everyone has an encryption key pair and a signing key pair
2. To encrypt a message, you first take the public encryption key of the recipient and encrypt your message with it. Then you use your own secret signing key and sign the ciphertext.
3. Then you send the final ciphertext (consisting of the signature and the actual ciphertext) to a recipient.
4. The recipient decrypts the ciphertext, using his secret decryption key and the senders public verification key. First the signature is verified and then the ciphertext is decrypted.

Answer 1

I am not sure how the IND-CCA experiment in this case works.

Well, it doesn't really. There are no verification keys designated as such in the CCA experiment and there is no designated sender in the definition of a public key encryption scheme at all.

So, the only way to communicate to the receiver who supposedly encrypted a ciphertext would be to put it in the ciphertext itself. However, the encryption process takes as input only the encryption key and the message. So where is the signing key going to come from?

The answer is: Either it needs to be an input, in which case what you have is no longer even syntactically an encryption scheme, or you could generate a fresh keypair every time you encrypt. But since those would not be bound to anything this would be useless.

How can an adversary use this property to win the IND-CCA security experiment?

Choose two arbitrary messages $m_0\neq m_1$ and output them as a challenge. Receive the challenge ciphertext $C^* = (c^*,\sigma)$ where $\sigma$ is a signature on $c^*$ under some key which we will have to assume that the receipient magically knows. Generate a new keypair, sign $c^*$ again, resulting in $\sigma'$ and ask the challenger to decrypt $C'=(c^*,\sigma')$. Since $\sigma'$ is valid, and therefore $C' \neq C^*$ is distributed identically to a ciphertext honestly generated by the attacker we will receive back $m_b$, thus breaking CCA security.

Answer 2

After doing some digging, I think it may just be a matter of IND-CCA3 (see the end of this answer and this paper) being meant instead of the, perhaps usually implied, IND-CCA2. In particular, the specific use of asymmetric cryptography for authentication of the sender may be the sticking point.

When talking about encrypt-then-MAC, the mechanism by which the symmetric key(s) have been exchanged may be assumed to inherently authenticate the sender as a part of the encrypt and MAC operations. This may be the case if a pre-shared key is used, or if a key is generated as a part of an authenticated Diffie-Hellman key exchange as in TLS.

However, inherent in your description of encrypt-then-sign is the expectation that hybrid encryption is being used, and that the authenticity is coming from the signature, not the use of the expected key. As such, the stakes have changed and a new notion of IND-CCA is relevant, one which specifically considers the authentication of the encrypted data. In turn, this re-signing by an adversary is effectively the creation of a new, valid ciphertext as far as IND-CCA3 is concerned.

I haven't had much time to really digest the IND-CCA3 schema and try to break down how your second question (How can an adversary use this property to win the IND-CCA security experiment?) translates, since what I've described is in no way a proof, but hopefully this will at least lead you down the right path.