Универсальное семейство хеш-функций — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Отмена правки 21735 участника Yulya3102 (обсуждение))
м
Строка 1: Строка 1:
 
==Определение==
 
==Определение==
  
Качественная хеш-функция удовлетворяет (приближенно) условию простого равномерного хеширования: для каждого ключа, независимо от хеширования других ключей, равновероятно помещение его в любую из <tex> m </tex> ячеек. Но это условие обычно невозможно проверить, так как распределение вероятностей, с которыми поступают входные данные, как правило, неизвестно. К тому же, вставляемые ключи могут и не быть независимыми. Если наш противник будет умышленно выбирать ключи для хеширования при помощи конкретной хеш-функции, то при некоторых реализациях хеш-таблиц может получиться так, что все ключи будут записанны в одну и ту же ячейку таблицы, что приведет к среднему времени выборки <tex> \theta(n) </tex>. Таким образом,  любая фиксированная хеш-функция становится уязвимой. И единственный эффективный выход из данной ситуации {{---}} случайный выбор хеш-функции. Такой подход называется универсальным хешированием. Он гарантирует хорошую производительность в среднем, вне зависимости от данных, выбранных злым человеком.
+
Качественная хеш-функция удовлетворяет (приближенно) условию простого равномерного хеширования: для каждого ключа, независимо от хеширования других ключей, равновероятно помещение его в любую из <tex> m </tex> ячеек. Но это условие обычно невозможно проверить, так как распределение вероятностей, с которыми поступают входные данные, как правило, неизвестно. К тому же, вставляемые ключи могут и не быть независимыми. Если наш противник будет умышленно выбирать ключи для хеширования при помощи конкретной хеш-функции, то при некоторых реализациях хеш-таблиц может получиться так, что все ключи будут записанны в одну и ту же ячейку таблицы, что приведет к среднему времени выборки <tex> \Theta(n) </tex>. Таким образом,  любая фиксированная хеш-функция становится уязвимой. И единственный эффективный выход из данной ситуации {{---}} случайный выбор хеш-функции. Такой подход называется универсальным хешированием. Он гарантирует хорошую производительность в среднем, вне зависимости от данных, выбранных злым человеком.
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
 
Пусть <tex> H </tex> {{---}} конечное множество хеш-функций, которые отображают пространство ключей <tex>\ U </tex> в диапазон <tex> \{0, 1, 2, .. , m - 1\} </tex>.
 
Пусть <tex> H </tex> {{---}} конечное множество хеш-функций, которые отображают пространство ключей <tex>\ U </tex> в диапазон <tex> \{0, 1, 2, .. , m - 1\} </tex>.
Такое множество называется '''универсальным''', если для каждой пары ключей <tex> k, l \in U </tex> количество хеш-функций <tex> h \in H </tex>, для которых <tex> h(k) = h(l) </tex> не превышает <tex> |H| / m </tex>.
+
Такое множество называется '''универсальным''', если для каждой пары ключей <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 </tex> вероятность коллизии между различными ключами <tex> k, l </tex> не превышает вероятности совпадения двух случайным образом выбранных хеш-значений из множества <tex> \{0, 1, 2, .. , m - 1\} </tex>, которая равна <tex> 1/m </tex>.
+
Иными словами, при случайном выборе хеш-функции из <tex> H </tex> вероятность коллизии между различными ключами <tex> k, l </tex> не превышает вероятности совпадения двух случайным образом выбранных хеш-значений из множества <tex> \{0, 1, 2, .. , m - 1\} </tex>, которая равна <tex dpi = "180"> \frac{1}{m} </tex>.
  
 
==Построение универсального множества хеш-функций==
 
==Построение универсального множества хеш-функций==
Строка 22: Строка 22:
 
<tex>s=(al+b)\mod p</tex>.
 
<tex>s=(al+b)\mod p</tex>.
  
<tex>r\ne s</tex>, так как <tex>r-s\equiv a(k-l)(\mod p)</tex>, а <tex>p</tex> {{---}} простое число, <tex>a</tex> и <tex>(k-l)</tex> не равны нулю по модулю <tex>p</tex>. Значит, произведение <tex>r</tex> и <tex>s</tex> также отлично от нуля по модулю <tex>p</tex>. Таким, образом, коллизии "по модулю <tex>p</tex>" отсутствуют. Более того, каждая из <tex>p(p-1)</tex> возможных пар <tex>(a,b):a\ne0</tex>, приводят к различным парам <tex>(r,s):r\ne s</tex>. Чтобы доказать это, достаточно рассмотреть возможность однозначного определения <tex>a</tex> и <tex>b</tex> по заданным <tex>r</tex> и <tex>s</tex>:
+
<tex>r\ne s</tex>, так как <tex>r-s\equiv a(k-l)(\!\!\!\mod p)</tex>, а <tex>p</tex> {{---}} простое число, <tex>a</tex> и <tex>(k-l)</tex> не равны нулю по модулю <tex>p</tex>. Значит, произведение <tex>r</tex> и <tex>s</tex> также отлично от нуля по модулю <tex>p</tex>. Таким, образом, коллизии "по модулю <tex>p</tex>" отсутствуют. Более того, каждая из <tex>p(p-1)</tex> возможных пар <tex>(a,b):a\ne0</tex>, приводят к различным парам <tex>(r,s):r\ne s</tex>. Чтобы доказать это, достаточно рассмотреть возможность однозначного определения <tex>a</tex> и <tex>b</tex> по заданным <tex>r</tex> и <tex>s</tex>:
  
 
<tex>a=\left((r-s)((k-l)^{-1}\mod p)\right)\mod p,\ b=(r-ak)\mod p</tex>.
 
