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.


1 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$

  • $\begingroup$ I agree with u regarding my first approach BUT assuming that given $MAC_k$ is $n$ length,( i.e we can't use the first approach) will it be cpa-secure? if yes can u suggest how to make a formal proof? $\endgroup$
    – Mike.R
    Commented Nov 24, 2018 at 10:10
  • $\begingroup$ $MAC_2$ is already length $n$, and your question says nothing else about the length. A specific MAC can change the question. $\endgroup$
    – kelalaka
    Commented Nov 24, 2018 at 10:14
  • $\begingroup$ I am trying to say that if a given MAC was revealing NO information would the scheme be cpa-secure. (or maybe It's already overthinking) $\endgroup$
    – Mike.R
    Commented Nov 24, 2018 at 10:32
  • $\begingroup$ It should be. since you assume the MAC reveals absolutely no information. see From Unpredictability to Indistinguishability: A Simple Construction of Pseudo-Random Functions from MACs $\endgroup$
    – kelalaka
    Commented Nov 24, 2018 at 11:24
  • $\begingroup$ Agree, how would u construct a formal proof in that case? (Approach #2) $\endgroup$
    – Mike.R
    Commented Nov 24, 2018 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.