Este șansa de coliziune 2^(n/2) a unei etichete de n biți Ï neschimbată dacă este redusă la (n/2)-biți folosind o reducere de Ï la un element de grup de ordine de 2^(n/2)?

Dacă $H(k, Î) = Ï$, în contextul în care $Ï$ este o $n$-pic etichetă produsă ca un mac pe o cheie, $k$și un mesaj, $M$, printr-o funcție hash cu taste, $H$, există o funcție $F(Ï) = T$ care se transformă $Ï$ într-un element de grup, $Τ$, a unui grup, $G$, de ordine $2^{\frac{n}{2}}$, astfel încât:

• Șansa de a produce oricare $T$ ( Unde $F(Ï') = F(Ï) = T$; și $Ï' â Ï$ ) este dat de $â2^{\frac{-n}{2}}$ ?

S-ar părea că oricare $n$-pic eticheta poate fi redusă la un $\frac{n}{2}$-pic etichetă cu aceeași șansă de coliziune dacă $F$ există.

Un naiv și simplu $F$ se poate considera că este just $F(Ï) = Ï$ $mod$ $N$, Unde $N$ este cel mai mare $\frac{n}{2}$-pic prim. Ideea este că $Ï$ $mod$ $N$ are o singură coliziune pentru toate numerele între doi multipli de $N$, în timp ce an $\frac{n}{2}$-pic funcția hash are a $2^{\frac{-n}{4}}$ șansa de coliziune pentru același număr de intrări unice. Sunt $â2^{\frac{n}{2}}$ multipli de $N$ în cadrul $n$-pic spatiul a tot posibilul $Ï$, prin urmare, $Ï$ $mod$ $N$ ar trebui doar să aibă $â2^{\frac{n}{2}}$ ciocniri.

Are un astfel de $F$ exista? Si este $F(Ï) = Ï$ $mod$ $N$ un exemplu de astfel de funcție?