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

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

• You should probably provide a definition for unforgeability, as this is not really a standard definition for encryption schemes. – Maeher Oct 15 '18 at 9:43
• @Maeher I've just added the definition. – Myath Oct 15 '18 at 9:52
• Consider that the definition does not rule out being able to transform a ciphertext into a different ciphertext for the same message. – Maeher Oct 15 '18 at 9:56
• @Maeher The criterion $m \notin Q$ does rule out transforming a ciphertext returned from the oracle to a different ciphertext for the same message. – Myath Oct 15 '18 at 9:59
• Read the definition again. A scheme can be unforgeable while it is possible to transform a ciphertext into a different one decrypting to the same message. This is because doing so does not help in winning the unforgeability game. Then consider how that contrasts with the restriction placed on decryption queries in the CCA game. – Maeher Oct 15 '18 at 10:03

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.