Просмотр кода страницы Универсальное хеширование

'''Универса́льное хеши́рование''' ({{lang-en|Universal hashing}}) — это вид [[хеширование|хеширования]], при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному [[алгоритм]]у<ref name=CW79>
{{статья
|заглавие=Universal Classes of Hash Functions
|издание={{Нп3|Journal of Computer and System Sciences}}
|том=18
|номер=2
|страницы=143—154
|doi=10.1016/0022-0000(79)90044-8
|id=Conference version in STOC'77
|язык=en
|автор=Carter, Larry; {{Нп3|Wegman, Mark N.|Wegman, Mark N.||Mark N. Wegman}}
|год=1979
|тип=journal}}</ref><ref name=Mikkel>Thorup, Mikkel, [http://www.diku.dk/summer-school-2014/course-material/mikkel-thorup/hash.pdf_copy|High Speed Hashing for Integers and Strings]{{Недоступная ссылка|date=Июнь 2019 |bot=InternetArchiveBot }}, Cornell University Library, July 15, 2014</ref>. Такой подход обеспечивает равномерное хеширование: для очередного ключа вероятности помещения его в любую ячейку совпадают. Известно несколько семейств универсальных хеш-функций, которые имеют многочисленные применения в [[Информатика|информатике]], в частности в [[Хеш-таблица|хеш-таблицах]], [[Вероятностный алгоритм|вероятностных алгоритмах]] и [[Криптография|криптографии]].

== Введение ==
{{Смотрите также|Хеширование}}

Впервые понятие универсального хеширования было введено в статье<ref name=CW79/> [[Картер, Ларри|Картера]] и {{нп4|Вегман, Марк|Вегмана|en|Mark N. Wegman}} в 1979 году.

Изначально универсальное хеширование было разработано как независящий от входных данных алгоритм, работающий в среднем за линейное время и предназначенный для хранения и извлечения ключей из хеш-таблицы. Под независимостью от входных данных подразумевается следующее: для любой [[последовательность|последовательности]] входных данных соответствующие хеш-значения элементов последовательности будут [[Дискретное равномерное распределение|равномерно распределены]] по хеш-таблице. При выполнении этого условия среднее время работы алгоритма для любых данных оказывается сравнимым со временем работы хеш-функции, используемой для распределения заранее известных данных<ref name=CW79/>.

Созданный алгоритм универсального хеширования представлял собой случайный выбор хеш-функции из некоторого набора хеш-функций(называемого универсальным семейством хеш-функций), обладающих определёнными свойствами. Авторами было показано, что в случае универсального хеширования число обращений к хеш-таблице (в среднем по всем функциям из семейства) для произвольных входных данных оказывается очень близким теоретическому минимуму для случая фиксированной хеш-функции со случайно распределёнными входными данными<ref name=CW79/>.

Используя универсальное хеширование, авторы хотели<ref name=CW79/>:
# Избавиться от необходимости предполагать вид входных данных.
# Устранить зависимость времени работы хеширования от вида входных данных.
# Добиться уменьшения числа [[Коллизия хеш-функции|коллизий]].

В работе<ref name=CW79/> Вегмана и Картера универсальное хеширование было применено для построения хеш-таблицы, хотя позднее универсальное хеширование получило применение и в других областях(см. [[#Применение]]).

== Определение универсального семейства хеш-функций ==
Пусть <math>U</math> — [[множество]] ключей, <math>H</math> — конечное множество хеш-функций, отображающих <math>U</math> во множество <math>\left \{ 0,1,..,m-1 \right \}</math>. Возьмем произвольные <math>h \in H</math> и <math>x,y \in U</math> и определим функцию коллизий <math>\delta _h (x,y)</math>:

<math>\delta _h (x,y) = \begin{cases}
  1,  & \mbox{if }  x \ne y \mbox{ and } h(x) = h(y)\\
  0, & \mbox{otherwise}
\end{cases}</math>

Если <math>\delta _h (x,y) = 1</math>, то говорят, что имеет место ''коллизия''. Можно определить функцию коллизии не для отдельных элементов <math>x,y,h</math>, а для целого множества элементов — для этого надо произвести [[сложение]] функций коллизий по всем элементам из множества. Например, если <math>H</math> — множество хеш-функций, <math>x \in U</math>, <math>S \subset U</math>, то для функции коллизии <math>\delta _H (x,S)</math> получим:

<math>\delta _H (x,S) = \sum_{h \in H} \sum_{y \in S} \delta _h (x,y)</math>

Причём порядок суммирования не имеет значения.

'''Определение.''' Семейство хеш-функций <math>H</math> называется '''универсальным'''<ref name=CW79/>, если
: <math> \forall x, y \in U \longrightarrow \delta _H (x,S) = \frac{\left | H \right |}{m}.</math>

Можно дать другое определение, эквивалентное данному.

'''Определение'''. Семейство хеш-функций <math>H</math> называется универсальным<ref>
{{книга
|заглавие=Randomized Algorithms
|издательство=[[Издательство Кембриджского университета|Cambridge University Press]]
|год=1995
|isbn=0-521-47465-5
|страницы=216—217
|язык=und
|автор=Motwani, Rajeev; Raghavan, Prabhakar
}}
</ref>{{sfn|Cormen|2001|pp=234—235}}, если
: <math>\forall x, y \in U, ~ x\ne y: ~~ \Pr_{h\in H} [h(x) = h(y)] \le \frac{1}{m}</math>

== Свойства универсального семейства хеш-функций в случае его применения к хеш-таблицам ==
Следующая [[теорема]] определяет нижнюю границу функции <math>\delta _h (x,y)</math> для произвольного семейства хеш-функций<ref name=CW79/>.

'''Теорема 1.'''Для любого семейства(не обязательно универсального) хеш-функций <math>H</math> существуют <math>x,y \in U</math> такие, что

<math>\delta _H (x,S) > \frac{\left | H \right |}{m} - \frac{\left | H \right |}{\left | U \right |}</math>

Из теоремы 1 следует, что нижняя граница функции коллизии близка к <math>\frac{\left | H \right |}{m}</math> в случае, когда <math>\left | U \right | </math> много больше <math>m</math>. В действительности, часто так и бывает. Например, пусть [[компилятор]] ставит в соответствие тысяче [[Переменная (программирование)|переменных]] последовательности из семи английских букв. Тогда <math>m = 1000</math>, а <math>\left | U \right | = 26^7</math>

Для универсального семейства хеш-функций это означает, что верхняя и нижняя границы функции коллизии довольно близки<ref name=CW79/>.

В статье<ref name=CW79/> универсальное хеширование применялось для организации [[Хеш-таблица#Разрешение коллизий|хеш-таблиц с разрешением коллизий методом цепоче]]к. Ниже изложены теоремы, дающие некоторые оценки значений функции коллизии и производительности хеширования в случае организации хеш-таблицы с разрешением коллизий методом цепочек.

Пусть <math>H</math> — универсальное семейство хеш-функций, отображающих множество ключей <math>U</math> во множество <math>\left \{ 0,1,..,m-1 \right \}</math>. Пусть для организации хеш-таблицы с разрешением коллизий методом цепочек, то есть с помощью [[линейный список|линейного списка]], используется некоторая случайная функция <math>h \in H</math>. Если хеш-функция <math>h</math> отобразила в таблицу подмножество <math>S \subset U</math> ключей, то средняя длина связанных списков будет равна <math>1 + \delta _h (x,S)</math>. Следующая теорема дает оценку для функции коллизий в случае универсального семейства.

'''Теорема 2.'''<ref name=CW79/> Пусть <math>x</math> — произвольный элемент множества <math>U</math>, <math>S</math> — произвольное подмножество множества <math>U</math>. Пусть функция <math>h</math> случайно выбирается из универсального семейства хеш-функций <math>H</math>. Тогда имеет место следующая оценка:

<math>\delta _h (x,S) \leqslant \frac{\left | S \right |}{m} </math>

Этот результат можно использовать для вычисления ожидаемой производительности хеш-функции для последовательности из <math>R</math> запросов. Но сначала надо уточнить, что подразумевается под производительностью. Для этого нужно определить понятие стоимости — под стоимостью одного запроса к хеш-таблице по ключу <math>x</math> понимается число <math>1 + \delta _h (x,S) </math>, где <math>S</math> — множество ранее помещённых в таблицу ключей, а в самой хеш-таблице используется метод цепочек(то есть это число операций, необходимое для выполнения одного запроса). Стоимость <math>C(h,R)</math> хеш-функции <math>h</math> на последовательности запросов <math>R</math> есть сумма стоимостей отдельных запросов, идущих в последовательности, указанной в <math>R</math>. Стоимость, по сути, представляет количественную меру производительности.

'''Теорема 3.'''<ref name=CW79/> Пусть <math>x</math> Пусть <math>R</math> — это последовательность из <math>r</math> запросов, содержащая <math>k</math> вставок. Пусть <math>H</math> — универсальное семейство хеш-функций. Тогда для случайно выбранной из <math>H</math> хеш-функции <math>h</math> справедливо [[неравенство]]:

<math>M[C(h,R)] \leqslant r(1+\frac{k}{m})</math>.

Довольно часто<ref name=CW79/> известно приближенное число ключей, которое необходимо хранить в хеш-таблице. Тогда, можно подобрать размер <math>m</math> хеш-таблицы таким образом, чтобы отношение <math>\frac{k}{m}</math> было приблизительно равно 1. Значит, согласно теореме 3, ожидаемая стоимость исполнения последовательности запросов <math>R</math> будет [[Пропорциональность#Прямо пропорциональные величины|прямо пропорционально]] числу запросов <math>r</math>. Причём это справедливо для любой последовательности запросов <math>R</math>, а не для некоторой «средней» последовательности.

Таким образом, для любой случайно выбранной из универсального семейства хеш-функции её производительность оказывается достаточно хорошей. Остаётся вопрос о том, нужно ли менять хеш-функцию с течением времени, а если нужно, то как часто.

В случае с хеш-таблицами частая смена хеш-функций ведёт к большим накладным расходам. Например, если хеш-таблица имеет очень большие размеры, то при смене хеш-функции потребуется перемещение большого объёма данных. Существует несколько стратегий выбора хеш-функции. Наиболее простая стратегия состоит в том, чтобы в начале работы случайно выбрать хеш-функцию <math>h</math> и не менять её вплоть до конца работы. Однако в этом случае производительность хеш-функции оказывается значительно ниже ожидаемой<ref name=CW79/>. Другая стратегия состоит в том, чтобы время от времени подсчитывать число коллизий и менять хеш-функцию, если это число значительно превышает ожидаемое. Такой подход обеспечивает хорошую производительность, при условии, что хеш-функция выбирается случайно.

== Построение универсального семейства хеш-функций ==
Этот раздел посвящён построению универсальных семейств хеш-функций, из которых случайным образом выбирается хеш-функция.

Существует несколько семей универсальных хеш-функций, которые различаются тем, для каких данных предназначены эти функции: [[скаляр]]ы (хеширование чисел), [[вектор (математика)|векторы]] фиксированной длины (хеширование векторов), векторы переменной длины (хеширование строк).

=== Хеширование чисел ===
Выберем [[простое число]] <math>p</math> и рассмотрим [[Конечное поле|поле]] <math>\mathbb {Z}_p = \left \{ 0,1, ...,p-1 \right \}</math> и его мультипликативную группу <math>\mathbb {Z} _p^* = \left \{ 1,..,p-1 \right \}</math>.

'''Теорема.''' Множество [[функция (математика)|функций]] вида <math>H_{p,m} = \left \{ h_{a,b}: a \in \mathbb {Z} _p^*,b \in \mathbb {Z} _p \right \}</math>, где <math>h_{a,b}(x) = ((ax+b) \mod p) \mod m</math>, является универсальным (Это было показано в работе Картера и Вегмана<ref name=CW79 />).

Действительно, <math>h(x) = h(y)</math> только при

: <math>ax+b \equiv ay + b + i\cdot m \pmod{p}, \; \forall i \in  \left \{ 0,1, ..., p/m  \right \}.</math>

Если <math> x \neq y </math>, то [[вычитание|разность]] <math>x-y \neq 0</math> и может быть обращена [[деление с остатком|по модулю]] <math>p</math>. Отсюда можно получить

: <math>a \equiv i\cdot m \cdot (x-y)^{-1} \pmod{p}.</math>

Это [[уравнение]] имеет <math>p-1</math> решений, причем правая часть может принимать <math>\lfloor p/m \rfloor</math> значений. Таким образом, вероятность коллизий равна

: <math>\lfloor p/m \rfloor / (p-1)</math>,

которая стремится к <math>1/m</math> при увеличении <math>p</math>. <math>\Box</math>

=== Хеширование векторов ===
Пусть число <math>m</math> является простым. Пусть входные данные <math>x</math> представлены как последовательность <math>r+1</math> элементов, принадлежащих <math>\left \{ 0,1,..,p-1 \right \}</math>, то есть <math>x = \left \langle x_0, x_1, ..., x_r \right \rangle</math>.

Для всех последовательностей вида <math>a = \left \langle a_0, a_1, ..., a_r \right \rangle, a_i \in \mathbb {Z}_p, i = \overline{0,r}</math> рассмотрим функцию <math>h_a</math> вида

: <math>h_a(x) =\sum^{r}_{i=0} {a_ix_i} \mod m</math>

Положим, что <math>H = \bigcup_a h_a</math>

Видно, что <math>H</math> содержит <math>m^{r+1}</math>

'''Теорема.''' Множество <math>H</math> является универсальным семейством хеш-функций (Это также было показано Картером и Вегманом<ref name=CW79 />).

Действительно, если <math>x = \left \langle x_0, x_1, ..., x_r \right \rangle, y = \left \langle y_0, y_1, ..., y_r \right \rangle</math>, причём <math>x_0 \neq y_0</math>, то <math>h_a(x) = h_a(y)</math> тогда и только тогда, когда

: <math>a_0(x_0 - y_0) = - \sum^{r}_{i=1} {a_i(x_i - y_i)} \mod m</math>

Поскольку <math>x_0 - y_0 \not\equiv 0 \mod m </math>, то <math>\forall \left \langle a_1, ..., a_r \right \rangle, \exists ! a_0 </math> при котором выполняется указанное уравнение. Количество таких последовательностей равно <math>m^r</math>, а значит и количество функций из <math>H</math>, не различающих <math>x</math> и <math>y</math> также равно <math>m^r</math>. Но <math>m^r = \frac{\left | H \right |}{m}</math>, откуда и следует универсальность. <math>\Box</math>

Это семейство функций можно обобщить<ref name=thorup09>
{{cite conference
   | last = Thorup | first = Mikkel
   | title = String hashing for linear probing
   | work = Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA)
   | pages = Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), 655–664
   | year = 2009
   | archive-url = https://web.archive.org/web/20131012004656/http://www.siam.org/proceedings/soda/2009/SODA09_072_thorupm.pdf
   | archive-date = 2013-10-12
   | dead-url = no
   | doi = 10.1137/1.9781611973068.72
   | url = http://epubs.siam.org/doi/pdf/10.1137/1.9781611973068.72
}}, section 5.3
</ref>. Рассмотрим семейство функций <math>H_{p,m} = \left \{ h_{a,b}: a \in \mathbb {Z} _p^*,b \in \mathbb {Z} _p \right \}</math> и для вектора <math>x = \left \langle x_0, x_1, ..., x_r \right \rangle</math> рассмотрим хеш-функцию

: <math>h(\bar{x}) = \left( \sum_{i=0}^{k-1} h_i(x_i) \right)\,\bmod~m</math>, где <math>h_i \in H</math>

Тогда совокупность таких функций также будет являться универсальным семейством.

=== Хеширование строк ===
В этом случае входными данными для хеш-функции являются вектора, длина которых не является фиксированной величиной. Если можно ограничить длину всех векторов некоторым числом <math>L</math>, то можно применить подход, который был использован для векторов фиксированной длины. При этом, если длина вектора <math>l</math> меньше <math>L</math>, то можно дополнить вектор нулями так, чтобы его длина стала равна <math>L</math><ref name=thorup09/>

Теперь предположим, что нельзя заранее подобрать число <math>L</math>, ограничивающее длину всех векторов. Тогда можно предложить такой подход<ref name=DGMP>Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas(1992). «Polynomial Hash Functions Are Reliable (Extended Abstract)». Proc. 19th International Colloquium on Automata, Languages and Programming (ICALP). pp. 235—246
</ref> : пусть имеется входной вектор <math>\bar{x} = (x_0,\dots, x_\ell), \forall x_i \in \left \{ 0, 1, ..., u-1 \right \}</math>. Положим, что <math>p \ge \max \{ u, m \}</math> и будем рассматривать компоненты вектора как коэффициенты [[многочлен]]а: <math>x_l \cdot a^l + x_{l-1} \cdot a^{l-1} + ... x_{1} \cdot a^{1} + x_{0} \cdot a^{0},</math> где <math>a \in \left \{ 0, 1, ..., p-1 \right \}</math>.

Тогда для векторов переменной длины универсальная хеш-функция может быть определена следующим образом:

: <math>h_a(\bar{x}) = h_{a}^\mathrm{int} \left( \big(\sum_{i=0}^\ell x_i\cdot  a^i \big) \bmod ~p \right),</math>
где
: <math>h_{a}^\mathrm{int}:\left \{ 0,1,..,p-1 \right \} \rightarrow\left \{ 0,1,..,m-1 \right \}</math>
является универсальной хеш-функцией для числовых аргументов.

== Применение ==
Коды аутентификации сообщений [[UMAC]], {{нп4|Poly1305-AES|Poly1305-AES|en|Poly1305-AES}} и некоторые другие основаны на использовании универсального хеширования<ref>* David Wagner, ed. [https://books.google.com/books?id=11BsCQAAQBAJ «Advances in Cryptology — CRYPTO 2008»] {{Wayback|url=https://books.google.com/books?id=11BsCQAAQBAJ |date=20160529122039 }}. p. 145.</ref><ref>* Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. [https://books.google.com/books?id=nhPmBQAAQBAJ «The Hash Function BLAKE»] {{Wayback|url=https://books.google.com/books?id=nhPmBQAAQBAJ |date=20160506004255 }}. 2014. p. 10.</ref><ref>* M. Wegman and L. Carter, «New hash functions and their use in authentication and set equality», Journal of Computer and System Sciences, 22 (1981), pp. 265—279.</ref>. В этих кодах для каждого сообщения выбирается своя хеш-функция в зависимости от его одноразового уникального номера.

Универсальное семейство хеш-функций может быть использовано в том случае, когда требуется наличие большого числа «хороших» хеш-функций. [[Программист]]ы часто тратят много времени, проводя [[анализ (раздел математики)|анализ]] работы хеш-функций на различных данных и пытаясь выбрать подходящую{{sfn|Кнут|2007|страницы=508—513}}. Время поиска можно уменьшить, взяв универсальное семейство хеш-функций и выбрав случайно несколько функций из этого семейства<ref name=CW79/>.

Теоретическая значимость универсального хеширования состоит в том, что оно даёт «хорошую» границу для средней производительности алгоритмов, использующих хеширование. Например, универсальное хеширование было применено в алгоритмах, представленных в работах
<ref>M.0.RABIN,Probabilistic algorithms, in «Proceedings of Symposium on New Directions and Recent Results in Algorithms and Complexity» (J.F.Traub,Ed.), pp.21-39,Academic Press, New York, 1976.</ref>
<ref>.GOTO AND Y.KANADA,Hashing lemmas on time complexities with applications to formula manipulation, in "Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, " Yorktown Heights, N.Y.,pp.149—153.</ref>
<ref>.GUSTAVSON AND D.Y.Y. YUN, Arithmetic complexity of unordered or sparse polynomials, in "Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, " Yorktown Heights, N.Y.,pp.154—159.</ref>.

В теоретической криптографии было показано, что с помощью универсальных хеш-функций можно построить систему [[аутентификация|аутентификации]] с предельно достижимой секретностью<ref name=CW79/>. Примером универсальной хеш-функцией с доказанной [[криптографическая стойкость|криптографической стойкостью]] является хеш-функция [[SWIFFT]].

Более того, одним из наиболее важных приложений универсального хеширования является скоординированная выборка<ref name=Mikkel/>.

== См. также ==
* [[Имитовставка|MAC]]
* [[UMAC]]

== Примечания ==
{{примечания|2}}

== Литература ==
* {{книга
 |автор         = Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.
 |заглавие      = Алгоритмы: построение и анализ
 |оригинал      = Introduction to algorithms
 |ссылка        = https://books.google.ru/books?id=NLngYyWFl_YC
 |издание       = 2-е изд
 |место         = USA
 |издательство  = MIT Press
 |год           = 2001
 |страницы      = 234—237
 |страниц       = 1180
 |isbn          = 9780262032933
 |ref           = Cormen
}}
* {{книга|подзаголовок|заглавие=Искусство программирования, том 3. Сортировка и поиск|оригинал=The Art of Computer Programming, vol.3. Sorting and Searching|ссылка=|автор=[[Дональд Кнут]]|издание=2-е изд|год=2007|место={{М.}}|издательство=[[Вильямс (издательство)|Вильямс]]|страницы=508—513, 557|страниц=824|isbn=0-201-89685-0|ref=Кнут}}
* {{книга
 |автор         = Michael Luby
 |заглавие      = Pseudorandomness and Cryptographic Applications
 |место         = USA
 |издательство  = Princeton University Press
 |год           = 1996
 |страницы      = 153—163
 |страниц       = 248
 |isbn          = 0691025460
 |ref           = MLuby
}}

== Ссылки ==
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%BD%D0%B8%D0%B2%D0%B5%D1%80%D1%81%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D1%81%D0%B5%D0%BC%D0%B5%D0%B9%D1%81%D1%82%D0%B2%D0%BE_%D1%85%D0%B5%D1%88-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9 Универсальное хеширование]
* [http://geo.web.ru/db/msg.html?mid=1161287&uri=node66.html Универсальные семейства хеш-функций]
{{Внешние ссылки}}

[[Категория:Теория сложности вычислений]]
[[Категория:Криптографические хеш-функции]]
[[Категория:Хеширование]]
[[Категория:Алгоритмы поиска]]