Is this MAC scheme secure?

Question

Say we have a computationally secure Message Authentication Code scheme (Gen, Tag, Ver).

Let $Tag'_k(m):=$ first half bits of $Tag_k(m)$. Let's assume the range of tags is $n$bits.

Is (Gen, Tag', Ver) secure?

An efficient adversary that breaks (Gen, Tag, Ver) can't be constructed using an effecient adversary that breaks (Gen, Tag', Ver) because the former still would have to guess the last $\frac{n}{2}$ bits. So I want to say it's not secure.

Yet I want to say it is secure because I can't think of an algorithm that can efficiently break (Gen, Tag', Ver).

Answer 1

It is not secure in general, but not insecure in general either.

For example, you can get a MAC algorithm for which it would be secure by concatenating constant data to a secure MAC. $Tag_k(m) = M_k(m)||0^n$ is a secure MAC if $M$ is. And clearly taking the first half of that is a secure MAC if $n = |M_k(m)|$.

On the other hand, reverse the order of the constant and non-constant part above and you get a MAC scheme for which taking the first half is very insecure.

If your secure MAC algorithm is based on a PRF, you can take the first half and have a MAC that is secure, but easier to guess randomly. (Because a secure PRF is a secure MAC and a truncated PRF is still a PRF.) Many MAC algorithms like HMAC and CMAC, for example, can be truncated for this reason.