Is the scheme $(r, Mac_k(r) \oplus m)$ CPA-secure?

Question

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."

1. 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.
2. 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.

Answer 1

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$