Score:1

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?

in flag

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?

Score:2
ru flag

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.

in flag
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?
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.