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

В математике и вычислительной технике универсальное хеширование (в рандомизированном алгоритме или структуре данных) означает случайный выбор хеш-функции из семейства хеш-функций с определенным математическим свойством (см. определение ниже). Это гарантирует низкое количество коллизий в ожидании , даже если данные выбраны злоумышленником. Известно множество универсальных семейств (для хеширования целых чисел, векторов, строк), и их оценка часто бывает очень эффективной. Универсальное хеширование имеет множество применений в информатике, например, в реализации хеш-таблиц , рандомизированных алгоритмов и криптографии .

Введение

См. также: Хэш-функция

Предположим, мы хотим сопоставить ключи из какой-то вселенной $U$ в $m$ контейнеры (с маркировкой $[m]=\{0,\dots ,m-1\}$). Алгоритму придется обрабатывать некоторый набор данных. $S\subseteq U$ из $|S|=n$ ключи, которые заранее не известны. Обычно целью хеширования является получение небольшого количества коллизий (ключи из $S$ они попадают в тот же контейнер). Детерминированная хеш-функция не может дать никаких гарантий в состязательных условиях, если $|U|>m\cdot n$, поскольку противник может выбрать $S$ быть точно прообразом мусорного ведра. Это означает, что все ключи данных попадают в один и тот же контейнер, что делает хеширование бесполезным. Более того, детерминированная хэш-функция не допускает повторного хеширования : иногда входные данные оказываются неподходящими для хеш-функции (например, слишком много коллизий), поэтому хотелось бы изменить хеш-функцию.

Решением этих проблем является случайный выбор функции из семейства хеш-функций. Семейство функций $H=\{h:U\to [m]\}$ называется универсальной семьей , если $\forall x,y\in U,~x\neq y:~~|\{h\in H:h(x)=h(y)\}|\leq {\frac {|H|}{m}}$.

Другими словами, любые два разных ключа Вселенной сталкиваются с вероятностью не более $1/m$ когда хеш-функция $h$ вытягивается равномерно случайным образом из $H$. Это именно та вероятность коллизии, которую мы могли бы ожидать, если бы хэш-функция присваивала каждому ключу действительно случайные хэш-коды.

Иногда определение смягчается постоянным коэффициентом, требуя только вероятности столкновения. $O(1/m)$ скорее, чем $\leq 1/m$. Эту концепцию ввели Картер и Вегман. в 1977 году и нашел многочисленные применения в информатике (см., например , ) .

Если у нас есть верхняя граница $\epsilon <1$ о вероятности столкновения мы говорим, что имеем $\epsilon$-почти универсальность. Так, например, универсальная семья имеет $1/m$-почти универсальность.

Многие, но не все, универсальные семейства обладают следующим более сильным свойством равномерной разности :

$\forall x,y\in U,~x\neq y$, когда $h$ выбирается случайным образом из семьи $H$, разница $h(x)-h(y)~{\bmod {~}}m$ равномерно распределен в $[m]$.

Обратите внимание, что определение универсальности касается только того, является ли $h(x)-h(y)=0$, который подсчитывает столкновения. Свойство равномерной разности более сильное.

(Аналогично, универсальное семейство может быть универсальным XOR, если $\forall x,y\in U,~x\neq y$, значение $h(x)\oplus h(y)~{\bmod {~}}m$ равномерно распределен в $[m]$ где $\oplus$ — это побитовая исключающая операция или. Это возможно только в том случае, если $m$ это степень двойки.)

Еще более сильным условием является попарная независимость : мы имеем это свойство, когда $\forall x,y\in U,~x\neq y$ у нас есть вероятность, что $x,y$ будет хэшироваться с любой парой хеш-значений $z_{1},z_{2}$ как будто они были совершенно случайными: $P(h(x)=z_{1}\land h(y)=z_{2})=1/m^{2}$. Парную независимость иногда называют сильной универсальностью.

Еще одно свойство — однородность. Мы говорим, что семейство является однородным, если все значения хеш-функции одинаково вероятны: $P(h(x)=z)=1/m$ для любого хэш-значения $z$. Универсальность не означает единообразия. Однако сильная универсальность предполагает единообразие.

