# 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. Oct 15, 2018 at 9:43
• @Maeher I've just added the definition. Oct 15, 2018 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. Oct 15, 2018 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. Oct 15, 2018 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. Oct 15, 2018 at 10:03