Может ли устойчивый к коллизиям хеш вернуть ноль?

Недавно я читал оригинал доказательство ГКМ.

В нем упоминаются свойства «почти универсального» и «возвращающего ноль» для хэш-функции.

Интересно, есть ли связь между ними, т.

Если хеш-функция устойчива к коллизиям, то она «маловероятно» возвращает ноль.

Более формально имеем следующее:

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

если $\mathrm{Pr}\left[H_{K}(M)\oplus H_{K}(M^{'})=0^{n}\ \middle|\ K\stackrel{\$}{ \leftarrow} \{0,1\}^{n}\right] \le \epsilon_{1}$ держится, то $\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}$ также держит.

Это утверждение верно?

• Если да, то как это доказать?
• Если нет, то какова связь между устойчивостью к коллизиям и нулевым результатом хеширования?

Заранее спасибо!

Это утверждение верно?

На самом деле, в конкретном случае GHASH это не так.

GHASH обладает тем свойством, что $\для всех k: H_k(0^n) = 0$; следовательно, это показывает, что желаемое неравенство не выполняется.

Что происходит для GHASH, у нас всегда есть $H_k(M) \oplus H_k(M') = H_k(M \oplus M')$; у нас также есть $\mathrm{Pr}\left[H_{K}(M) =0^{n} \middle|\ K\stackrel{\$}{\leftarrow} \{0,1\}^{n} \right] \le \epsilon$ за $M \ne 0^n$, поэтому исходное неравенство выполняется.

Кстати, вы спросили о «устойчивых к коллизиям хеш-функциях»; оказывается, что GHASH не является хэш-функцией, устойчивой к коллизиям, — вместо этого это "$\Дельта$ почти универсальная хеш-функция"; ваше первое уравнение (заменяющее $0^n$ со свободной переменной) по существу является определением.

GHASH не является хэш-функцией, устойчивой к коллизиям, потому что, если вам предоставлен доступ Oracle к GHASH, его легко восстановить. $к$, и оттуда легко найти коллизии.