Poate un hash rezistent la coliziune să returneze zero?

Recent, am citit originalul dovada a GCM.

A menționat proprietățile „aproape universal” și „return zero” pentru funcția hash.

Mă întreb dacă există o legătură între cele două, adică

Dacă o funcție hash este rezistentă la coliziuni, atunci este „putin probabil” să returneze zero.

Într-un mod mai formal, avem următoarele:

Pentru $\forall M, M^{'} \in \{0,1\}^{n}, M \ne M^{'}$,

dacă $\mathrm{Pr}\left[H_{K}(M)\oplus H_{K}(M^{'})=0^{n}\ \middle|\ K\stackrel{\$}{ \leftarrow} \{0,1\}^{n}\right] \le \epsilon_{1}$ tine, atunci $\mathrm{Pr}\left[H_{K}(M) =0^{n} \middle|\ K\stackrel{\$}{\leftarrow} \{0,1\}^{n} \right] \le \mathrm{Pr}\left[H_{K}(M)\oplus H_{K}(M^{'})=0^{n}\ \middle|\ K\stackrel{\ \$}{\leftarrow} \{0,1\}^{n}\right] \le \epsilon_{1}$ detine si.

Este corecta aceasta afirmatie?

• Dacă este, cum să demonstrez asta?
• Dacă nu, care este relația dintre rezistența la coliziune și rezultatul zero hash?

Mulțumesc anticipat!

Este corecta aceasta afirmatie?

De fapt, în cazul specific al lui GHASH, nu este.

GHASH are proprietatea că $\forall k: H_k(0^n) = 0$; prin urmare, asta arată că inegalitatea dorită nu este valabilă.

Ceea ce se întâmplă este pentru GHASH, mereu am făcut-o $H_k(M) \oplus H_k(M') = H_k(M \oplus M')$; de asemenea avem $\mathrm{Pr}\left[H_{K}(M) =0^{n} \middle|\ K\stackrel{\$}{\leftarrow} \{0,1\}^{n} \right] \le \epsilon$ pentru $M \ne 0^n$, motiv pentru care inegalitatea originală este valabilă.

Pe o notă secundară, ați întrebat despre „funcțiile hash rezistente la coliziune”; se dovedește că GHASH nu este o funcție hash rezistentă la coliziuni - în schimb, este un "$\Delta$ funcția hash aproape universală"; prima dvs. ecuație (înlocuind $0^n$ cu o variabilă liberă) este în esență definiția.

GHASH nu este o funcție hash rezistentă la coliziuni, deoarece dacă vi se oferă acces Oracle la GHASH, este ușor de recuperat $k$, iar de acolo, este ușor să găsiți coliziuni.