Универсальное хеширование
Универса́льное хеши́рование (Шаблон:Lang-en) — это вид хеширования, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму<ref name=CW79> Шаблон:Статья</ref><ref name=Mikkel>Thorup, Mikkel, Speed Hashing for Integers and StringsШаблон:Недоступная ссылка, Cornell University Library, July 15, 2014</ref>. Такой подход обеспечивает равномерное хеширование: для очередного ключа вероятности помещения его в любую ячейку совпадают. Известно несколько семейств универсальных хеш-функций, которые имеют многочисленные применения в информатике, в частности в хеш-таблицах, вероятностных алгоритмах и криптографии.
Введение
Впервые понятие универсального хеширования было введено в статье<ref name=CW79/> Картера и Шаблон:Нп4 в 1979 году.
Изначально универсальное хеширование было разработано как независящий от входных данных алгоритм, работающий в среднем за линейное время и предназначенный для хранения и извлечения ключей из хеш-таблицы. Под независимостью от входных данных подразумевается следующее: для любой последовательности входных данных соответствующие хеш-значения элементов последовательности будут равномерно распределены по хеш-таблице. При выполнении этого условия среднее время работы алгоритма для любых данных оказывается сравнимым со временем работы хеш-функции, используемой для распределения заранее известных данных<ref name=CW79/>.
Созданный алгоритм универсального хеширования представлял собой случайный выбор хеш-функции из некоторого набора хеш-функций(называемого универсальным семейством хеш-функций), обладающих определёнными свойствами. Авторами было показано, что в случае универсального хеширования число обращений к хеш-таблице (в среднем по всем функциям из семейства) для произвольных входных данных оказывается очень близким теоретическому минимуму для случая фиксированной хеш-функции со случайно распределёнными входными данными<ref name=CW79/>.
Используя универсальное хеширование, авторы хотели<ref name=CW79/>:
- Избавиться от необходимости предполагать вид входных данных.
- Устранить зависимость времени работы хеширования от вида входных данных.
- Добиться уменьшения числа коллизий.
В работе<ref name=CW79/> Вегмана и Картера универсальное хеширование было применено для построения хеш-таблицы, хотя позднее универсальное хеширование получило применение и в других областях(см. #Применение).
Определение универсального семейства хеш-функций
Пусть [math]\displaystyle{ U }[/math] — множество ключей, [math]\displaystyle{ H }[/math] — конечное множество хеш-функций, отображающих [math]\displaystyle{ U }[/math] во множество [math]\displaystyle{ \left \{ 0,1,..,m-1 \right \} }[/math]. Возьмем произвольные [math]\displaystyle{ h \in H }[/math] и [math]\displaystyle{ x,y \in U }[/math] и определим функцию коллизий [math]\displaystyle{ \delta _h (x,y) }[/math]:
[math]\displaystyle{ \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]\displaystyle{ \delta _h (x,y) = 1 }[/math], то говорят, что имеет место коллизия. Можно определить функцию коллизии не для отдельных элементов [math]\displaystyle{ x,y,h }[/math], а для целого множества элементов — для этого надо произвести сложение функций коллизий по всем элементам из множества. Например, если [math]\displaystyle{ H }[/math] — множество хеш-функций, [math]\displaystyle{ x \in U }[/math], [math]\displaystyle{ S \subset U }[/math], то для функции коллизии [math]\displaystyle{ \delta _H (x,S) }[/math] получим:
[math]\displaystyle{ \delta _H (x,S) = \sum_{h \in H} \sum_{y \in S} \delta _h (x,y) }[/math]
Причём порядок суммирования не имеет значения.
Определение. Семейство хеш-функций [math]\displaystyle{ H }[/math] называется универсальным<ref name=CW79/>, если
- [math]\displaystyle{ \forall x, y \in U \longrightarrow \delta _H (x,S) = \frac{\left | H \right |}{m}. }[/math]
Можно дать другое определение, эквивалентное данному.
Определение. Семейство хеш-функций [math]\displaystyle{ H }[/math] называется универсальным<ref> Шаблон:Книга </ref>Шаблон:Sfn, если
- [math]\displaystyle{ \forall x, y \in U, ~ x\ne y: ~~ \Pr_{h\in H} [h(x) = h(y)] \le \frac{1}{m} }[/math]
Свойства универсального семейства хеш-функций в случае его применения к хеш-таблицам
Следующая теорема определяет нижнюю границу функции [math]\displaystyle{ \delta _h (x,y) }[/math] для произвольного семейства хеш-функций<ref name=CW79/>.
Теорема 1.Для любого семейства(не обязательно универсального) хеш-функций [math]\displaystyle{ H }[/math] существуют [math]\displaystyle{ x,y \in U }[/math] такие, что
[math]\displaystyle{ \delta _H (x,S) \gt \frac{\left | H \right |}{m} - \frac{\left | H \right |}{\left | U \right |} }[/math]
Из теоремы 1 следует, что нижняя граница функции коллизии близка к [math]\displaystyle{ \frac{\left | H \right |}{m} }[/math] в случае, когда [math]\displaystyle{ \left | U \right | }[/math] много больше [math]\displaystyle{ m }[/math]. В действительности, часто так и бывает. Например, пусть компилятор ставит в соответствие тысяче переменных последовательности из семи английских букв. Тогда [math]\displaystyle{ m = 1000 }[/math], а [math]\displaystyle{ \left | U \right | = 26^7 }[/math]
Для универсального семейства хеш-функций это означает, что верхняя и нижняя границы функции коллизии довольно близки<ref name=CW79/>.
В статье<ref name=CW79/> универсальное хеширование применялось для организации хеш-таблиц с разрешением коллизий методом цепочек. Ниже изложены теоремы, дающие некоторые оценки значений функции коллизии и производительности хеширования в случае организации хеш-таблицы с разрешением коллизий методом цепочек.
Пусть [math]\displaystyle{ H }[/math] — универсальное семейство хеш-функций, отображающих множество ключей [math]\displaystyle{ U }[/math] во множество [math]\displaystyle{ \left \{ 0,1,..,m-1 \right \} }[/math]. Пусть для организации хеш-таблицы с разрешением коллизий методом цепочек, то есть с помощью линейного списка, используется некоторая случайная функция [math]\displaystyle{ h \in H }[/math]. Если хеш-функция [math]\displaystyle{ h }[/math] отобразила в таблицу подмножество [math]\displaystyle{ S \subset U }[/math] ключей, то средняя длина связанных списков будет равна [math]\displaystyle{ 1 + \delta _h (x,S) }[/math]. Следующая теорема дает оценку для функции коллизий в случае универсального семейства.
Теорема 2.<ref name=CW79/> Пусть [math]\displaystyle{ x }[/math] — произвольный элемент множества [math]\displaystyle{ U }[/math], [math]\displaystyle{ S }[/math] — произвольное подмножество множества [math]\displaystyle{ U }[/math]. Пусть функция [math]\displaystyle{ h }[/math] случайно выбирается из универсального семейства хеш-функций [math]\displaystyle{ H }[/math]. Тогда имеет место следующая оценка:
[math]\displaystyle{ \delta _h (x,S) \leqslant \frac{\left | S \right |}{m} }[/math]
Этот результат можно использовать для вычисления ожидаемой производительности хеш-функции для последовательности из [math]\displaystyle{ R }[/math] запросов. Но сначала надо уточнить, что подразумевается под производительностью. Для этого нужно определить понятие стоимости — под стоимостью одного запроса к хеш-таблице по ключу [math]\displaystyle{ x }[/math] понимается число [math]\displaystyle{ 1 + \delta _h (x,S) }[/math], где [math]\displaystyle{ S }[/math] — множество ранее помещённых в таблицу ключей, а в самой хеш-таблице используется метод цепочек(то есть это число операций, необходимое для выполнения одного запроса). Стоимость [math]\displaystyle{ C(h,R) }[/math] хеш-функции [math]\displaystyle{ h }[/math] на последовательности запросов [math]\displaystyle{ R }[/math] есть сумма стоимостей отдельных запросов, идущих в последовательности, указанной в [math]\displaystyle{ R }[/math]. Стоимость, по сути, представляет количественную меру производительности.
Теорема 3.<ref name=CW79/> Пусть [math]\displaystyle{ x }[/math] Пусть [math]\displaystyle{ R }[/math] — это последовательность из [math]\displaystyle{ r }[/math] запросов, содержащая [math]\displaystyle{ k }[/math] вставок. Пусть [math]\displaystyle{ H }[/math] — универсальное семейство хеш-функций. Тогда для случайно выбранной из [math]\displaystyle{ H }[/math] хеш-функции [math]\displaystyle{ h }[/math] справедливо неравенство:
[math]\displaystyle{ M[C(h,R)] \leqslant r(1+\frac{k}{m}) }[/math].
Довольно часто<ref name=CW79/> известно приближенное число ключей, которое необходимо хранить в хеш-таблице. Тогда, можно подобрать размер [math]\displaystyle{ m }[/math] хеш-таблицы таким образом, чтобы отношение [math]\displaystyle{ \frac{k}{m} }[/math] было приблизительно равно 1. Значит, согласно теореме 3, ожидаемая стоимость исполнения последовательности запросов [math]\displaystyle{ R }[/math] будет прямо пропорционально числу запросов [math]\displaystyle{ r }[/math]. Причём это справедливо для любой последовательности запросов [math]\displaystyle{ R }[/math], а не для некоторой «средней» последовательности.
Таким образом, для любой случайно выбранной из универсального семейства хеш-функции её производительность оказывается достаточно хорошей. Остаётся вопрос о том, нужно ли менять хеш-функцию с течением времени, а если нужно, то как часто.
В случае с хеш-таблицами частая смена хеш-функций ведёт к большим накладным расходам. Например, если хеш-таблица имеет очень большие размеры, то при смене хеш-функции потребуется перемещение большого объёма данных. Существует несколько стратегий выбора хеш-функции. Наиболее простая стратегия состоит в том, чтобы в начале работы случайно выбрать хеш-функцию [math]\displaystyle{ h }[/math] и не менять её вплоть до конца работы. Однако в этом случае производительность хеш-функции оказывается значительно ниже ожидаемой<ref name=CW79/>. Другая стратегия состоит в том, чтобы время от времени подсчитывать число коллизий и менять хеш-функцию, если это число значительно превышает ожидаемое. Такой подход обеспечивает хорошую производительность, при условии, что хеш-функция выбирается случайно.
Построение универсального семейства хеш-функций
Этот раздел посвящён построению универсальных семейств хеш-функций, из которых случайным образом выбирается хеш-функция.
Существует несколько семей универсальных хеш-функций, которые различаются тем, для каких данных предназначены эти функции: скаляры (хеширование чисел), векторы фиксированной длины (хеширование векторов), векторы переменной длины (хеширование строк).
Хеширование чисел
Выберем простое число [math]\displaystyle{ p }[/math] и рассмотрим поле [math]\displaystyle{ \mathbb {Z}_p = \left \{ 0,1, ...,p-1 \right \} }[/math] и его мультипликативную группу [math]\displaystyle{ \mathbb {Z} _p^* = \left \{ 1,..,p-1 \right \} }[/math].
Теорема. Множество функций вида [math]\displaystyle{ H_{p,m} = \left \{ h_{a,b}: a \in \mathbb {Z} _p^*,b \in \mathbb {Z} _p \right \} }[/math], где [math]\displaystyle{ h_{a,b}(x) = ((ax+b) \mod p) \mod m }[/math], является универсальным (Это было показано в работе Картера и Вегмана<ref name=CW79 />).
Действительно, [math]\displaystyle{ h(x) = h(y) }[/math] только при
- [math]\displaystyle{ ax+b \equiv ay + b + i\cdot m \pmod{p}, \; \forall i \in \left \{ 0,1, ..., p/m \right \}. }[/math]
Если [math]\displaystyle{ x \neq y }[/math], то разность [math]\displaystyle{ x-y \neq 0 }[/math] и может быть обращена по модулю [math]\displaystyle{ p }[/math]. Отсюда можно получить
- [math]\displaystyle{ a \equiv i\cdot m \cdot (x-y)^{-1} \pmod{p}. }[/math]
Это уравнение имеет [math]\displaystyle{ p-1 }[/math] решений, причем правая часть может принимать [math]\displaystyle{ \lfloor p/m \rfloor }[/math] значений. Таким образом, вероятность коллизий равна
- [math]\displaystyle{ \lfloor p/m \rfloor / (p-1) }[/math],
которая стремится к [math]\displaystyle{ 1/m }[/math] при увеличении [math]\displaystyle{ p }[/math]. [math]\displaystyle{ \Box }[/math]
Хеширование векторов
Пусть число [math]\displaystyle{ m }[/math] является простым. Пусть входные данные [math]\displaystyle{ x }[/math] представлены как последовательность [math]\displaystyle{ r+1 }[/math] элементов, принадлежащих [math]\displaystyle{ \left \{ 0,1,..,p-1 \right \} }[/math], то есть [math]\displaystyle{ x = \left \langle x_0, x_1, ..., x_r \right \rangle }[/math].
Для всех последовательностей вида [math]\displaystyle{ a = \left \langle a_0, a_1, ..., a_r \right \rangle, a_i \in \mathbb {Z}_p, i = \overline{0,r} }[/math] рассмотрим функцию [math]\displaystyle{ h_a }[/math] вида
- [math]\displaystyle{ h_a(x) =\sum^{r}_{i=0} {a_ix_i} \mod m }[/math]
Положим, что [math]\displaystyle{ H = \bigcup_a h_a }[/math]
Видно, что [math]\displaystyle{ H }[/math] содержит [math]\displaystyle{ m^{r+1} }[/math]
Теорема. Множество [math]\displaystyle{ H }[/math] является универсальным семейством хеш-функций (Это также было показано Картером и Вегманом<ref name=CW79 />).
Действительно, если [math]\displaystyle{ x = \left \langle x_0, x_1, ..., x_r \right \rangle, y = \left \langle y_0, y_1, ..., y_r \right \rangle }[/math], причём [math]\displaystyle{ x_0 \neq y_0 }[/math], то [math]\displaystyle{ h_a(x) = h_a(y) }[/math] тогда и только тогда, когда
- [math]\displaystyle{ a_0(x_0 - y_0) = - \sum^{r}_{i=1} {a_i(x_i - y_i)} \mod m }[/math]
Поскольку [math]\displaystyle{ x_0 - y_0 \not\equiv 0 \mod m }[/math], то [math]\displaystyle{ \forall \left \langle a_1, ..., a_r \right \rangle, \exists ! a_0 }[/math] при котором выполняется указанное уравнение. Количество таких последовательностей равно [math]\displaystyle{ m^r }[/math], а значит и количество функций из [math]\displaystyle{ H }[/math], не различающих [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] также равно [math]\displaystyle{ m^r }[/math]. Но [math]\displaystyle{ m^r = \frac{\left | H \right |}{m} }[/math], откуда и следует универсальность. [math]\displaystyle{ \Box }[/math]
Это семейство функций можно обобщить<ref name=thorup09> Шаблон:Cite conference, section 5.3 </ref>. Рассмотрим семейство функций [math]\displaystyle{ H_{p,m} = \left \{ h_{a,b}: a \in \mathbb {Z} _p^*,b \in \mathbb {Z} _p \right \} }[/math] и для вектора [math]\displaystyle{ x = \left \langle x_0, x_1, ..., x_r \right \rangle }[/math] рассмотрим хеш-функцию
- [math]\displaystyle{ h(\bar{x}) = \left( \sum_{i=0}^{k-1} h_i(x_i) \right)\,\bmod~m }[/math], где [math]\displaystyle{ h_i \in H }[/math]
Тогда совокупность таких функций также будет являться универсальным семейством.
Хеширование строк
В этом случае входными данными для хеш-функции являются вектора, длина которых не является фиксированной величиной. Если можно ограничить длину всех векторов некоторым числом [math]\displaystyle{ L }[/math], то можно применить подход, который был использован для векторов фиксированной длины. При этом, если длина вектора [math]\displaystyle{ l }[/math] меньше [math]\displaystyle{ L }[/math], то можно дополнить вектор нулями так, чтобы его длина стала равна [math]\displaystyle{ L }[/math]<ref name=thorup09/>
Теперь предположим, что нельзя заранее подобрать число [math]\displaystyle{ 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]\displaystyle{ \bar{x} = (x_0,\dots, x_\ell), \forall x_i \in \left \{ 0, 1, ..., u-1 \right \} }[/math]. Положим, что [math]\displaystyle{ p \ge \max \{ u, m \} }[/math] и будем рассматривать компоненты вектора как коэффициенты многочлена: [math]\displaystyle{ x_l \cdot a^l + x_{l-1} \cdot a^{l-1} + ... x_{1} \cdot a^{1} + x_{0} \cdot a^{0}, }[/math] где [math]\displaystyle{ a \in \left \{ 0, 1, ..., p-1 \right \} }[/math].
Тогда для векторов переменной длины универсальная хеш-функция может быть определена следующим образом:
- [math]\displaystyle{ 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]\displaystyle{ h_{a}^\mathrm{int}:\left \{ 0,1,..,p-1 \right \} \rightarrow\left \{ 0,1,..,m-1 \right \} }[/math]
является универсальной хеш-функцией для числовых аргументов.
Применение
Коды аутентификации сообщений UMAC, Шаблон:Нп4 и некоторые другие основаны на использовании универсального хеширования<ref>* David Wagner, ed. «Advances in Cryptology — CRYPTO 2008» Шаблон:Wayback. p. 145.</ref><ref>* Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. «The Hash Function BLAKE» Шаблон:Wayback. 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. Время поиска можно уменьшить, взяв универсальное семейство хеш-функций и выбрав случайно несколько функций из этого семейства<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/>.
