Универсальное хеширование

Универса́льное хеши́рование (англ. Universal hashing) — это вид хеширования, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму^[1]^[2]. Такой подход обеспечивает равномерное хеширование: для очередного ключа вероятности помещения его в любую ячейку совпадают. Известно несколько семейств универсальных хеш-функций, которые имеют многочисленные применения в информатике, в частности в хеш-таблицах, вероятностных алгоритмах и криптографии.

Введение

Впервые понятие универсального хеширования было введено в статье^[1] Картера и Вегмана^[англ.] в 1979 году.

Изначально универсальное хеширование было разработано как независящий от входных данных алгоритм, работающий в среднем за линейное время и предназначенный для хранения и извлечения ключей из хеш-таблицы. Под независимостью от входных данных подразумевается следующее: для любой последовательности входных данных соответствующие хеш-значения элементов последовательности будут равномерно распределены по хеш-таблице. При выполнении этого условия среднее время работы алгоритма для любых данных оказывается сравнимым со временем работы хеш-функции, используемой для распределения заранее известных данных^[1].

Созданный алгоритм универсального хеширования представлял собой случайный выбор хеш-функции из некоторого набора хеш-функций(называемого универсальным семейством хеш-функций), обладающих определёнными свойствами. Авторами было показано, что в случае универсального хеширования число обращений к хеш-таблице (в среднем по всем функциям из семейства) для произвольных входных данных оказывается очень близким теоретическому минимуму для случая фиксированной хеш-функции со случайно распределёнными входными данными^[1].

Используя универсальное хеширование, авторы хотели^[1]:

Избавиться от необходимости предполагать вид входных данных.
Устранить зависимость времени работы хеширования от вида входных данных.
Добиться уменьшения числа коллизий.

