Универсальное семейство хеш-функций

Определение

Качественная хеш-функция удовлетворяет (приближенно) условию простого равномерного хеширования: для каждого ключа, независимо от хеширования других ключей, равновероятно помещение его в любую из [math] m [/math] ячеек. Но это условие обычно невозможно проверить, так как распределение вероятностей, с которыми поступают входные данные, как правило, неизвестно. К тому же, вставляемые ключи могут и не быть независимыми. Если наш противник будет умышленно выбирать ключи для хеширования при помощи конкретной хеш-функции, то при некоторых реализациях хеш-таблиц может получиться так, что все ключи будут записаны в одну и ту же ячейку таблицы, что приведет к среднему времени выборки [math] \Theta(n) [/math]. Таким образом, любая фиксированная хеш-функция становится уязвимой. И единственный эффективный выход из данной ситуации — случайный выбор хеш-функции. Такой подход называется универсальным хешированием. Он гарантирует хорошую производительность в среднем, вне зависимости от данных, выбранных нашим противником.

Определение:

Пусть [math] H [/math] — конечное множество хеш-функций, которые отображают пространство ключей [math]\ U [/math] в диапазон [math] \{0, 1, 2, .. , m - 1\} [/math]. Такое множество называется универсальным, если для каждой пары ключей [math] k, l \in U, (k\ne l)[/math] количество хеш-функций [math] h \in H [/math], для которых [math] h(k) = h(l) [/math] не превышает [math] \frac{|H|}{m} [/math].

Иными словами, при случайном выборе хеш-функции из [math] H [/math] вероятность коллизии между различными ключами [math] k, l [/math] не превышает вероятности совпадения двух случайным образом выбранных хеш-значений из множества [math] \{0, 1, 2, .. , m - 1\} [/math], которая равна [math] \frac{1}{m} [/math].

Построение универсального множества хеш-функций

Теорема:

Множество хеш функций [math]H_{p,m}=\{h_{a,b}:a\in Z_p^*,b\in Z_p\}[/math], где [math]h_{a,b}(k)=((ak+b)\mod p)\mod m[/math], [math]Z_p^*=\{1,2,...,p-1\}[/math], [math]Z_p=\{0,1,...,p-1\}[/math], [math]p[/math] — простое число, является универсальным.

Доказательство:

[math]\triangleright[/math]

Рассмотрим [math]k,l\in Z_p:k\ne l[/math]. Пусть для данной хеш-функции [math]h_{a,b}[/math] [math]r=(ak+b)\mod p[/math], [math]s=(al+b)\mod p[/math]. [math]r\ne s[/math], так как [math]r-s\equiv a(k-l)\pmod p[/math], а [math]p[/math] — простое число, [math]a[/math] и [math](k-l)[/math] не равны нулю по модулю [math]p[/math]. Значит, произведение [math]r[/math] и [math]s[/math] также отлично от нуля по модулю [math]p[/math]. Таким, образом, коллизии "по модулю [math]p[/math]" отсутствуют. Более того, каждая из [math]p(p-1)[/math] возможных пар [math](a,b)[/math], приводят к различным парам [math](r,s):r\ne s[/math]. Чтобы доказать это, достаточно рассмотреть возможность однозначного определения [math]a[/math] и [math]b[/math] по заданным [math]r[/math] и [math]s[/math]: [math]a=\left((r-s)((k-l)^{-1}\mod p)\right)\mod p,\ b=(r-ak)\mod p[/math]. Поскольку имеется только [math]p(p-1)[/math] возможных пар [math](r,s):r\ne s[/math], то имеется взаимнооднозначное соответствие между парами [math](a,b)[/math] и парами [math](r,s):r\ne s[/math]. Таким образом, для любых [math]k,l[/math] при равномерном случайном выборе пары [math](a,b)[/math] из [math]Z_p^*\times Z_p[/math], получаемая в результате пара [math](r,s)[/math] может быть с равной вероятностью любой из пар с отличающимися значениями по модулю [math]p[/math]. Отсюда следует, что вероятность того, что различные ключи [math]k,l[/math] приводят к коллизии, равна вероятности того, что [math]r\equiv s\pmod m[/math] при произвольном выборе отличающихся по модулю [math]p[/math] значений [math]r[/math] и [math]s[/math]. Для данного [math]r[/math] имеется [math]p-1[/math] возможное значение [math]s[/math]. При этом число значений [math]s:s\ne r[/math] и [math]s\equiv r\pmod p[/math], не превышает [math]\left\lceil \frac{p}{m}\right\rceil-1\le\frac{p+m-1}{m}-1=\frac{p-1}{m}[/math]. Вероятность того, что [math]s[/math] приводит к коллизии с [math]r[/math] при приведении по модулю [math]m[/math], не превышает [math]\frac{p-1}{m}\cdot\frac{1}{p-1}=\frac{1}{m}[/math]. Значит, [math]\forall k\ne l\in Z_p\ P(h_{a,b}(k)=h_{a,b}(l))\le\frac{1}{m}[/math], что означает, что множество хеш-функций [math]H_{p,m}[/math] является универсальным.

