Is the scheme $(r, Mac_k(r) \oplus m)$ CPA-secure? I honestly admit this question is taken from a h.w assignment:


  Prove or refute: the following encryption scheme is CPA-secure: Let $(\text{Gen},  \text{Mac}, \text{Vrfy})$ be a secure MAC with tags of length $n$. Encrypt a message $m \in (0,1)^n$ by choosing a random $r \in (0, 1)^n$ and outputting $(r, \text{Mac}_k(r) \oplus m)$.


As I just have started with this course, please point out if my approach or my usage of technical terms are incorrect or imprecise. I am following the book named "Introduction to modern crypthography."


My first approach was to refute the claim. I thought about giving an example for a MAC that is secure but yields a non-secure scheme. For instance, consider the MAC which appends a zero at the end. As far as I can tell,  a PRF $f$ can be used as a MAC, so I could define something like $\text{Mac}(x) = f(x) ||0$ or, even, use some other MAC instead of $f$. It's easy to see that the scheme will not be CPA-secure as an adversary's decision can base solely on the last bit of the message.
In contrast to my first approach, I would actually like to prove it. My intuition tells me, given a random $r$, $\text{Mac}_k(r)$ should be also random. Thus, I get a random string XOR'ed with $m$ (which actually seems like an OTP), which should be secure.
The problem is that I don't know how to complete my proof by reduction. If I build an attacker $A'$ how it should interact with the other attacker $A$? I would start by assuming the scheme is NOT CPA-secure and would come to a contradiction by giving a MAC which yields a scheme which is not CPA secure---but I am very confused on how to do it.


It would be really nice if I could get some clues or related examples on how to formalize my line of thinking.
Your first approach was almost correct. Your question says nothing about the shape of the secure MAC except the length. The secure MAC only says that you cannot forge a new tag from the previous ones. 

Let $MAC_1$ be a secure map with output length $n-1$ than

$$MAC_2(m) = MAC_1(m)\|0$$
will be a secure MAC with output length $n$. 

Now, put $MAC_2$ into your scheme and use 0 to distinguish the messages. The adversary sends two messages $m_1$ and $m_2$ such that $\operatorname{lsb}(m_1) \neq \operatorname{lsb}(m_2)$. When the messages returned he can distinguish just by observing the lsb's of $MAC(r_i)\oplus m_i$