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

Введение

Впервые понятие универсального хеширования было введено в статье и _en в 1979 году.

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

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

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

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

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

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

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

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

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

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

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

Определение. Семейство хеш-функций ${\displaystyle H}$ называется универсальным , если

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

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

Определение . Семейство хеш-функций ${\displaystyle H}$ называется универсальным , если

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \lfloor p/m\rfloor /(p-1)}$ ,

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle h({\bar {x}})=\left(\sum _{i=0}^{k-1}h_{i}(x_{i})\right)\,{\bmod {~}}m}$ , где ${\displaystyle h_{i}\in H}$

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

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

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

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

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

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

где

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

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

Применение

Коды аутентификации сообщений UMAC , _en и некоторые другие основаны на использовании универсального хеширования . В этих кодах для каждого сообщения выбирается своя хеш-функция в зависимости от его одноразового уникального номера.

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

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

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

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

См. также

• MAC
• UMAC

Примечания

Литература

• 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 .

Ссылки