В работе^[1] Вегмана и Картера универсальное хеширование было применено для построения хеш-таблицы, хотя позднее универсальное хеширование получило применение и в других областях(см. #Применение).

Определение универсального семейства хеш-функций

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

$\delta _{h}(x,y)={\begin{cases}1,&{\mbox{if }}x\neq y{\mbox{ and }}h(x)=h(y)\\0,&{\mbox{otherwise}}\end{cases}}$

Если $\delta _{h}(x,y)=1$ , то говорят, что имеет место коллизия. Можно определить функцию коллизии не для отдельных элементов $x,y,h$ , а для целого множества элементов — для этого надо произвести сложение функций коллизий по всем элементам из множества. Например, если $H$ — множество хеш-функций, $x\in U$ , $S\subset U$ , то для функции коллизии $\delta _{H}(x,S)$ получим:

$\delta _{H}(x,S)=\sum _{h\in H}\sum _{y\in S}\delta _{h}(x,y)$

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

Определение. Семейство хеш-функций $H$ называется универсальным^[1], если

\forall x,y\in U\longrightarrow \delta _{H}(x,S)={\frac {\left|H\right|}{m}}.

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

Определение. Семейство хеш-функций $H$ называется универсальным^[3]^[4], если

\forall x,y\in U,~x\neq y:~~\Pr _{h\in H}[h(x)=h(y)]\leq {\frac {1}{m}}

Свойства универсального семейства хеш-функций в случае его применения к хеш-таблицам

Следующая теорема определяет нижнюю границу функции $\delta _{h}(x,y)$ для произвольного семейства хеш-функций^[1].

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

$\delta _{H}(x,S)>{\frac {\left|H\right|}{m}}-{\frac {\left|H\right|}{\left|U\right|}}$

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

Для универсального семейства хеш-функций это означает, что верхняя и нижняя границы функции коллизии довольно близки^[1].

В статье^[1] универсальное хеширование применялось для организации хеш-таблиц с разрешением коллизий методом цепочек. Ниже изложены теоремы, дающие некоторые оценки значений функции коллизии и производительности хеширования в случае организации хеш-таблицы с разрешением коллизий методом цепочек.

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

Теорема 2.^[1] Пусть $x$ — произвольный элемент множества $U$ , $S$ — произвольное подмножество множества $U$ . Пусть функция $h$ случайно выбирается из универсального семейства хеш-функций $H$ . Тогда имеет место следующая оценка:

$\delta _{h}(x,S)\leqslant {\frac {\left|S\right|}{m}}$

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

Теорема 3.^[1] Пусть $x$ Пусть $R$ — это последовательность из $r$ запросов, содержащая $k$ вставок. Пусть $H$ — универсальное семейство хеш-функций. Тогда для случайно выбранной из $H$ хеш-функции $h$ справедливо неравенство:

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

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

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

В случае с хеш-таблицами частая смена хеш-функций ведёт к большим накладным расходам. Например, если хеш-таблица имеет очень большие размеры, то при смене хеш-функции потребуется перемещение большого объёма данных. Существует несколько стратегий выбора хеш-функции. Наиболее простая стратегия состоит в том, чтобы в начале работы случайно выбрать хеш-функцию $h$ и не менять её вплоть до конца работы. Однако в этом случае производительность хеш-функции оказывается значительно ниже ожидаемой^[1]. Другая стратегия состоит в том, чтобы время от времени подсчитывать число коллизий и менять хеш-функцию, если это число значительно превышает ожидаемое. Такой подход обеспечивает хорошую производительность, при условии, что хеш-функция выбирается случайно.

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

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

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

Хеширование чисел

Выберем простое число $p$ и рассмотрим поле $\mathbb {Z} _{p}=\left\{0,1,...,p-1\right\}$ и его мультипликативную группу $\mathbb {Z} _{p}^{*}=\left\{1,..,p-1\right\}$ .

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

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

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

Если $x\neq y$ , то разность $x-y\neq 0$ и может быть обращена по модулю $p$ . Отсюда можно получить

a\equiv i\cdot m\cdot (x-y)^{-1}{\pmod {p}}.

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

\lfloor p/m\rfloor /(p-1)

,

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

Хеширование векторов

Пусть число $m$ является простым. Пусть входные данные $x$ представлены как последовательность $r+1$ элементов, принадлежащих $\left\{0,1,..,p-1\right\}$ , то есть $x=\left\langle x_{0},x_{1},...,x_{r}\right\rangle$ .

Для всех последовательностей вида $a=\left\langle a_{0},a_{1},...,a_{r}\right\rangle ,a_{i}\in \mathbb {Z} _{p},i={\overline {0,r}}$ рассмотрим функцию $h_{a}$ вида

h_{a}(x)=\sum _{i=0}^{r}{a_{i}x_{i}}\mod m

Положим, что $H=\bigcup _{a}h_{a}$

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

Теорема. Множество $H$ является универсальным семейством хеш-функций (Это также было показано Картером и Вегманом^[1]).

Действительно, если $x=\left\langle x_{0},x_{1},...,x_{r}\right\rangle ,y=\left\langle y_{0},y_{1},...,y_{r}\right\rangle$ , причём $x_{0}\neq y_{0}$ , то $h_{a}(x)=h_{a}(y)$ тогда и только тогда, когда

a_{0}(x_{0}-y_{0})=-\sum _{i=1}^{r}{a_{i}(x_{i}-y_{i})}\mod m

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

Это семейство функций можно обобщить^[5]. Рассмотрим семейство функций $H_{p,m}=\left\{h_{a,b}:a\in \mathbb {Z} _{p}^{*},b\in \mathbb {Z} _{p}\right\}$ и для вектора $x=\left\langle x_{0},x_{1},...,x_{r}\right\rangle$ рассмотрим хеш-функцию

h({\bar {x}})=\left(\sum _{i=0}^{k-1}h_{i}(x_{i})\right)\,{\bmod {~}}m

, где

h_{i}\in H

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

Хеширование строк

В этом случае входными данными для хеш-функции являются вектора, длина которых не является фиксированной величиной. Если можно ограничить длину всех векторов некоторым числом $L$ , то можно применить подход, который был использован для векторов фиксированной длины. При этом, если длина вектора $l$ меньше $L$ , то можно дополнить вектор нулями так, чтобы его длина стала равна $L$ ^[5]

Теперь предположим, что нельзя заранее подобрать число $L$ , ограничивающее длину всех векторов. Тогда можно предложить такой подход^[6] : пусть имеется входной вектор ${\bar {x}}=(x_{0},\dots ,x_{\ell }),\forall x_{i}\in \left\{0,1,...,u-1\right\}$ . Положим, что $p\geq \max\{u,m\}$ и будем рассматривать компоненты вектора как коэффициенты многочлена: $x_{l}\cdot a^{l}+x_{l-1}\cdot a^{l-1}+...x_{1}\cdot a^{1}+x_{0}\cdot a^{0},$ где $a\in \left\{0,1,...,p-1\right\}$ .

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

h_{a}({\bar {x}})=h_{a}^{\mathrm {int} }\left({\big (}\sum _{i=0}^{\ell }x_{i}\cdot a^{i}{\big )}{\bmod {~}}p\right),

где

h_{a}^{\mathrm {int} }:\left\{0,1,..,p-1\right\}\rightarrow \left\{0,1,..,m-1\right\}

является универсальной хеш-функцией для числовых аргументов.

Применение

Коды аутентификации сообщений UMAC, Poly1305-AES^[англ.] и некоторые другие основаны на использовании универсального хеширования^[7]^[8]^[9]. В этих кодах для каждого сообщения выбирается своя хеш-функция в зависимости от его одноразового уникального номера.

Универсальное семейство хеш-функций может быть использовано в том случае, когда требуется наличие большого числа «хороших» хеш-функций. Программисты часто тратят много времени, проводя анализ работы хеш-функций на различных данных и пытаясь выбрать подходящую^[10]. Время поиска можно уменьшить, взяв универсальное семейство хеш-функций и выбрав случайно несколько функций из этого семейства^[1].

Теоретическая значимость универсального хеширования состоит в том, что оно даёт «хорошую» границу для средней производительности алгоритмов, использующих хеширование. Например, универсальное хеширование было применено в алгоритмах, представленных в работах ^[11] ^[12] ^[13].

В теоретической криптографии было показано, что с помощью универсальных хеш-функций можно построить систему аутентификации с предельно достижимой секретностью^[1]. Примером универсальной хеш-функцией с доказанной криптографической стойкостью является хеш-функция SWIFFT.

Более того, одним из наиболее важных приложений универсального хеширования является скоординированная выборка^[2].

См. также

MAC
UMAC

Примечания

↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ ¹² ¹³ ¹⁴ ¹⁵ ¹⁶ ¹⁷ ¹⁸ Carter, Larry; Wegman, Mark N.^[англ.]. Universal Classes of Hash Functions (англ.) // Journal of Computer and System Sciences^[англ.] : journal. — 1979. — Vol. 18, no. 2. — P. 143—154. — doi:10.1016/0022-0000(79)90044-8.
↑ ¹ ² Thorup, Mikkel, Speed Hashing for Integers and Strings (недоступная ссылка), Cornell University Library, July 15, 2014
↑ Motwani, Rajeev; Raghavan, Prabhakar. Randomized Algorithms (неопр.). — Cambridge University Press, 1995. — С. 216—217. — ISBN 0-521-47465-5.
↑ Cormen, 2001, pp. 234—235.
↑ ¹ ² Thorup, Mikkel (2009). String hashing for linear probing. Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), 655—664. doi:10.1137/1.9781611973068.72. Архивировано (PDF) 12 октября 2013., section 5.3
↑ 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
↑ * David Wagner, ed. «Advances in Cryptology — CRYPTO 2008» Архивная копия от 29 мая 2016 на Wayback Machine. p. 145.
↑ * Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. «The Hash Function BLAKE» Архивная копия от 6 мая 2016 на Wayback Machine. 2014. p. 10.
↑ * 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.
↑ Кнут, 2007, с. 508—513.
↑ 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.
↑ .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.
↑ .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.

