# Construction of a SKE scheme based on a PRF family and on a MAC with UF-CMA security. Is the scheme secure?

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

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?

• 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. Commented Jan 18, 2023 at 1:28