Why is an Encrypt-and-MAC scheme with deterministic MAC not IND-CPA secure? 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.
I'm a little bit confused by your notation (what's $1^n$ supposed to mean? based on context, it looks like a key or a passphrase, but I've never seen that notation before), but the exercise itself seems to just amount to proving that an Encrypt-and-MAC scheme, using a deterministic MAC of the plaintext which is sent in plain, cannot be IND-CPA secure.

To prove that, keep in mind that there's nothing in the IND-CPA definition saying that the adversary cannot use the encryption oracle on the challenge messages.  Since the MAC is deterministic and sent in plain, the adversary can just compare the MAC parts of two encrypted messages to determine (with very high probability) whether they encode the same plaintext.