Unforgeable CPA-secure private-key encryption scheme that is not CCA-secure

Question

This is exercise with 4.26 in Katz and Lindell's introduction to cryptography 2nd ed.

The question is: Show a CPA-secure private-key encryption scheme that is unforgeable but is not CCA-secure.

This is what I've come up with.

Let $F$ be a pseudorandom function.

$Gen(1^n): k \leftarrow \{0,1\}^n$.

$Enc_k(m): r_1\leftarrow \{0, 1\}^n, r_2 \leftarrow \{0,1\}^n\setminus \{r_1\}$, output $c = (r_1, r_2, F_k(r_1) \oplus m, F_{k}(r_2) \oplus m)$.

$Dec_k(r_1,r_2,c_1,c_2): \perp$ if $r_1 = r_2$ or $F_k(r_1)\oplus c_1 \neq F_k(r_2) \oplus c_2$, else output $m = F_k(r_1)\oplus c_1$.

I have somehow proved that this is unforgeable and CPA secure. I wonder if there is an easier way to go about it or if this scheme indeed has the required properties.

The notation $\perp$ means decryption fails. To summarize, unforgeability means that an adversary with encryption oracle can't come up with a valid ciphertext whose underlying message wasn't queried to the oracle before except with negligible probability.

Thank you.

EDIT: This scheme doesn't work. Flipping the last bit of the 3rd and 4th components of the ciphertext yields a valid encryption of $m$ with last bit flipped.

EDIT: To provide the formal definition of unforgeability.

Define the unforgeable encryption experiment $EncForge_{A, \Pi}(n)$:

1. Run $Gen(1^n)$ to obtain a key k.

2. The adversary $A$ is given input $1^n$ and access to an encryption oracle $Enc_k(\cdot)$. The adversary outputs a ciphertext $c$.

3. Let $m = Dec_k(c)$, and let $Q$ denote the set of all queries that $A$ asked its encryption oracle. The output of the experiment is 1 if and only if $m \neq \perp$ and $m \notin Q$.

An encryption scheme $\Pi = (Gen,Enc,Dec)$ if for any PPT adversary $A$, $$ P[EncForge_{A,\Pi}(n) = 1] \le negl(n) $$ for some negligible function $negl$.

Answer 1

Take an authenticated (unforgeable and CCA-secure) encryption scheme, such as the one constructed in the book using encrypt-then-authenticate with a CPA-secure encryption and a strongly secure MAC.

Define a new scheme by appending to the ciphertext a random string.

This new scheme is still CPA secure and unforgeable. But it's not CCA secure because the adversary can change the random appendix and thus ask the oracle for decryption and win the CCA game.