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

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

Введение

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

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

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

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

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

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

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

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

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

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

Определение. Семейство хеш-функций называется универсальным[1], если

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

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

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

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

Теорема 1.Для любого семейства(не обязательно универсального) хеш-функций существуют такие, что

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

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

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

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

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

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

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

.

Довольно часто[1] известно приближенное число ключей, которое необходимо хранить в хеш-таблице. Тогда, можно подобрать размер хеш-таблицы таким образом, чтобы отношение было приблизительно равно 1. Значит, согласно теореме 3, ожидаемая стоимость исполнения последовательности запросов будет прямо пропорционально числу запросов . Причём это справедливо для любой последовательности запросов , а не для некоторой «средней» последовательности.

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

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

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

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

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

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

Выберем простое число и рассмотрим поле и его мультипликативную группу .

Теорема. Множество функций вида , где , является универсальным (Это было показано в работе Картера и Вегмана[1]).

Действительно, только при

Если , то разность и может быть обращена по модулю . Отсюда можно получить

Это уравнение имеет решений, причем правая часть может принимать значений. Таким образом, вероятность коллизий равна

,

которая стремится к при увеличении .

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

Пусть число является простым. Пусть входные данные представлены как последовательность элементов, принадлежащих , то есть .

Для всех последовательностей вида рассмотрим функцию вида

Положим, что

Видно, что содержит

Теорема. Множество является универсальным семейством хеш-функций (Это также было показано Картером и Вегманом[1]).

Действительно, если , причём , то тогда и только тогда, когда

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

Это семейство функций можно обобщить[5]. Рассмотрим семейство функций и для вектора рассмотрим хеш-функцию

, где

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

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

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

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

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

где

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

Применение

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

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

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

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

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

См. также

Примечания

  1. Carter, Larry; Wegman, Mark N. Universal Classes of Hash Functions (англ.) // Journal of Computer and System Sciences : journal. — 1979. Vol. 18, no. 2. P. 143—154. doi:10.1016/0022-0000(79)90044-8.
  2. Thorup, Mikkel, Speed Hashing for Integers and Strings (недоступная ссылка), Cornell University Library, July 15, 2014
  3. Motwani, Rajeev; Raghavan, Prabhakar. Randomized Algorithms (неопр.). Cambridge University Press, 1995. — С. 216—217. — ISBN 0-521-47465-5.
  4. Cormen, 2001, pp. 234—235.
  5. Thorup, Mikkel (2009). «String hashing for linear probing».: Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), 655–664. DOI:10.1137/1.9781611973068.72., section 5.3
  6. Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas(1992). «Polynomial Hash Functions Are Reliable (Extended Abstract)». Proc. 19th International Colloquium on Automata, Languages and Programming (ICALP). pp. 235—246
    • M. Wegman and L. Carter, «New hash functions and their use in authentication and set equality», Journal of Computer and System Sciences, 22 (1981), pp. 265—279.
  7. Кнут, 2007, с. 508—513.
  8. M.0.RABIN,Probabilistic algorithms, in «Proceedings of Symposium on New Directions and Recent Results in Algorithms and Complexity» (J.F.Traub,Ed.), pp.21-39,Academic Press, New York, 1976.
  9. .GOTO AND Y.KANADA,Hashing lemmas on time complexities with applications to formula manipulation, in "Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, " Yorktown Heights, N.Y.,pp.149—153.
  10. .GUSTAVSON AND D.Y.Y. YUN, Arithmetic complexity of unordered or sparse polynomials, in "Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, " Yorktown Heights, N.Y.,pp.154—159.

Литература

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

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.