k -независимое хеширование

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

Фон [ править ]

Целью хеширования обычно является отображение ключей из некоторого большого домена (юниверса) в меньший диапазон, например бункеры (помеченные ). При анализе рандомизированных алгоритмов и структур данных часто желательно, чтобы хэш-коды различных ключей «вели себя случайным образом». Например, если бы хэш-код каждого ключа был независимым случайным выбором , количество ключей на ячейку можно было бы проанализировать с использованием границы Чернова . Детерминированная хеш-функция не может предложить такую гарантию в условиях состязательности, поскольку злоумышленник может выбрать ключи, которые будут в точности прообразом корзины. Кроме того, детерминированная хеш-функция не позволяет перехешировать ${\ displaystyle U}$ ${\ displaystyle m}$ ${\ Displaystyle [м] = \ {0, \ точки, м-1 \}}$ ${\ Displaystyle [м]}$ : иногда входные данные оказываются плохими для хеш-функции (например, слишком много коллизий), поэтому хочется изменить хеш-функцию.

Решение этих проблем - случайный выбор функции из большого семейства хеш-функций. Случайность при выборе хеш-функции может быть использована для гарантии некоторого желаемого случайного поведения хэш-кодов любых интересующих ключей. Первым определением в этом направлении было универсальное хеширование , которое гарантирует низкую вероятность конфликта для любых двух назначенных ключей. Концепция -независимого хеширования, введенная Вегманом и Картером в 1981 г. ^[2], усиливает гарантии случайного поведения семейств обозначенных ключей и добавляет гарантию равномерного распределения хэш-кодов. ${\ displaystyle k}$ ${\ displaystyle k}$

Определения [ править ]

Наиболее строгое определение, введенное Вегманом и Картером ^[2] под названием «строго универсальное семейство хешей», заключается в следующем. Семейство хеш-функций является независимым, если для любых различных ключей и любых хэш-кодов (не обязательно различных) мы имеем: ${\ displaystyle _ {k}}$ ${\ Displaystyle Н = \ {ч: U \ к [м] \}}$ ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle (x_ {1}, \ dots, x_ {k}) \ в U ^ {k}}$ ${\ displaystyle k}$ ${\ displaystyle (y_ {1}, \ dots, y_ {k}) \ in [м] ^ {k}}$

\Pr _{h\in H}\left[h(x_{1})=y_{1}\land \cdots \land h(x_{k})=y_{k}\right]=m^{-k}

Это определение эквивалентно следующим двум условиям:

для любого фиксированного , как извлекается случайным образом из , равномерно распределяется в . $x\in U$ $h$ $H$ $h(x)$ $[m]$
для любых фиксированных, различных ключей , взятых случайным образом , являются независимыми случайными величинами. $x_{1},\dots ,x_{k}\in U$ $h$ $H$ $h(x_{1}),\dots ,h(x_{k})$

Часто бывает неудобно достичь идеальной совместной вероятности из- за проблем с округлением. Следуя ^[3], можно определить -независимую семью, удовлетворяющую: $m^{-k}$ $(\mu ,k)$

\forall

отчетливый и ,

(x_{1},\dots ,x_{k})\in U^{k}

\forall (y_{1},\dots ,y_{k})\in [m]^{k}

~~\Pr _{h\in H}\left[h(x_{1})=y_{1}\land \cdots \land h(x_{k})=y_{k}\right]\leq \mu /m^{k}

Обратите внимание, что даже если оно близко к 1, больше не являются независимыми случайными величинами, что часто является проблемой при анализе рандомизированных алгоритмов. Следовательно, более распространенной альтернативой решению проблем округления является доказательство того, что семейство хешей близко по статистике к независимому семейству, что позволяет черным ящиком использовать свойства независимости. $\mu$ $h(x_{i})$ $k$

Методы [ править ]

Полиномы со случайными коэффициентами [ править ]

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

Хеширование табуляции [ править ]

Хеширование табуляции - это метод сопоставления ключей с хеш-значениями путем разделения каждого ключа на байты , использования каждого байта в качестве индекса в таблице случайных чисел (с другой таблицей для каждой позиции байта) и объединения результатов этих поисков в таблице с помощью побитовая операция исключающее ИЛИ. Таким образом, он требует большей случайности при инициализации, чем полиномиальный метод, но позволяет избежать, возможно, медленных операций умножения. Он 3-независимый, но не 4-независимый. ^[4] Варианты хеширования табуляции могут достигать более высокой степени независимости, выполняя поиск в таблице на основе перекрывающихся комбинаций битов входного ключа или применяя простое хеширование табуляции итеративно. ^[5]^[6]

Независимость, необходимая для различных методов хеширования [ править ]

Понятие k -независимости может использоваться для различения различных методов хеширования в соответствии с уровнем независимости, необходимым для обеспечения постоянного ожидаемого времени на операцию.

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

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

С другой стороны, линейное зондирование , более простая форма открытой адресации, при которой размер шага всегда равен единице, требует 5-независимости. Может быть гарантирована работа с постоянным ожидаемым временем на операцию с 5-независимой хеш-функцией ^[8], и существуют 4-независимые хеш-функции, для которых требуется логарифмическое время на операцию. ^[9]

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

