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.

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

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

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.