# Is this MAC scheme secure?

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

• For the usual MAC algorithms the result is $\frac{n}2$ less secure. But it may be possible to construct a MAC where the first and second parts of the authentication tag are related in such a way that it is less secure. Security isn't a boolean though; there is no secure / not secure, only more secure or less secure. And even that may be subjective. – Maarten Bodewes Nov 25 '15 at 21:30

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)|$.