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

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

Введение

См. также: Хеширование

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

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

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

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

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

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

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

Пусть ${\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}$ называется универсальным^[1], если

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

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

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

${\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].

Теорема 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}}$

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

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

Пусть ${\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.^[1] Пусть ${\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.^[1] Пусть ${\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}})}$.

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

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

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

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

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

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

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

Выберем простое число ${\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}$, является универсальным (Это было показано в работе Картера и Вегмана^[1]).

Действительно, ${\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}$ является универсальным семейством хеш-функций (Это также было показано Картером и Вегманом^[1]).

Действительно, если ${\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 }$

Это семейство функций можно обобщить^[5]. Рассмотрим семейство функций ${\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}$^[5]

Теперь предположим, что нельзя заранее подобрать число ${\displaystyle L}$, ограничивающее длину всех векторов. Тогда можно предложить такой подход^[6] : пусть имеется входной вектор ${\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, Poly1305-AES^[англ.] и некоторые другие основаны на использовании универсального хеширования^[7][8][9]. В этих кодах для каждого сообщения выбирается своя хеш-функция в зависимости от его одноразового уникального номера.

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

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

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

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

См. также

• MAC
• UMAC