Универсальное семейство хеш-функций — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 26 промежуточных версий 8 участников) | |||
Строка 1: | Строка 1: | ||
− | == | + | ==Определение== |
− | Качественная хеш-функция удовлетворяет (приближенно) условию простого равномерного хеширования: для каждого ключа, независимо от хеширования других ключей, равновероятно помещение его в любую из <tex> m </tex> ячеек. Но это условие обычно невозможно проверить, так как распределение вероятностей, с которыми поступают входные данные, как правило, неизвестно. К тому же, вставляемые ключи могут и не быть независимыми. Если | + | Качественная хеш-функция (англ. ''hash function'') удовлетворяет (приближенно) условию простого равномерного [[Хеширование|хеширования]]: для каждого ключа, независимо от хеширования других ключей, равновероятно помещение его в любую из <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| | + | Такое множество называется '''универсальным''' (англ. ''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 </tex> вероятность коллизии между различными ключами <tex> k, l </tex> не превышает вероятности совпадения двух случайным образом выбранных хеш-значений из множества <tex> \{0, 1, 2, .. , m - 1\} </tex>, которая равна <tex> 1 | + | Иными словами, при случайном выборе хеш-функции из <tex> H </tex> вероятность коллизии между различными ключами <tex> k, l </tex> не превышает вероятности совпадения двух случайным образом выбранных хеш-значений из множества <tex> \{0, 1, 2, .. , m - 1\} </tex>, которая равна <tex dpi = "180"> \frac{1}{m} </tex>. |
− | == | + | ==Построение универсального множества хеш-функций== |
+ | {{Теорема | ||
+ | |statement= | ||
+ | Множество хеш функций <tex>H_{p,m}=\{h_{a,b}:a\in Z_p^*,b\in Z_p\}</tex>, где <tex>h_{a,b}(k)=((ak+b)\bmod p)\bmod m</tex>, <tex>Z_p^*=\{1,2,\dots,p-1\}</tex>, <tex>Z_p=\{0,1,\dots,p-1\}</tex>, <tex>p</tex> {{---}} простое число, является универсальным. | ||
+ | |proof= | ||
+ | Рассмотрим <tex>k,l\in Z_p:k\ne l</tex>. Пусть для данной хеш-функции <tex>h_{a,b}</tex> | ||
− | * | + | <tex>r=(ak+b)\bmod p</tex>, |
+ | |||
+ | <tex>s=(al+b)\bmod p</tex>. | ||
+ | |||
+ | <tex>r\ne s</tex>, так как <tex>r-s\equiv a(k-l)\pmod 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)</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}\bmod p)\right)\bmod p,\ b=(r-ak)\bmod p</tex>. | ||
+ | |||
+ | Поскольку имеется только <tex>p(p-1)</tex> возможных пар <tex>(r,s):r\ne s</tex>, то имеется взаимнооднозначное соответствие между парами <tex>(a,b)</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\pmod 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\pmod p</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 dpi = "150">\frac{p-1}{m}\cdot\frac{1}{p-1}=\frac{1}{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> является универсальным. | ||
+ | }} | ||
+ | |||
+ | == Попарная независимость == | ||
+ | |||
+ | {{Определение | ||
+ | |definition= | ||
+ | Пусть <tex> H </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(k) = x </tex> и <tex> h(l) = y </tex>, равна <tex dpi = "150"> \frac{1}{m^2} + o(\frac{1}{m^2}) </tex>. | ||
+ | }} | ||
+ | |||
+ | ==Построение попарно независимого множества хеш-функций== | ||
+ | {{Теорема | ||
+ | |statement= | ||
+ | Семейство хеш функций, описанное выше, также является попарно независимым. | ||
+ | |proof= | ||
+ | Для функции <tex>h_{a,b}</tex> получаем | ||
+ | |||
+ | <tex>x = (ak+b)\bmod p \bmod m</tex> | ||
+ | |||
+ | <tex>y = (al+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>k</tex>. Вычитаем: | ||
+ | |||
+ | <tex>lx - ky = b(l - k)\bmod p \bmod m</tex> | ||
+ | |||
+ | Запишем иначе: | ||
+ | |||
+ | <tex>x - y \equiv a(k - l)+im \pmod p</tex> | ||
+ | |||
+ | <tex>lx - ky \equiv b(l - k)+jm \pmod p</tex>, | ||
+ | |||
+ | где <tex dpi = "135"> 0 \le i, j < \lfloor \frac{p}{m} \rfloor </tex>. | ||
+ | |||
+ | Стоит отметить, что эти равенства мы считаем выполненными, если при данных <tex>a, b, x</tex> и <tex>y</tex> и '''каких-либо''' <tex>i</tex> и <tex>j</tex> они будут верными (исходя из того как мы их получили). | ||
+ | |||
+ | <tex>k \ne l</tex>, <tex>p</tex> {{---}} простое, тогда | ||
+ | |||
+ | <tex>a \equiv (k - l)^{-1}(x - y - im) \pmod p</tex> | ||
+ | |||
+ | <tex>b \equiv (l - k)^{-1}(lx - ky - jm)</tex> <tex>\pmod p</tex> | ||
+ | |||
+ | Теперь заметим, что <tex>a</tex> принимает <tex>p</tex> различных значений, а <tex>i</tex> {{---}} <tex dpi = "130">\lfloor \frac{p}{m} \rfloor</tex> значений. Понятно, что для заданных <tex>x, y</tex> и <tex>a</tex> с вероятностью лишь <tex dpi = "130"> \frac{1}{m} </tex> найдётся <tex>i</tex>, обращающий первое равенство в тождество; аналогично и со вторым равенством. | ||
+ | |||
+ | Остаётся подытожить наши выкладки. | ||
+ | |||
+ | <tex>P( [x = (ak+b)\bmod p \bmod m]</tex> <tex>\wedge</tex> <tex>[y = (al+b)\bmod p \bmod m])</tex> | ||
+ | <tex>=</tex> | ||
+ | |||
+ | <tex>=</tex> | ||
+ | <tex>P( [a \equiv (k - l)^{-1}(x - y - im)</tex> <tex>\pmod p]</tex> <tex>\wedge</tex> <tex>[b \equiv (l - k)^{-1}(lx - ky - jm)</tex> <tex>\pmod p])</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>=</tex> | ||
+ | <tex dpi = "130">(\frac{1}{m} + o(\frac{1}{m})) \cdot (\frac{1}{m} + o(\frac{1}{m})) = \frac{1}{m^2} + o(\frac{1}{m^2})</tex> | ||
+ | |||
+ | Переход к третьей строчке объясняется тем, что события, объединённые знаком <tex>\wedge</tex>, независимы (т.к. случайные величины здесь только <tex>a</tex> и <tex>b</tex>; <tex>x, y, k, l</tex> {{---}} фиксированы). | ||
+ | }} | ||
+ | |||
+ | ==Источники информации== | ||
+ | |||
+ | * Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2005. — с. 294. — ISBN 5-8459-0857-4 | ||
+ | |||
+ | [[Категория: Дискретная математика и алгоритмы]][[Категория:Хеширование]] |
Текущая версия на 19:12, 4 сентября 2022
Определение
Качественная хеш-функция (англ. hash function) удовлетворяет (приближенно) условию простого равномерного хеширования: для каждого ключа, независимо от хеширования других ключей, равновероятно помещение его в любую из ячеек. Но это условие обычно невозможно проверить, так как распределение вероятностей, с которыми поступают входные данные, как правило, неизвестно. К тому же, вставляемые ключи могут и не быть независимыми. Если наш противник будет умышленно выбирать ключи для хеширования при помощи конкретной хеш-функции, то при некоторых реализациях хеш-таблиц может получиться так, что все ключи будут записаны в одну и ту же ячейку таблицы, что приведет к среднему времени выборки . Таким образом, любая фиксированная хеш-функция становится уязвимой. И единственный эффективный выход из данной ситуации — случайный выбор хеш-функции. Такой подход называется универсальным хешированием. Он гарантирует хорошую производительность в среднем, вне зависимости от данных, выбранных нашим противником.
Определение: |
Пусть | — конечное множество хеш-функций, которые отображают пространство ключей в диапазон . Такое множество называется универсальным (англ. universal), если для каждой пары ключей количество хеш-функций , для которых не превышает .
Иными словами, при случайном выборе хеш-функции из вероятность коллизии между различными ключами не превышает вероятности совпадения двух случайным образом выбранных хеш-значений из множества , которая равна .
Построение универсального множества хеш-функций
Теорема: |
Множество хеш функций , где , , , — простое число, является универсальным. |
Доказательство: |
Рассмотрим . Пусть для данной хеш-функции, . , так как , а — простое число, и не равны нулю по модулю . Значит, произведение и также отлично от нуля по модулю . Таким, образом, коллизии "по модулю " отсутствуют. Более того, каждая из возможных пар , приводят к различным парам . Чтобы доказать это, достаточно рассмотреть возможность однозначного определения и по заданным и : . Поскольку имеется только возможных пар , то имеется взаимнооднозначное соответствие между парами и парами . Таким образом, для любых при равномерном случайном выборе пары из , получаемая в результате пара может быть с равной вероятностью любой из пар с отличающимися значениями по модулю .Отсюда следует, что вероятность того, что различные ключи приводят к коллизии, равна вероятности того, что при произвольном выборе отличающихся по модулю значений и . Для данного имеется возможное значение . При этом число значений и , не превышает. Вероятность того, что Значит, приводит к коллизии с при приведении по модулю , не превышает . , что означает, что множество хеш-функций является универсальным. |
Попарная независимость
Определение: |
Пусть | — универсальное семейство хеш-функций. Говорят что оно обладает свойством попарной независимости(англ. pairwise independence), если при фиксированных для каждой пары ключей вероятность того, что и , равна .
Построение попарно независимого множества хеш-функций
Теорема: |
Семейство хеш функций, описанное выше, также является попарно независимым. |
Доказательство: |
Для функции получаем
Выразим отсюда и . Вычтя из первого уравнения второе, получим:
Теперь сначала первое домножим на , и второе на . Вычитаем:
Запишем иначе:
, где .Стоит отметить, что эти равенства мы считаем выполненными, если при данных и и каких-либо и они будут верными (исходя из того как мы их получили)., — простое, тогда
Теперь заметим, что принимает различных значений, а — значений. Понятно, что для заданных и с вероятностью лишь найдётся , обращающий первое равенство в тождество; аналогично и со вторым равенством.Остаётся подытожить наши выкладки.
Переход к третьей строчке объясняется тем, что события, объединённые знаком , независимы (т.к. случайные величины здесь только и ; — фиксированы). |
Источники информации
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2005. — с. 294. — ISBN 5-8459-0857-4