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

Универсальное хеширование — это вероятностный метод построения хеш-функций, при котором из некоторого семейства функций случайным образом выбирается одна конкретная функция для использования в конкретном приложении. Основная цель универсального хеширования — минимизировать вероятность коллизий (ситуаций, когда двум разным ключам соответствует одно и то же хеш-значение) для любого заранее неизвестного набора входных данных, в том числе для данных, специально подобранных злоумышленником. Ключевое свойство универсального семейства хеш-функций заключается в том, что для любых двух различных ключей вероятность того, что случайно выбранная функция из этого семейства присвоит им одинаковое хеш-значение, не превышает величины, обратной размеру области значений функции (обычно 1/m, где m — количество возможных хеш-значений).

¶История

Концепция универсального хеширования была впервые предложена американскими учёными Ларри Картером и Марком Вегманом в 1979 году. В своей основополагающей работе «Universal Classes of Hash Functions» они формализовали идею рандомизированного выбора хеш-функции и доказали, что такой подход позволяет гарантировать хорошую производительность хеш-таблиц в среднем, независимо от распределения входных данных. До этого основным недостатком детерминированных хеш-функций была их уязвимость к специально подобранным наборам ключей, которые могли вызывать большое количество коллизий и, как следствие, деградацию производительности (например, в хеш-таблицах с цепочками время поиска могло стать линейным). Универсальное хеширование стало важным шагом в развитии алгоритмов и структур данных, особенно в контексте обеспечения устойчивости к атакам типа «отказ в обслуживании» (DoS), основанным на коллизиях.

¶Определение и формальные свойства

Семейство хеш-функций H, отображающих множество ключей U в множество значений {0, 1, …, m-1}, называется универсальным, если для любых двух различных ключей x и y (x ≠ y) выполняется неравенство:

\[ \Pr_{h \in H}[h(x) = h(y)] \le \frac{1}{m} \]

где вероятность берётся по случайному равновероятному выбору функции h из семейства H.

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

¶Сильно универсальное хеширование (2-независимое)

Более сильное свойство — сильно универсальное (или 2-независимое) хеширование. Семейство H называется сильно универсальным, если для любых двух различных ключей x и y и любых (не обязательно различных) значений a и b из области значений выполняется:

\[ \Pr_{h \in H}[h(x) = a \land h(y) = b] = \frac{1}{m^2} \]

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

¶Примеры универсальных семейств

Существует несколько простых и эффективных конструкций универсальных семейств хеш-функций.

¶Семейство на основе умножения по модулю простого числа

Пусть p — простое число, большее максимально возможного значения ключа (например, p > |U|). Рассмотрим семейство функций вида:

\[ h_{a,b}(x) = ((a \cdot x + b) \mod p) \mod m \]

где a и b — случайные числа, такие что a ∈ {1, 2, …, p-1}, b ∈ {0, 1, …, p-1}. Это семейство является универсальным. Вероятность коллизии для двух различных ключей x и y не превышает 1/m. Данная конструкция проста в реализации и широко используется на практике.

¶Семейство на основе полиномов

Для обеспечения k-независимости (обобщение 2-независимости) можно использовать полиномы степени k-1 над полем простого порядка. Например, для 2-независимости (сильно универсального) семейства можно использовать функцию:

\[ h_{a,b}(x) = (a \cdot x + b) \mod p \]

где a и b выбираются случайно, а p — простое число. Эта конструкция является частным случаем предыдущей, но без дополнительного взятия модуля m. Для получения значений в диапазоне [0, m-1] результат дополнительно приводится по модулю m.

¶Семейство на основе умножения с последующим сдвигом (Carter-Wegman)

Другой распространённый подход, особенно эффективный для целочисленных ключей, — использование умножения на нечётное число и сдвига. Пусть w — размер машинного слова (например, 32 или 64 бита). Выбирается случайное нечётное число a. Тогда хеш-функция определяется как:

\[ h_a(x) = (a \cdot x) \gg (w - m) \]

где «>>» — битовый сдвиг вправо. Это семейство является универсальным для m, являющегося степенью двойки. Оно очень быстрое, так как требует всего одну операцию умножения и один сдвиг.

¶Применение

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

¶Хеш-таблицы

Основное и наиболее известное применение — построение хеш-таблиц с гарантированной производительностью. При использовании универсального хеширования ожидаемое время выполнения операций вставки, удаления и поиска в хеш-таблице с разрешением коллизий методом цепочек составляет O(1 + α), где α — коэффициент заполнения. Это верно для любого набора входных данных, что делает хеш-таблицы устойчивыми к атакам, основанным на коллизиях. Без универсального хеширования злоумышленник, зная детерминированную хеш-функцию, может подобрать множество ключей, все из которых будут хешироваться в одну ячейку, что приведёт к деградации производительности до O(n).

¶Криптография и аутентификация

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

¶Алгоритмы и структуры данных

• Фильтры Блума: Для минимизации вероятности ложных положительных срабатываний могут использоваться универсальные хеш-функции.
• Поиск подстрок (алгоритм Рабина-Карпа): Использует хеширование для сравнения строк. Хотя классический алгоритм использует полиномиальное хеширование, которое не является универсальным, существуют его модификации с универсальными семействами для повышения надёжности.
• Минимизация хеш-функций (MinHash): Техника для оценки сходства множеств, основанная на использовании нескольких независимых хеш-функций из универсального семейства.
• Счётные фильтры (Count-Min Sketch): Вероятностная структура данных для оценки частоты элементов в потоке, использующая универсальные хеш-функции для равномерного распределения данных по матрице счётчиков.

¶Критика и ограничения

Несмотря на свои преимущества, универсальное хеширование не лишено недостатков.

• Случайность выбора: Для каждого экземпляра структуры данных (например, каждой хеш-таблицы) необходимо генерировать новую случайную хеш-функцию. Это требует источника случайности и может быть неудобно в некоторых приложениях, где требуется детерминированное поведение.
• Накладные расходы: Вычисление универсальной хеш-функции может быть немного медленнее, чем простой детерминированной функции (например, взятие остатка от деления), хотя для многих конструкций (например, на основе умножения) эта разница незначительна.
• Гарантии только в среднем: Универсальное хеширование даёт гарантии на ожидаемое количество коллизий для фиксированного набора ключей. Однако для конкретного выбора функции может возникнуть больше коллизий, чем ожидалось, хотя вероятность этого мала. Для критически важных приложений могут потребоваться более сильные методы, такие как совершенное хеширование (для статических наборов ключей) или хеширование с кукушкой (Cuckoo Hashing).
• Не является криптографически стойким: Универсальные хеш-функции не предназначены для обеспечения криптографической стойкости, такой как необратимость или устойчивость к коллизиям для активного противника. Для криптографических целей используются криптографические хеш-функции (например, SHA-256), которые обладают гораздо более сильными, но и более дорогими свойствами.

¶Источники

• Carter, J. L., & Wegman, M. N. (1979). Universal classes of hash functions. Journal of Computer and System Sciences, 18(2), 143-154.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. (Глава 11: Хеш-таблицы).
• Motwani, R., & Raghavan, P. (1995). Randomized Algorithms. Cambridge University Press. (Глава 8: Хеширование).
• Wegman, M. N., & Carter, J. L. (1981). New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences, 22(3), 265-279.