Имея семейство со свойством равномерного расстояния, можно создать попарно независимое или сильно универсальное хеш-семейство, добавив равномерно распределенную случайную константу со значениями в $[m]$ к хеш-функциям. (Аналогично, если $m$ является степенью двойки, мы можем добиться попарной независимости от универсального семейства хэшей XOR, выполнив исключающую случайную константу или с равномерно распределенной случайной константой.) Поскольку сдвиг на константу иногда не имеет значения в приложениях (например, хэш-таблицах), тщательное разграничение между свойством равномерного расстояния и попарно независимым иногда не проводится.

Для некоторых приложений (например, хеш-таблиц) важно, чтобы младшие биты хеш-значений также были универсальными. Когда семья строго универсальна, это гарантировано: если $H$ представляет собой сильно универсальное семейство с $m=2^{L}$, то семейство, составленное из функций $h{\bmod {2^{L'}}}$ для всех $h\in H$ также является сильно универсальным для $L'\leq L$. К сожалению, то же самое нельзя сказать о (просто) универсальных семьях. Например, семья, состоящая из тождественной функции $h(x)=x$ явно универсален, но семейство, состоящее из функции $h(x)=x{\bmod {2^{L'}}}$ не может быть универсальным.

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

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

Математические гарантии

Для любого фиксированного набора $S$ из $n$ ключей, использование универсального семейства гарантирует следующие свойства.

1. Для любого фиксированного $x$ в $S$, ожидаемое количество ключей в корзине $h(x)$ является $n/m$. При реализации хеш-таблиц путем объединения это число пропорционально ожидаемому времени выполнения операции с использованием ключа. $x$ (например, запрос, вставка или удаление).
2. Ожидаемое количество пар ключей $x,y$ в $S$ с $x\neq y$ которые сталкиваются ( $h(x)=h(y)$) ограничено сверху $n(n-1)/2m$, что в порядке $O(n^{2}/m)$. Когда количество бункеров, $m$ выбирается линейным по $n$ (т.е. определяется функцией из $\Omega (n)$), ожидаемое количество столкновений равно $O(n)$. При хешировании в $n^{2}$ бункеров, коллизий вообще нет с вероятностью не менее половины.
3. Ожидаемое количество ключей в корзинах не менее $t$ ключи в них ограничены сверху $2n/(t-2(n/m)+1)$. Таким образом, если вместимость каждого контейнера ограничена трехкратным средним размером ( $t=3n/m$), общее количество ключей в переполненных бункерах не более $O(m)$. Это справедливо только для семейства хэшей, вероятность коллизии которого ограничена сверху величиной $1/m$. Если используется более слабое определение, ограничивая его формулой $O(1/m)$, этот результат уже не соответствует действительности.

Поскольку приведенные выше гарантии справедливы для любого фиксированного набора $S$, они сохраняются, если набор данных выбран противником. Однако злоумышленник должен сделать этот выбор до (или независимо от) случайного выбора алгоритмом хэш-функции. Если злоумышленник может наблюдать за случайным выбором алгоритма, случайность бесполезна, и ситуация аналогична детерминированному хешированию.

Вторая и третья гарантии обычно используются вместе с перефразированием . Например, можно подготовить рандомизированный алгоритм для обработки некоторых $O(n)$ количество столкновений. Если он наблюдает слишком много столкновений, он выбирает другое случайное $h$ из семьи и повторяется. Универсальность гарантирует, что количество повторений является геометрической случайной величиной .

Конструкции

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

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

В этом разделе рассматривается случай хеширования целых чисел, которые помещаются в машинные слова; таким образом, такие операции, как умножение, сложение, деление и т. д., являются дешевыми инструкциями машинного уровня. Пусть вселенная, которую нужно хэшировать, будет $\{0,\dots ,|U|-1\}$.

Оригинальное предложение Картера и Вегмана было выбрать простое число $p\geq |U|$ и определить

$h_{a,b}(x)=((ax+b)~{\bmod {~}}p)~{\bmod {~}}m$

где $a,b$ являются случайно выбранными целыми числами по модулю $p$ с $a\neq 0$. (Это одна итерация линейного конгруэнтного генератора .)

Чтобы увидеть это $H=\{h_{a,b}\}$ является универсальным семейством, заметим, что $h(x)=h(y)$ имеет место только тогда, когда

$ax+b\equiv ay+b+i\cdot m{\pmod {p}}$

для некоторого целого числа $i$ между $0$ и $(p-1)/m$. С $p\geq |U|$, если $x\neq y$ их разница $x-y$ ненулевое значение и имеет обратный по модулю $p$. Решение для $a$ урожайность

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

Есть $p-1$ возможные варианты для $a$ (с $a=0$ исключено) и, варьируя $i$ в допустимом диапазоне, $\lfloor (p-1)/m\rfloor$ возможные ненулевые значения для правой части. Таким образом, вероятность столкновения равна

$\lfloor (p-1)/m\rfloor /(p-1)\leq ((p-1)/m)/(p-1)=1/m$.

Еще один способ увидеть $H$ является универсальной семьей через понятие статистического расстояния . Напишите разницу $h(x)-h(y)$ как

$h(x)-h(y)\equiv (a(x-y)~{\bmod {~}}p){\pmod {m}}$.

С $x-y$ ненулевое значение и $a$ равномерно распределен в $\{1,\dots ,p-1\}$, отсюда следует, что $a(x-y)$ модуль $p$ также равномерно распределены в $\{1,\dots ,p-1\}$. Распределение $(h(x)-h(y))~{\bmod {~}}m$ таким образом, почти однороден, вплоть до разницы в вероятности $\pm 1/p$ между образцами. В результате статистическое расстояние до однородного семейства равно $O(m/p)$, который становится пренебрежимо малым, когда $p\gg m$.

Семейство более простых хеш-функций

$h_{a}(x)=(ax~{\bmod {~}}p)~{\bmod {~}}m$

является лишь приблизительно универсальным: $\Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m$ для всех $x\neq y$. Более того, этот анализ почти точен; Картер и Вегман покажи это $\Pr\{h_{a}(1)=h_{a}(m+1)\}\geq 2/(m+1)$ в любое время $(p-1)~{\bmod {~}}m=1$.

Как избежать модульной арифметики

Современным способом хеширования целых чисел является схема с множественным сдвигом, описанная Дитцфельбингером и др. в 1997 году. Избегая модульной арифметики, этот метод гораздо проще реализовать, а также на практике он работает значительно быстрее (обычно как минимум в четыре раза). ). Схема предполагает, что количество ячеек равно степени двойки, $m=2^{M}$. Позволять $w$ — количество битов в машинном слове. Затем хеш-функции параметризуются по нечетным положительным целым числам. $a<2^{w}$ (что подходит под одно слово $w$ биты). Чтобы оценить $h_{a}(x)$, умножить $x$ к $a$ модуль $2^{w}$ и затем поддерживать высокий порядок $M$ бит в качестве хеш-кода. В математической записи это

$h_{a}(x)=(a\cdot x\,\,{\bmod {\,}}2^{w})\,\,\mathrm {div} \,\,2^{w-M}.$

Эта схема не удовлетворяет свойству равномерной разности и является лишь $2/m$-почти универсальный ; для любого $x\neq y$, $\Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m$.

Чтобы понять поведение хеш-функции, обратите внимание, что если $ax{\bmod {2}}^{w}$ и $ay{\bmod {2}}^{w}$ имеют одинаковые старшие биты «M», тогда $a(x-y){\bmod {2}}^{w}$ имеет либо все 1, либо все 0 в качестве битов M высшего порядка (в зависимости от того, $ax{\bmod {2}}^{w}$ или $ay{\bmod {2}}^{w}$ больше). Предположим, что младший бит набора $x-y$ появляется на позиции $w-c$. С $a$ является случайным нечетным целым числом, а нечетные целые числа имеют обратные значения в кольце $Z_{2^{w}}$, отсюда следует, что $a(x-y){\bmod {2}}^{w}$ будут равномерно распределены между $w$-битовые целые числа с младшим установленным битом в позиции $w-c$. Таким образом, вероятность того, что все эти биты равны 0 или 1, не превышает $2/2^{M}=2/m$. С другой стороны, если $c<M$, то M бит более высокого порядка $a(x-y){\bmod {2}}^{w}$ содержат как 0, так и 1, поэтому это точно, что $h(x)\neq h(y)$. Наконец, если $c=M$ затем немного $w-M$ из $a(x-y){\bmod {2}}^{w}$ равен 1 и $h_{a}(x)=h_{a}(y)$ тогда и только тогда, когда биты $w-1,\ldots ,w-M+1$ также равны 1, что происходит с вероятностью $1/2^{M-1}=2/m$.

Этот анализ является точным, как можно показать на примере $x=2^{w-M-2}$ и $y=3x$. Чтобы получить действительно «универсальную» хеш-функцию, можно использовать схему «умножить-сложить-сдвиг», которая выбирает биты более высокого порядка.

$h_{a,b}(x)=((ax+b){\bmod {2}}^{w+M})\,\mathrm {div} \,2^{w},$

где $a$ представляет собой случайное положительное целое число с $a<2^{2w}$ и $b$ представляет собой случайное неотрицательное целое число с $b<2^{2w}$. Для этого необходимо выполнить арифметические действия $2w$-битные беззнаковые целые числа. Эта версия множественного сдвига принадлежит Дитцфельбингеру и позже была более точно проанализирована Вельфелем.

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

В этом разделе рассматривается хеширование вектора машинных слов фиксированной длины. Интерпретируйте ввод как вектор ${\bar {x}}=(x_{0},\dots ,x_{k-1})$ из $k$ машинные слова (целые числа $w$ бит каждый). Если $H$ — универсальное семейство со свойством равномерной разности, следующее семейство (восходящее к Картеру и Вегману) ) также обладает свойством равномерной разности (и, следовательно, является универсальным):

$h({\bar {x}})=\left(\sum _{i=0}^{k-1}h_{i}(x_{i})\right)\,{\bmod {~}}m$, где каждый $h_{i}\in H$ выбирается независимо случайным образом.

Если $m$ является степенью двойки, то суммирование можно заменить исключающим или.

На практике, если доступна арифметика двойной точности, она реализуется с помощью семейства хэш-функций с умноженным сдвигом. Инициализируйте хэш-функцию с помощью вектора ${\bar {a}}=(a_{0},\dots ,a_{k-1})$ случайных нечетных целых чисел на $2w$ бит каждый. Тогда, если количество ячеек равно $m=2^{M}$ для $M\leq w$:

$h_{\bar {a}}({\bar {x}})=\left({\big (}\sum _{i=0}^{k-1}x_{i}\cdot a_{i}{\big )}~{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}$.

Можно сократить вдвое количество умножений, что на практике примерно означает двукратное ускорение. Инициализируйте хэш-функцию с помощью вектора ${\bar {a}}=(a_{0},\dots ,a_{k-1})$ случайных нечетных целых чисел на $2w$ бит каждый. Следующее семейство хешей является универсальным:

$h_{\bar {a}}({\bar {x}})=\left({\Big (}\sum _{i=0}^{\lceil k/2\rceil }(x_{2i}+a_{2i})\cdot (x_{2i+1}+a_{2i+1}){\Big )}{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}$.

Если операции двойной точности недоступны, можно интерпретировать входные данные как вектор полуслов ( $w/2$-битовые целые числа). Затем алгоритм будет использовать $\lceil k/2\rceil$ умножения, где $k$ было число полуслов в векторе. Таким образом, алгоритм работает со «скоростью» одного умножения на входное слово.

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

Также возможна сильная универсальность на высокой скорости. Инициализируйте хэш-функцию с помощью вектора ${\bar {a}}=(a_{0},\dots ,a_{k})$ случайных целых чисел на $2w$ биты. Вычислить

$h_{\bar {a}}({\bar {x}})^{\mathrm {strong} }=(a_{0}+\sum _{i=0}^{k-1}a_{i+1}x_{i}{\bmod {~}}2^{2w})\,\,\mathrm {div} \,\,2^{w}$.

Результат является строго универсальным на $w$ биты. Экспериментально было обнаружено, что на последних процессорах Intel он работает со скоростью 0,2 цикла ЦП на байт. $w=32$.

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

Это относится к хешированию переменного размера вектора машинных слов . Если длина строки может быть ограничена небольшим числом, лучше всего использовать векторное решение сверху (концептуально дополняя вектор нулями до верхней границы). Требуемое пространство — это максимальная длина строки, но время для вычисления $h(s)$ это всего лишь длина $s$. Поскольку нули в строке запрещены, заполнение нулями можно игнорировать при вычислении хеш-функции, не влияя на универсальность. Обратите внимание: если в строке разрешены нули, то лучше всего перед заполнением добавить ко всем строкам фиктивный ненулевой символ (например, 1): это гарантирует, что универсальность не пострадает.

Теперь предположим, что мы хотим хешировать ${\bar {x}}=(x_{0},\dots ,x_{\ell })$, где хорошая привязка $\ell$ априори не известно. Универсальная семья, предложенная обрабатывает строку $x$ как коэффициенты многочлена по модулю большого простого числа. Если $x_{i}\in [u]$, позволять $p\geq \max\{u,m\}$ быть простым и определить:

$h_{a}({\bar {x}})=h_{\mathrm {int} }\left({\big (}\sum _{i=0}^{\ell }x_{i}\cdot a^{\ell -i}{\big )}{\bmod {~}}p\right)$, где $a\in [p]$ является равномерно случайным и $h_{\mathrm {int} }$ выбирается случайным образом из целочисленной области отображения универсального семейства $[p]\mapsto [m]$.

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

uint hash(String x, int a, int p)
	uint h = INITIAL_VALUE
	for (uint i=0 ; i < x.length ; ++i)
		h = ((h*a) + x[i]) mod p
	return h

Этот скользящий хэш Рабина-Карпа основан на линейном конгруэнтном генераторе . Вышеуказанный алгоритм также известен как мультипликативная хеш-функция . На практике оператора mod и параметра p можно вообще избежать, просто разрешив переполнение целого числа, поскольку оно эквивалентно mod ( Max-Int-Value + 1) во многих языках программирования. В таблице ниже показаны значения, выбранные для инициализации h и a для некоторых популярных реализаций.

Выполнение	INITIAL_VALUE	а
Бернштейна Хэш-функция djb2	5381	33
СТЛПорт 4.6.2	0	5
Кернигана и Ритчи Хэш-функция	0	31
java.lang.String.hashCode()	0	31

Рассмотрим две строки ${\bar {x}},{\bar {y}}$ и пусть $\ell$ быть длиной более длинного; для анализа более короткая строка концептуально дополняется нулями до длины $\ell$. Столкновение перед применением $h_{\mathrm {int} }$ подразумевает, что $a$ является корнем многочлена с коэффициентами ${\bar {x}}-{\bar {y}}$. Этот полином имеет не более $\ell$ корни по модулю $p$, поэтому вероятность столкновения не более $\ell /p$. Вероятность столкновения через случайное $h_{\mathrm {int} }$ приводит общую вероятность столкновения к ${\frac {1}{m}}+{\frac {\ell }{p}}$. Таким образом, если простое число $p$ достаточно велико по сравнению с длиной хешируемых строк, семейство очень близко к универсальному (по статистическому расстоянию ).

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

Как избежать модульной арифметики

Чтобы смягчить вычислительные издержки модульной арифметики, на практике используются три приема:

1. Человек выбирает главное $p$ быть близким к степени двойки, например простому числу Мерсенна . Это позволяет выполнять арифметические операции по модулю $p$ быть реализовано без деления (с использованием более быстрых операций, таких как сложение и сдвиг). Например, в современных архитектурах можно работать с $p=2^{61}-1$, пока $x_{i}$'s - 32-битные значения.
2. К блокам можно применять векторное хеширование. Например, векторное хеширование применяется к каждому блоку строки из 16 слов, а хеширование строки применяется к $\lceil k/16\rceil$ результаты. Поскольку более медленное хеширование строк применяется к значительно меньшему вектору, оно, по сути, будет таким же быстрым, как и векторное хеширование.
3. В качестве делителя выбирают степень двойки, что позволяет выполнять арифметические операции по модулю. $2^{w}$ реализовать без деления (с использованием более быстрых операций битовой маскировки ). Семейство хеш-функций NH использует этот подход.

См. также

• K-независимое хеширование - семейство хэш-функций
• Прокручивающееся хеширование — тип хеш-функции. Страницы, отображающие краткие описания целей перенаправления.
• Табулационное хеширование – хэш-функции, вычисляемые методом исключающего или
• Минимальная независимость — метод интеллектуального анализа данных. Страницы с краткими описаниями целей перенаправления.
• Универсальная односторонняя хеш-функция - тип универсальной хеш-функции в криптографии, предложенный в качестве альтернативы устойчивым к коллизиям хеш-функциям. Страницы, отображающие описания викиданных в качестве запасного варианта.
• Последовательность с низким расхождением - Тип математической последовательности
• Идеальное хеширование – хеш-функция без каких-либо коллизий. Страницы с краткими описаниями целей перенаправления.

Дальнейшее чтение

• Кнут, Дональд Эрвин (1998). Искусство компьютерного программирования, Том. III: Сортировка и поиск (3-е изд.). Чтение, месса; Лондон: Аддисон-Уэсли. ISBN  0-201-89685-0 .

Внешние ссылки

• Структуры открытых данных. Раздел 5.1.1. Мультипликативное хеширование , Пэт Морин.