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)$
- $k^*=(k^{'},k^{''}) \leftarrow^{\\\$} \{0,1\}^{2\lambda}$;
- $(m_0,m_1) \leftarrow A^{Enc(k^*,·),Dec(k^*,·)}(1^{\lambda})$;
- $b\leftarrow^{\\\$} \{0,1\}$;
- $c^* \leftarrow Enc(k^*,m_b)$;
- $b^{'} \leftarrow A^{Enc(k^*,·),Dec(k^*,·)}(1^{\lambda},c^*)$.
And I want that
$Game (\lambda,0) ≈ Game (\lambda,1)$.
If
- $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?
