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?
