Изменения

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

Такое множество называется '''универсальным'''(англ. ''universal''), если для каждой пары ключей <tex> k, l \in U, (k\ne l)</tex> количество хеш-функций <tex> h \in H </tex>, для которых <tex> h(k) = h(l) </tex> не превышает <tex dpi = "180"> \frac{|H|}{m} </tex>.

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

<tex>r=(ak+b)\mod bmod p</tex>,

<tex>s=(al+b)\mod bmod p</tex>.

<tex>a=\left((r-s)((k-l)^{-1}\mod bmod p)\right)\mod bmod p,\ b=(r-ak)\mod bmod p</tex>.

Говорят что оно обладает свойством '''попарной независимости'''(англ. ''pairwise independence''), если при фиксированных <tex> x, y</tex> <tex> (0 \le x, y \le m-1)</tex> для каждой пары ключей <tex> k, l \in U, (k\ne l) </tex> количество хеш-функций <tex> h \in H </tex>вероятность того, для которых что <tex> h(k) = x </tex> и <tex> h(l) = y </tex> не превышает , равна <tex dpi = "180150"> \frac{|H|1}{m^2} + o(\frac{1}{m^2}) </tex>.

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

<tex>x = (ak+b)\bmod p \equiv bmod m</tex> <tex>y = (akal+b)\bmod p \bmod m</tex> Выразим отсюда <tex>a</tex> и <tex>b</tex>. Вычтя из первого уравнения второе, получим: <tex>x - y = a(k - l)\bmod p \bmod m</tex> Теперь сначала первое домножим на <tex>l</tex> , и второе на <tex>modk</tex> . Вычитаем: <tex>lx - ky = b(l - k)\bmod p\bmod m</tex>  Запишем иначе: <tex>modx - y \equiv a(k - l)+im \pmod p</tex> <tex>lx - ky \equiv b(l - k)+jm \pmod p</tex> , где <texdpi = "135">0 \le i, j < \lfloor \frac{p}{m} \rfloor </tex>.

Стоит отметить, что эти равенства мы считаем выполненными, если при данных <tex>y \equiv (al+a, b), x</tex> и <tex>mody</tex> и '''каких-либо''' <tex>pi</tex> и <tex>mod</tex> <tex>mj</tex>они будут верными (исходя из того как мы их получили).

<tex>x a \equiv ak+b+(k - l)^{-1}(x - y - im</tex> <tex>) \pmod p</tex>

<tex>y b \equiv al+b+(l - k)^{-1}(lx - ky - jm)</tex> <tex>\pmod p</tex>,

где Теперь заметим, что <tex>a</tex> принимает <tex>p</tex> различных значений, а <tex>i</tex> {{---}} <texdpi = "130"> 0 \le ilfloor \frac{p}{m} \rfloor</tex> значений. Понятно, что для заданных <tex>x, j y< /tex> и <tex>a</tex> с вероятностью лишь <tex dpi = "130"> \frac{p1}{m} </tex> найдётся <tex>i</tex>, обращающий первое равенство в тождество; аналогично и со вторым равенством.

Стоит отметить, что эту систему считаем верной если '''при каких-либо''' <tex>i</tex> и <tex>j</tex> входящие в неё равенства будут вернымиОстаётся подытожить наши выкладки.

Выразим отсюда <tex>aP( [x = (ak+b)\bmod p \bmod m]</tex> <tex>\wedge</tex> и <tex>[y = (al+b)\bmod p \bmod m])</tex> <tex>=</tex>. Вычтя из первого уравнения второе получим

<tex>x - y =</tex><tex>P( [a \equiv a(k - l)^{-1}(x - y - im)</tex> <tex>mod\pmod p]</tex> <tex>p\wedge</tex> <tex>[b \equiv (l - k)^{-1}(lx - ky - jm)</tex> <tex>\pmod mp])</tex> <tex>=</tex>

Теперь сначала первое домножим на <tex>=</tex><tex>P( a \equiv (k - l)^{-1}(x - y - im)</tex>, и второе на <tex>\pmod p)</tex> <tex>\cdot</tex> <tex>P( b \equiv (l - k)^{-1}(lx - ky - jm)</tex> <tex>\pmod p)</tex> <tex>=</tex>; вычитая получим

<tex>lx - ky \equiv b(l - k)=</tex> <texdpi = "130">mod</tex> <tex>p</tex> <tex>(\frac{1}{m} + o(\frac{1}{m})) \cdot (\frac{1}{m} + o(\frac{1}{m})) = \frac{1}{m^2} + o(\pmod frac{1}{m^2})</tex>

==Источникиинформации==