Consider the following construction of a SKE scheme $\Pi^*=(Enc^*,Dec^*)$ based on a PRF family $F=\{F_k:\{0,1\}^n\rightarrow \{0,1\}^n\}_{k\in\{0,1\}^\lambda}$ and on a MAC $ Tag:\{0,1\}^\lambda \times \{0,1\}^n \rightarrow \{0,1\}^\lambda$ with UF-CMA security.

Key Generation: The key generation algorithm returns a random key $k^*=(k^{'},k^{''})$ where $k^{'},k^{''} \in \{0,1\}^\lambda$.

Encryption: The encryption algorirhm takes $k^*=(k^{'},k^{''})$ and $m \in \{0,1\}^n$ as input, and it returns $c^*=(r,c^{'},c^{''})$ where $r \leftarrow^{\\\$} \{0,1\}^n, c^{'}=F_{k^{'}}(r)⊕ m $ and $c^{''}=Tag_{k^{''}}(c^{'})$.

Decryption: The decryption algorithm takes $k^*=(k^{'},k^{''})$ and $c^*=(r,c^{'},c^{''})$ and outputs $m=F_{k^{'}}(r)⊕ c^{'}$ if and only if $Tag_{k^{''}}(c^{'})=c^{''}$, othwrwise it outputs 0.

Prove or disprove $\Pi^*$ achieves CCA security.

I want to prove that $\Pi^*$ is secure, so I'm considering the following game $Game(\lambda,b)$

  1. $k^*=(k^{'},k^{''}) \leftarrow^{\\\$} \{0,1\}^{2\lambda}$;
  2. $(m_0,m_1) \leftarrow A^{Enc(k^*,·),Dec(k^*,·)}(1^{\lambda})$;
  3. $b\leftarrow^{\\\$} \{0,1\}$;
  4. $c^* \leftarrow Enc(k^*,m_b)$;
  5. $b^{'} \leftarrow A^{Enc(k^*,·),Dec(k^*,·)}(1^{\lambda},c^*)$.

And I want that $Game (\lambda,0) ≈ Game (\lambda,1)$.


  • $c^{'}_b=F_{k^{'}}(r)⊕ m_b $
  • $c^{''}_b=Tag_{k^{''}}(c^{'}_b)$

Since $r$ and $b$ are random and $F_{k^{'}}$ is a PRF than $c^{'}_0$ and $c^{'}_1$ have the same distribution.

Now, since $Tag_{k^{''}}$ is UF-CMA, then $Tag_{k^{''}}(c^{'}_0)$ and $Tag_{k^{''}}(c^{'}_1)$ have the same distribution too.

Hence, it is impossible to distinguish $(c^{'}_0,c^{''}_0)$ from $(c^{'}_0,c^{''}_0)$ and therefore $Game (\lambda,0) ≈ Game (\lambda,1)$.

Is that all right?

  • 1
    $\begingroup$ This is just encrypt-then-MAC but you don't take a MAC of the entire ciphertext. It turns out that this scheme is not CCA-secure. Your sketch considers indistinguishability of the ciphertexts, but does not account for the adversary's view of its decryption oracle. $\endgroup$
    – Mikero
    Commented Jan 18, 2023 at 1:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.