<tex>a=\left((r-s)((k-l)^{-1}\mod p)\right)\mod p,\ b=(r-ak)\mod p</tex>.
Строка 28: Строка 28:
 
Поскольку имеется только <tex>p(p-1)</tex> возможных пар <tex>(r,s):r\ne s</tex>, то имеется взаимнооднозначное соответствие между парами <tex>(a,b):a\ne0</tex> и парами <tex>(r,s):r\ne s</tex>. Таким образом, для любых <tex>k,l</tex> при равномерном случайном выборе пары <tex>(a,b)</tex> из <tex>Z_p^*\times Z_p</tex>, получаемая в результате пара <tex>(r,s)</tex> может быть с равной вероятностью любой из пар с отличающимися значениями по модулю <tex>p</tex>.
 
Поскольку имеется только <tex>p(p-1)</tex> возможных пар <tex>(r,s):r\ne s</tex>, то имеется взаимнооднозначное соответствие между парами <tex>(a,b):a\ne0</tex> и парами <tex>(r,s):r\ne s</tex>. Таким образом, для любых <tex>k,l</tex> при равномерном случайном выборе пары <tex>(a,b)</tex> из <tex>Z_p^*\times Z_p</tex>, получаемая в результате пара <tex>(r,s)</tex> может быть с равной вероятностью любой из пар с отличающимися значениями по модулю <tex>p</tex>.
  
Отсюда следует, что вероятность того, что различные ключи <tex>k,l</tex> приводят к коллизии, равна вероятности того, что <tex>r\equiv s(\mod m)</tex> при произвольном выборе отличающихся по модулю <tex>p</tex> значений <tex>r</tex> и <tex>s</tex>. Для данного <tex>r</tex> имеется <tex>p-1</tex> возможное значение <tex>s</tex>. При этом число значений <tex>s:s\ne r</tex> и <tex>s\equiv r(\mod p)</tex>, не превышает
+
Отсюда следует, что вероятность того, что различные ключи <tex>k,l</tex> приводят к коллизии, равна вероятности того, что <tex>r\equiv s(\!\!\!\mod m)</tex> при произвольном выборе отличающихся по модулю <tex>p</tex> значений <tex>r</tex> и <tex>s</tex>. Для данного <tex>r</tex> имеется <tex>p-1</tex> возможное значение <tex>s</tex>. При этом число значений <tex>s:s\ne r</tex> и <tex>s\equiv r(\!\!\!\mod p)</tex>, не превышает
  
<tex>\lceil p/m\rceil-1\le((p+m-1)/m)-1=(p-1)/m</tex>.
+
<tex dpi = "150">\left\lceil \frac{p}{m}\right\rceil-1\le\frac{p+m-1}{m}-1=\frac{p-1}{m}</tex>.
  
Вероятность того, что <tex>s</tex> приводит к коллизии с <tex>r</tex> при приведении по модулю <tex>m</tex>, не превышает <tex>((p-1)/m)(p-1)=1/(p-1)=1/m</tex>.
+
Вероятность того, что <tex>s</tex> приводит к коллизии с <tex>r</tex> при приведении по модулю <tex>m</tex>, не превышает <tex dpi = "150">\frac{p-1}{m}(p-1)=\frac{1}{p-1}=\frac{1}{m}</tex>.
  
Значит, <tex>\forall k\ne l\in Z_p\ P(h_{a,b}(k)=h_{a,b}(l))\le1/m</tex>, что означает, что множество хеш-функций <tex>H_{p,m}</tex> является универсальным.
+
Значит, <tex dpi = "150">\forall k\ne l\in Z_p\ P(h_{a,b}(k)=h_{a,b}(l))\le\frac{1}{m}</tex>, что означает, что множество хеш-функций <tex>H_{p,m}</tex> является универсальным.
 
}}
 
}}
  

Версия 19:20, 1 мая 2012

Определение

Качественная хеш-функция удовлетворяет (приближенно) условию простого равномерного хеширования: для каждого ключа, независимо от хеширования других ключей, равновероятно помещение его в любую из [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)(\!\!\!\mod 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):a\ne0[/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):a\ne0[/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(\!\!\!\mod 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(\!\!\!\mod 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}(p-1)=\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]

Источники

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