[math]\triangleleft[/math]

Попарная независимость

Определение:

Пусть [math] H [/math] — универсальное семейство хеш-функций. Говорят что оно обладает свойством попарной независимости, если при фиксированных [math] x, y[/math] [math] (0 \le x, y \le m-1)[/math] для каждой пары ключей [math] k, l \in U (k\ne l) [/math] вероятность того, что [math] h(k) = x [/math] и [math] h(l) = y [/math], равна [math] \frac{1}{m^2} + o(\frac{1}{m^2}) [/math].

Построение попарно независимого множества хеш-функций

Теорема:

Семейство хеш функций, описанное выше, также является попарно независимым.

Доказательство:

[math]\triangleright[/math]

Для функции [math]h_{a,b}[/math] получаем [math]x \equiv (ak+b)\bmod p \bmod m[/math] [math]y \equiv (al+b)\bmod p \bmod m[/math] Выразим отсюда [math]a[/math] и [math]b[/math]. Вычтя из первого уравнения второе, получим: [math]x - y = a(k - l)\bmod p \bmod m[/math] Теперь сначала первое домножим на [math]l[/math], и второе на [math]k[/math]. Вычитаем: [math]lx - ky = b(l - k)\bmod p \bmod m[/math] Запишем иначе: [math]x - y \equiv a(k - l)+im \pmod p[/math] [math]lx - ky \equiv b(l - k)+jm \pmod p[/math], где [math] 0 \le i, j \lt \lfloor \frac{p}{m} \rfloor [/math]. Стоит отметить, что эти равенства мы считаем выполненными, если при данных [math]a, b, x[/math] и [math]y[/math] и каких-либо [math]i[/math] и [math]j[/math] они будут верными (исходя из того как мы их получили). [math]k \ne l[/math], [math]p[/math] — простое, тогда [math]a \equiv (k - l)^{-1}(x - y - im) \pmod p[/math] [math]b \equiv (l - k)^{-1}(lx - ky - jm)[/math] [math]\pmod p[/math] Теперь заметим, что [math]a[/math] принимает [math]p[/math] различных значений, а [math]i[/math] — [math]\lfloor \frac{p}{m} \rfloor[/math] значений. Понятно, что для заданных [math]x, y[/math] и [math]a[/math] с вероятностью лишь [math] \frac{1}{m} [/math] найдётся [math]i[/math], обращающий первое равенство в тождество; аналогично и со вторым равенством. Остаётся подытожить наши выкладки. [math]P( [x \equiv (ak+b)\bmod p \bmod m][/math] [math]\wedge[/math] [math][y \equiv (al+b)\bmod p \bmod m])[/math] [math]=[/math] [math]=[/math] [math]P( [a \equiv (k - l)^{-1}(x - y - im)[/math] [math]\pmod p][/math] [math]\wedge[/math] [math][b \equiv (l - k)^{-1}(lx - ky - jm)[/math] [math]\pmod p])[/math] [math]=[/math] [math]=[/math] [math]P( a \equiv (k - l)^{-1}(x - y - im)[/math] [math]\pmod p)[/math] [math]\cdot[/math] [math]P( b \equiv (l - k)^{-1}(lx - ky - jm)[/math] [math]\pmod p)[/math] [math]=[/math] [math]=[/math] [math](\frac{1}{m} + o(\frac{1}{m})) \cdot (\frac{1}{m} + o(\frac{1}{m})) = \frac{1}{m^2} + o(\frac{1}{m^2})[/math] Переход к третьей строчке объясняется тем, что события, объединённые знаком [math]\wedge[/math], независимы (т.к. случайные величины здесь только [math]a[/math] и [math]b[/math]; [math]x, y, k, l[/math] — фиксированы).

[math]\triangleleft[/math]

Источники

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2005. — с. 294. — ISBN 5-8459-0857-4