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

  • $\begingroup$ You should probably provide a definition for unforgeability, as this is not really a standard definition for encryption schemes. $\endgroup$
    – Maeher
    Oct 15, 2018 at 9:43
  • $\begingroup$ @Maeher I've just added the definition. $\endgroup$
    – Myath
    Oct 15, 2018 at 9:52
  • $\begingroup$ Consider that the definition does not rule out being able to transform a ciphertext into a different ciphertext for the same message. $\endgroup$
    – Maeher
    Oct 15, 2018 at 9:56
  • $\begingroup$ @Maeher The criterion $m \notin Q$ does rule out transforming a ciphertext returned from the oracle to a different ciphertext for the same message. $\endgroup$
    – Myath
    Oct 15, 2018 at 9:59
  • $\begingroup$ 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. $\endgroup$
    – Maeher
    Oct 15, 2018 at 10:03

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.