Difference between INT-CTXT and INT-PTXT

I have read recently (here) about INT-CTXT and INT-PTXT and that INT-CTXT is strictly stronger than INT-PTXT. I wonder if there is any clear example of the situation when INT-PTXT is achieved but no INT-CTXT?

There are also examples of related situation in the original article (e.g. Encrypt-and-MAC and MAC-then-Encrypt schemes on pp. 25-31) but I haven't managed to understand them. How an adversary is able to produce a ciphertext which wasn't produced by the sender but is not able to produce a ciphertext decrypting to a message which the sender has never encrypted?

My answer is taken from the following paper http://cseweb.ucsd.edu/~mihir/papers/oem.pdf (it is a well-written paper, so if you are interested in this topic I highly recommend you to read it).

Suppose $\mathcal{SE = (K, E, D)}$ is INT-PTXT secure. From $\mathcal{SE}$ we create another scheme $\mathcal{SE}_2 = (\mathcal{K}, \mathcal{E}_2, \mathcal{D}_2)$ which is also INT-PTXT secure, but not INT-CTXT secure. The idea is to add to every ciphertext produced by $\mathcal{E}$ a redundant bit which will be ignored upon decryption. This allows us to easily create new ciphertexts from old ones which still decrypts to the same plaintext. Intuitively, an attacker cannot exploit this against INT-PTXT (which requires it to submit ciphertexts that decrypts to new plaintexts), but it will help us to break INT-CTXT security.

In detail, the definitions of $\mathcal{E}_2$ and $\mathcal{D}_2$ are as follows.

$\underline{\mathcal{E}_2(K, M)}:\\\quad C \gets \mathcal{E}(K, M)\\\quad \text{Return } 0 || C$

$\underline{\mathcal{D}_2(K, C)}:\\\quad\text{Parse$C$as$b || C'$where$b$is a bit (return$\perp$if the parsing fails)}\\ \quad M \gets \mathcal{D}(K,C') \\ \quad \text{Return } M$

I leave it to you to prove that $\mathcal{SE}_2$ is also INT-PTXT (the reduction can be found in the last paragraph before Section 4 in http://cseweb.ucsd.edu/~mihir/papers/oem.pdf).

Here is a simple attack that shows that $\mathcal{SE}_2$ is not INT-CTXT.

$\text{Adversary$\mathcal{A}$}\\ \quad \text{Let$M$be any arbitrary plaintext} \\ \quad C \gets \mathbf{EncryptOracle}(M)\\ \quad \text{Parse$C$as$0 || C'$}\\ \quad \mathbf{VerificationOracle}(1 || C')$

Note that $\mathcal{A}$ is a valid INT-CTXT adversary since it asks for the verification of a ciphertext it did not previously obtain from an encrypt query. But it is not a valid INT-PTXT adversary since both $0 || C'$ and $1 || C'$ decrypt to the same plaintext $M$ (and $\mathcal{A}$ previously asked for the encryption of $M$).

• Also note that $D_2$ needs to reject the empty ciphertext. ​ ​ – user991 Jan 22 '17 at 11:05
• @RickyDemer Yes, good catch, I've added that in. Thanks. – hakoja Jan 22 '17 at 15:08