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?


1 Answer 1


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.

  • $\begingroup$ Thank you for the insight! Do you have a source beyond the birthday paradox wiki which explains more deeply this property of image spaces on random functions? $\endgroup$
    – aiootp
    Commented Oct 2, 2021 at 20:00

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.