I'm preparing myself to exam, but I have a lot of troubles with rigorous proofs. It's the task from two-years ago exam. At the bottom I reminded one definition.
Let $(Gen_E,Enc,Dec)$ be an IND-CPA-secure encryption scheme.
Let $(Gen_M,Mac,Vrfy)$ be a secure MAC.
Define an encryption scheme as follows:
$Gen'$ upon input $1^n$, generates $k_1 \leftarrow Gen_E(1^n), k_2 \leftarrow Gen_M(1^n)$,
$Enc'$ upon input key $(k_1,k_2)$ and message $m \in \lbrace 0,1 \rbrace^*$, computes $c=Enc_{k_1}(m)$ and $t=Mac_{k_2}(m)$ and outputs $(c,t)$.
$Dec'$ upon input key $(k_1,k_2)$ and ciphertext $(c,t)$, outputs $Dec_{k_1}(c)$ if $Vrfy_{k_2}\left( Dec_{k_1}(c),t \right)=1$ and outputs $\perp \not\in \mathcal{M}_n$ otherwise.
Prove that this construction is not even IND-CPA-secure when the Mac algorithm is deterministic.
Reminder (IND-CPA-secure).
An (efficient secret-key) encryption scheme $(Gen,Enc,Dec)$ is IND-CPA-secure if for any PPT adversary $\mathcal{A}$ it holds that $Pr[PrivK^{cpa}_{\mathcal{A}}(n)=1]-1/2$ is negligible function, where $PrivK^{cpa}_{\mathcal{A}}(n)$ denotes the output of the following experiment:
(a) Let $k \leftarrow Gen(1^n)$
(b) The adversary $\mathcal{A}$ is given input $1^n$ and oracle access to $Enc_k(\cdot)$. It outputs a pair of messages $m_0, m_1 \in \mathcal{M}_n$ of the same length.
(c) Let $b \in \lbrace 0,1 \rbrace$ be chosen uniformly at random. Then a ciphertext $c \leftarrow Enc_k(m_b)$ is computed and given to $\mathcal{A}$.
(d) $\mathcal{A}$ is given the challenge ciphertext $c$ and oracle access to $Enc_k(\cdot)$. It outputs a bit $b'$.
(e) The output of the experiment is $1$ if $b'=b$, and $0$ otherwise.
If you could help me with the rigorous proof, I'd be really grateful for your time.