^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4.
^ а б в г Вегман, Марк Н .; Картер, Дж. Лоуренс (1981). «Новые хеш-функции и их использование при аутентификации и установлении равенства» (PDF) . Журнал компьютерных и системных наук . 22 (3): 265–279. DOI : 10.1016 / 0022-0000 (81) 90033-7 . Версия конференции в FOCS'79 . Проверено 9 февраля 2011 года . CS1 maint: discouraged parameter (link)
^ Сигел, Алан (2004). «Об универсальных классах чрезвычайно случайных хэш-функций с постоянным временем и их пространственно-временном компромиссе» (PDF) . SIAM Journal on Computing . 33 (3): 505–543. DOI : 10,1137 / S0097539701386216 . Версия конференции в FOCS'89.
^ Патрашку, Михай ; Thorup, Mikkel (2012), «Сила простого хеширования табуляции», Journal of the ACM , 59 (3): Art. 14, Arxiv : 1011,5200 , DOI : 10,1145 / 2220357,2220361 , МР 2946218
^ Siegel, Алан (2004), "Об универсальных классах крайне случайной постоянной времени хэш - функции" (PDF) , SIAM журнал по вычислениям , 33 (3): 505-543, DOI : 10,1137 / S0097539701386216 , MR 2066640 , архивируются из оригинал (PDF) на 17.02.2019
^ Thorup, М. (2013), «Простая табуляция, быстрые расширители, двойная табуляция, и высокая независимость», Труды 54 - й ежегодного IEEE симпозиум по Основе информатики (FOCS 2013) , стр 90-99,. Arxiv : 1311,3121 , DOI : 10.1109 / FOCS.2013.18 , ISBN 978-0-7695-5135-7, Руководство по ремонту 3246210 CS1 maint: discouraged parameter (link)
^ Брэдфорд, Филипп G .; Katehakis, Майкл Н. (2007), "Вероятностное исследование комбинаторных расширителей и хеширования" (PDF) , SIAM журнал по вычислениям , 37 (1): 83-111, DOI : 10,1137 / S009753970444630X , MR 2306284 , архивируется от оригинала (PDF) 25 января 2016 г. , дата обращения 19 января 2016 г.
^ Паг, Анна; Паг, Расмус ; Ружич, Милан (2009), «Линейное зондирование с постоянной независимостью», SIAM Journal on Computing , 39 (3): 1107–1120, arXiv : cs / 0612055 , doi : 10,1137 / 070702278 , MR 2538852
^ Патрашку, Михай ; Thorup, Mikkel (2010), «О k -независимости, необходимой для линейного зондирования и минимальной независимости» (PDF) , Автоматы, языки и программирование, 37-й Международный коллоквиум, ICALP 2010, Бордо, Франция, 6-10 июля 2010 г., Труды Часть I , Lecture Notes в области компьютерных наук , 6198 , Springer, С. 715-726,. Arxiv : 1302,5127 , DOI : 10.1007 / 978-3-642-14165-2_60 , ISBN 978-3-642-14164-5

Дальнейшее чтение [ править ]

Мотвани, Раджив; Рагхаван, Прабхакар (1995). Рандомизированные алгоритмы . Издательство Кембриджского университета. п. 221 . ISBN 978-0-521-47465-8.

[CLRS-1] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4.

[WC81-2] а б в г Вегман, Марк Н .; Картер, Дж. Лоуренс (1981). «Новые хеш-функции и их использование при аутентификации и установлении равенства» (PDF) . Журнал компьютерных и системных наук . 22 (3): 265–279. DOI : 10.1016 / 0022-0000 (81) 90033-7 . Версия конференции в FOCS'79 . Проверено 9 февраля 2011 года . CS1 maint: discouraged parameter (link)

[Siegel-3] Сигел, Алан (2004). «Об универсальных классах чрезвычайно случайных хэш-функций с постоянным временем и их пространственно-временном компромиссе» (PDF) . SIAM Journal on Computing . 33 (3): 505–543. DOI : 10,1137 / S0097539701386216 . Версия конференции в FOCS'89.

[4] Патрашку, Михай ; Thorup, Mikkel (2012), «Сила простого хеширования табуляции», Journal of the ACM , 59 (3): Art. 14, Arxiv : 1011,5200 , DOI : 10,1145 / 2220357,2220361 , МР 2946218

[5] Siegel, Алан (2004), "Об универсальных классах крайне случайной постоянной времени хэш - функции" (PDF) , SIAM журнал по вычислениям , 33 (3): 505-543, DOI : 10,1137 / S0097539701386216 , MR 2066640 , архивируются из оригинал (PDF) на 17.02.2019

[6] Thorup, М. (2013), «Простая табуляция, быстрые расширители, двойная табуляция, и высокая независимость», Труды 54 - й ежегодного IEEE симпозиум по Основе информатики (FOCS 2013) , стр 90-99,. Arxiv : 1311,3121 , DOI : 10.1109 / FOCS.2013.18 , ISBN 978-0-7695-5135-7, Руководство по ремонту 3246210 CS1 maint: discouraged parameter (link)

[7] Брэдфорд, Филипп G .; Katehakis, Майкл Н. (2007), "Вероятностное исследование комбинаторных расширителей и хеширования" (PDF) , SIAM журнал по вычислениям , 37 (1): 83-111, DOI : 10,1137 / S009753970444630X , MR 2306284 , архивируется от оригинала (PDF) 25 января 2016 г. , дата обращения 19 января 2016 г.

[8] Паг, Анна; Паг, Расмус ; Ружич, Милан (2009), «Линейное зондирование с постоянной независимостью», SIAM Journal on Computing , 39 (3): 1107–1120, arXiv : cs / 0612055 , doi : 10,1137 / 070702278 , MR 2538852

[9] Патрашку, Михай ; Thorup, Mikkel (2010), «О k -независимости, необходимой для линейного зондирования и минимальной независимости» (PDF) , Автоматы, языки и программирование, 37-й Международный коллоквиум, ICALP 2010, Бордо, Франция, 6-10 июля 2010 г., Труды Часть I , Lecture Notes в области компьютерных наук , 6198 , Springer, С. 715-726,. Arxiv : 1302,5127 , DOI : 10.1007 / 978-3-642-14165-2_60 , ISBN 978-3-642-14164-5

[1],