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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Введение[править | править код]

Впервые понятие универсального хеширования было введено в статье[1] Картера и Вегманаruen в 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-AESruen и некоторые другие основаны на использовании универсального хеширования[7][8][9]. В этих кодах для каждого сообщения выбирается своя хеш-функция в зависимости от его одноразового уникального номера.

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

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

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

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

См. также[править | править код]

Примечания[править | править код]

  1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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. 1 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. 1 2 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
  7. * David Wagner, ed. «Advances in Cryptology — CRYPTO 2008». p. 145.
  8. * Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. «The Hash Function BLAKE». 2014. p. 10.
  9. * 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.
  10. Knuth, 2007, pp.508-513.
  11. 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.
  12. .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.
  13. .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.

Литература[править | править код]

Ссылки[править | править код]