Введение
Техника выбора хеш-функций
В математике и информатике универсальное хеширование (в рандомизированном алгоритме или структуре данных) относится к случайному выбору хеш-функции из семейства хеш-функций, обладающего определенным математическим свойством (см. определение ниже). Это гарантирует небольшое ожидаемое количество коллизий, даже если данные выбираются злоумышленником. Известно множество универсальных семейств (для хеширования целых чисел, векторов, строк), и вычисление функций из этих семейств часто очень эффективно. Универсальное хеширование находит широкое применение в информатике, например, при реализации хеш-таблиц, рандомизированных алгоритмов и в криптографии.
In mathematics and computing, universal hashing (in a randomized algorithm or data structure) refers to selecting a hash function at random from a family of hash functions with a certain mathematical property (see definition below). This guarantees a low number of collisions in expectation, even if the data is chosen by an adversary. Many universal families are known (for hashing integers, vectors, strings), and their evaluation is often very efficient. Universal hashing has numerous uses in computer science, for example in implementations of hash tables, randomized algorithms, and cryptography.
Введение
Предположим, мы хотим отобразить ключи из некоторой вселенной в ячейки (обозначенные). Алгоритм должен будет обрабатывать некоторый набор данных ключей, который неизвестен заранее. Обычно целью хеширования является получение небольшого числа коллизий (ключей из вселенной, попадающих в одну и ту же ячейку). Детерминированная хеш-функция не может предложить никаких гарантий в неблагоприятных условиях, поскольку противник может выбрать ключи, являющиеся точно прообразами ячейки. Это означает, что все ключи данных попадут в одну ячейку, что делает хеширование бесполезным. Кроме того, детерминированная хеш-функция не позволяет выполнять перехеширование: иногда входные данные оказываются неудачными для хеш-функции (например, слишком много коллизий), поэтому хотелось бы изменить хеш-функцию. Решение этих проблем состоит в случайном выборе функции из семейства хеш-функций. Семейство функций называется универсальным семейством, если, другими словами, любые два различных ключа из вселенной сталкиваются с вероятностью не более, когда хеш-функция выбирается равномерно случайным образом из этого семейства. Это именно та вероятность коллизии, которую мы ожидали бы, если бы хеш-функция присваивала действительно случайные хеш-коды каждому ключу. Иногда определение смягчается на постоянный фактор, требуя лишь вероятности коллизии, а не. Эта концепция была введена Картером и Вегманом в 1977 году и нашла многочисленные применения в информатике (см., например). Если у нас есть верхняя граница вероятности коллизии, мы говорим, что у нас есть почти универсальность. Например, универсальное семейство обладает почти универсальностью. Многие, но не все, универсальные семейства обладают следующим более сильным свойством равномерной разности: , когда выбирается случайным образом из семейства, разность равномерно распределена в. Обратите внимание, что определение универсальности касается только того, является ли, что учитывает коллизии. Свойство равномерной разности сильнее. (Аналогично, универсальное семейство может быть XOR-универсальным, если, значение равномерно распределено в, где является операцией побитового исключающего ИЛИ. Это возможно только в том случае, если является степенью 2. Еще более сильным условием является парная независимость: мы имеем это свойство, когда вероятность того, что хеш-функция отобразит любой парой хеш-значений, такая же, как если бы они были совершенно случайными: парная независимость иногда называется сильной универсальностью. Другое свойство — равномерность. Мы говорим, что семейство равномерно, если все хеш-значения равновероятны: для любого хеш-значения. Универсальность не подразумевает равномерность. Однако сильная универсальность подразумевает равномерность. При наличии семейства со свойством равномерной разности можно получить парно независимое или сильно универсальное хеш-семейство, добавляя к хеш-функциям равномерно распределенную случайную константу со значениями в. (Аналогично, если является степенью 2, мы можем достичь парной независимости из XOR-универсального хеш-семейства, выполнив операцию исключающего ИЛИ с равномерно распределенной случайной константой.) Поскольку сдвиг на константу иногда не имеет значения в приложениях (например, в хеш-таблицах), то иногда не делается тщательного различия между свойством равномерной разности и парной независимостью. Для некоторых приложений (таких как хеш-таблицы) важно, чтобы наименее значимые биты хеш-значений также были универсальными. Когда семейство сильно универсально, это гарантируется: если это сильно универсальное семейство с, то семейство, состоящее из функций для всех, также сильно универсально для. К сожалению, то же самое не относится к (просто) универсальным семействам. Например, семейство, состоящее из тождественной функции, явно универсально, но семейство, состоящее из функции, не является универсальным. UMAC, Poly1305 AES и несколько других алгоритмов кода аутентификации сообщений основаны на универсальном хешировании. В таких приложениях программное обеспечение выбирает новую хеш-функцию для каждого сообщения, основанную на уникальном одноразовом номере (nonce) для этого сообщения. Несколько реализаций хеш-таблиц основаны на универсальном хешировании. В таких приложениях программное обеспечение обычно выбирает новую хеш-функцию только после того, как замечает, что "слишком много" ключей столкнулись; до тех пор одна и та же хеш-функция продолжает использоваться снова и снова. (Некоторые схемы разрешения коллизий, такие как динамическое совершенное хеширование, выбирают новую хеш-функцию каждый раз при возникновении коллизии. Другие схемы разрешения коллизий, такие как cuckoo-хеширование и хеширование с выбором из двух, допускают некоторое количество коллизий перед выбором новой хеш-функции). Обзор самых быстрых известных универсальных и сильно универсальных хеш-функций для целых чисел, векторов и строк можно найти в.
In other words, any two different keys of the universe collide with probability at most when the hash function is drawn uniformly at random from This is exactly the probability of collision we would expect if the hash function assigned truly random hash codes to every key. Sometimes, the definition is relaxed by a constant factor, only requiring collision probability rather than This concept was introduced by Carter and Wegman in 1977, and has found numerous applications in computer science (see, for example). If we have an upper bound of on the collision probability, we say that we have almost universality. So for example, a universal family has almost universality. Many, but not all, universal families have the following stronger uniform difference property:
, when is drawn randomly from the family , the difference is uniformly distributed in
Note that the definition of universality is only concerned with whether , which counts collisions. The uniform difference property is stronger. (Similarly, a universal family can be XOR universal if , the value is uniformly distributed in where is the bitwise exclusive or operation. This is only possible if is a power of two.) An even stronger condition is pairwise independence: we have this property when we have the probability that will hash to any pair of hash values is as if they were perfectly random: Pairwise independence is sometimes called strong universality. Another property is uniformity. We say that a family is uniform if all hash values are equally likely: for any hash value Universality does not imply uniformity. However, strong universality does imply uniformity. Given a family with the uniform distance property, one can produce a pairwise independent or strongly universal hash family by adding a uniformly distributed random constant with values in to the hash functions. (Similarly, if is a power of two, we can achieve pairwise independence from an XOR universal hash family by doing an exclusive or with a uniformly distributed random constant.) Since a shift by a constant is sometimes irrelevant in applications (e. g. hash tables), a careful distinction between the uniform distance property and pairwise independent is sometimes not made. For some applications (such as hash tables), it is important for the least significant bits of the hash values to be also universal. When a family is strongly universal, this is guaranteed: if is a strongly universal family with , then the family made of the functions for all is also strongly universal for Unfortunately, the same is not true of (merely) universal families. For example, the family made of the identity function is clearly universal, but the family made of the function fails to be universal. UMAC and Poly1305 AES and several other message authentication code algorithms are based on universal hashing. In such applications, the software chooses a new hash function for every message, based on a unique nonce for that message. Several hash table implementations are based on universal hashing. In such applications, typically the software chooses a new hash function only after it notices that "too many" keys have collided; until then, the same hash function continues to be used over and over. (Some collision resolution schemes, such as dynamic perfect hashing, pick a new hash function every time there is a collision. Other collision resolution schemes, such as cuckoo hashing and 2 choice hashing, allow a number of collisions before picking a new hash function). A survey of fastest known universal and strongly universal hash functions for integers, vectors, and
strings is found in.
Векторы хеширования
Этот раздел посвящен хешированию вектора фиксированной длины машинных слов. Рассматривайте входные данные как вектор машинных слов (целых чисел, состоящих из *n* бит). Если *H* – универсальное семейство с равномерным свойством разности, то следующее семейство (предложенное Картером и Вегманом) …
На практике, при наличии арифметики двойной точности, это реализуется с помощью хеш-семейства хеш-функций, основанных на умножении и сдвиге. Если операции двойной точности недоступны, входные данные можно интерпретировать как вектор полуслов (целых чисел, состоящих из *n*/2 бит). Тогда алгоритм выполнит *m* умножений, где *m* – количество полуслов в векторе. Таким образом, алгоритм работает со "скоростью" одного умножения на слово входных данных. Такую же схему можно использовать для хеширования целых чисел, интерпретируя их биты как векторы байтов. В этом варианте векторная техника известна как табличная хешировка и представляет собой практическую альтернативу универсальным схемам хеширования, основанным на умножении. Возможна также высокая скорость при сильной универсальности. Инициализируйте хеш-функцию вектором из *k* случайных целых чисел, каждое из которых состоит из *n* бит. Вычислите…
Результат является сильно универсальным для *n* бит. Экспериментально установлено, что на современных процессорах Intel для *n* = 64 он работает со скоростью 0,2 цикла ЦП на байт.