# Is the collision chance 2^(n/2) of an n-bit tag τ unchanged if reduced to (n/2)-bits using a reduction of τ to some 2^(n/2) order group element?

If $$H(k, Μ) = τ$$, in the context where $$τ$$ is an $$n$$-bit tag produced as a mac on a key, $$k$$, and a message, $$M$$, through a keyed-hash function, $$H$$, is there a function $$F(τ) = T$$ that transforms $$τ$$ into a group element, $$Τ$$, of some group, $$G$$, of order $$2^{\frac{n}{2}}$$, such that:

• The chance of producing any $$T$$ ( where $$F(τ') = F(τ) = T$$; and $$τ' ≠ τ$$ ) is given by $$≈2^{\frac{-n}{2}}$$ ?

It would appear that any $$n$$-bit tag can be reduced to an $$\frac{n}{2}$$-bit tag with the same collision chance if $$F$$ exists.

A naïve and simple $$F$$ one can consider is just $$F(τ) = τ$$ $$mod$$ $$N$$, where $$N$$ is the largest $$\frac{n}{2}$$-bit prime. The idea is that $$τ$$ $$mod$$ $$N$$ has only one collision for all numbers between two multiples of $$N$$, whereas an $$\frac{n}{2}$$-bit hash function has a $$2^{\frac{-n}{4}}$$ collision chance for the same number of unique inputs. There are $$≈2^{\frac{n}{2}}$$ multiples of $$N$$ within the $$n$$-bit space of all possible $$τ$$, therefore, $$τ$$ $$mod$$ $$N$$ should only have $$≈2^{\frac{n}{2}}$$ collisions.

Does such an $$F$$ exist? And, is $$F(τ) = τ$$ $$mod$$ $$N$$ an example of such a function?

No. The birthday paradox applies to all image spaces. Randomly evaluating any function with large input space and an image space of size $$2^{n/2}$$ is expected to produce a collision after roughly $$2^{n/4}$$ evaluations.