Литература

Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Алгоритмы: построение и анализ = Introduction to algorithms. — 2-е изд. — USA: MIT Press, 2001. — С. 234—237. — 1180 с. — ISBN 9780262032933.
Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: Вильямс, 2007. — С. 508—513, 557. — 824 с. — ISBN 0-201-89685-0.
Michael Luby. Pseudorandomness and Cryptographic Applications. — USA: Princeton University Press, 1996. — С. 153—163. — 248 с. — ISBN 0691025460.

Ссылки

[CW79-1] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ ¹² ¹³ ¹⁴ ¹⁵ ¹⁶ ¹⁷ ¹⁸ Carter, Larry; Wegman, Mark N.^[англ.]. Universal Classes of Hash Functions (англ.) // Journal of Computer and System Sciences^[англ.] : journal. — 1979. — Vol. 18, no. 2. — P. 143—154. — doi:10.1016/0022-0000(79)90044-8.

[Mikkel-2] ¹ ² Thorup, Mikkel, Speed Hashing for Integers and Strings (недоступная ссылка), Cornell University Library, July 15, 2014

[3] Motwani, Rajeev; Raghavan, Prabhakar. Randomized Algorithms (неопр.). — Cambridge University Press, 1995. — С. 216—217. — ISBN 0-521-47465-5.

[_2713df985c3a53e5-4] Cormen, 2001, pp. 234—235.

[thorup09-5] ¹ ² Thorup, Mikkel (2009). String hashing for linear probing. Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), 655—664. doi:10.1137/1.9781611973068.72. Архивировано (PDF) 12 октября 2013., section 5.3

[DGMP-6] 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

[7] * David Wagner, ed. «Advances in Cryptology — CRYPTO 2008» Архивная копия от 29 мая 2016 на Wayback Machine. p. 145.

[8] * Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. «The Hash Function BLAKE» Архивная копия от 6 мая 2016 на Wayback Machine. 2014. p. 10.

[9] * 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.

[_6af8d9ad022bab44-10] Кнут, 2007, с. 508—513.

[11] 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.

[12] .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.

[13] .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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]