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

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

Предыстория [ править ]

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

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

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

Самое строгое определение, введенное Вегманом и Картером. ^[2] под названием «сильно универсальный $_{k}$ семейство хеш-функций» следующее. Семейство хеш-функций $H=\{h:U\to [m]\}$ является $k$ -независимый, если для любого $k$ отдельные клавиши $(x_{1},\dots ,x_{k})\in U^{k}$ и любой $k$ хэш-коды (не обязательно разные) $(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]=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})$ являются независимыми случайными величинами.

Часто бывает неудобно добиться идеальной совместной вероятности $m^{-k}$ из-за проблем с округлением. Следующий, ^[3] можно определить $(\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}

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

Техники [ править ]

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

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

В общем случае полином можно вычислить в любом конечном поле .Помимо полей по простому модулю, популярным выбором является поле размера $2^{n}$ , который поддерживает быструю арифметику с конечными полями на современных компьютерах.Именно такой подход использовали Дэниел Лемир и Оуэн Кейзер для CLHash. ^[4]

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

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

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

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

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

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

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

Требуемая k-независимость для хеширования Cuckoo по состоянию на 2021 год неизвестна.В 2009 году было показано ^[11] что $O(\log n)$ -независимости достаточно, и как минимум 6-независимость нужна .Другой подход — использовать хеширование Tabulation , которое не является 6-независимым, но было показано в 2012 году. ^[12] иметь другие свойства, достаточные для хеширования Cuckoo.Третий подход 2014 года ^[13] заключается в незначительной модификации хеш-таблицы кукушки с помощью так называемого тайника, который дает возможность использовать не что иное, как 2-независимые хэш-функции.

Другие приложения [ править ]

Кейн , Нельсон и Дэвид Вудрафф улучшили алгоритм Флажоле-Мартена для задачи различных элементов в 2010 году. ^[14]Чтобы дать $\varepsilon$ приближение к правильному ответу, им нужно ${\tfrac {\log 1/\varepsilon }{\log \log 1/\varepsilon }}$ -независимая хэш-функция.

Алгоритм эскиза Count для уменьшения размерности требует двух хэш-функций: одной 2-независимой и одной 4-независимой .

Алгоритм Карлоффа-Цвика для задачи MAX-3SAT может быть реализован с использованием 3-независимых случайных величин.

Алгоритм MinHash можно реализовать с помощью $\log {\tfrac {1}{\epsilon }}$ -независимая хеш-функция, как было доказано Петром Индиком в 1999 году. ^[15]

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

^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4 .
^ Jump up to: ^а ^б ^с ^д Вегман, Марк Н .; Картер, Дж. Лоуренс (1981). «Новые хеш-функции и их использование при аутентификации и установлении равенства» (PDF) . Журнал компьютерных и системных наук . 22 (3): 265–279. дои : 10.1016/0022-0000(81)90033-7 . Версия конференции в FOCS'79 . Проверено 9 февраля 2011 г.
^ Сигел, Алан (2004). «Об универсальных классах чрезвычайно случайных хэш-функций с постоянным временем и их компромиссе во времени и пространстве» (PDF) . SIAM Journal по вычислительной технике . 33 (3): 505–543. дои : 10.1137/S0097539701386216 . Версия конференции в FOCS'89.
^ Лемир, Дэниел и Оуэн Кейзер. «Более быстрое 64-битное универсальное хеширование с использованием умножения без переноса». Журнал криптографической инженерии 6.3 (2016): 171–185.
^ Патрашку, Михай ; Торуп, Миккель (2012), «Сила простого хеширования таблиц», Журнал ACM , 59 (3): Ст. 14, arXiv : 1011.5200 , doi : 10.1145/2220357.2220361 , MR 2946218
^ Сигел, Алан (2004), «Об универсальных классах чрезвычайно случайных хэш-функций с постоянным временем» (PDF) , SIAM Journal on Computing , 33 (3): 505–543, doi : 10.1137/S0097539701386216 , MR 2066640 , S2CID 1742179 , заархивировано из оригинала (PDF) 17 февраля 2019 г.
^ Торуп, М. (2013), «Простые таблицы, быстрые расширения, двойные таблицы и высокая независимость», Труды 54-го ежегодного симпозиума IEEE по основам компьютерных наук (FOCS 2013) , стр. 90–99, arXiv : 1311.3121 , дои : 10.1109/FOCS.2013.18 , ISBN 978-0-7695-5135-7 , МР 3246210
^ Брэдфорд, Филипп Г.; Катехакис, Майкл Н. (2007), «Вероятностное исследование комбинаторных расширителей и хеширования» (PDF) , SIAM Journal on Computing , 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
^ Патрашку, Михай ; Торуп, Миккель (2010), «О $k$ -независимости, необходимой для линейного зондирования и минимальной независимости» (PDF) , Автоматы, языки и программирование, 37-й международный коллоквиум, ICALP 2010, Бордо, Франция, 6–10 июля 2010 г., Материалы , Часть I , Конспект лекций по информатике , вып. 6198, Springer, стр. 715–726, arXiv : 1302.5127 , doi : 10.1007/978-3-642-14165-2_60 , ISBN 978-3-642-14164-5
^ Коэн, Джеффри С. и Дэниел М. Кейн. «Границы независимости, необходимые для хеширования с кукушкой». Транзакции ACM в алгоритмах (2009).
^ Путрашку, Михай и Миккель Торуп. «Сила простого хеширования таблиц». Журнал ACM (JACM) 59.3 (2012): 1-50.
^ Аумюллер, Мартин, Мартин Дитцфельбингер и Филипп Вельфель. «Явных и эффективных хэш-семейств достаточно для кукушкиного хеширования с помощью тайника». Алгоритмика 70.3 (2014): 428-456.
^ Кейн, Дэниел М., Джелани Нельсон и Дэвид П. Вудрафф. «Оптимальный алгоритм решения задачи о различных элементах». Материалы двадцать девятого симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных. 2010.
^ Индик, Петр. «Небольшое приблизительно минимальное независимое семейство хэш-функций». Журнал алгоритмов 38.1 (2001): 84-90.

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

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

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

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

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

[4] Лемир, Дэниел и Оуэн Кейзер. «Более быстрое 64-битное универсальное хеширование с использованием умножения без переноса». Журнал криптографической инженерии 6.3 (2016): 171–185.

[5] Патрашку, Михай ; Торуп, Миккель (2012), «Сила простого хеширования таблиц», Журнал ACM , 59 (3): Ст. 14, arXiv : 1011.5200 , doi : 10.1145/2220357.2220361 , MR 2946218

[6] Сигел, Алан (2004), «Об универсальных классах чрезвычайно случайных хэш-функций с постоянным временем» (PDF) , SIAM Journal on Computing , 33 (3): 505–543, doi : 10.1137/S0097539701386216 , MR 2066640 , S2CID 1742179 , заархивировано из оригинала (PDF) 17 февраля 2019 г.

[7] Торуп, М. (2013), «Простые таблицы, быстрые расширения, двойные таблицы и высокая независимость», Труды 54-го ежегодного симпозиума IEEE по основам компьютерных наук (FOCS 2013) , стр. 90–99, arXiv : 1311.3121 , дои : 10.1109/FOCS.2013.18 , ISBN 978-0-7695-5135-7 , МР 3246210

[8] Брэдфорд, Филипп Г.; Катехакис, Майкл Н. (2007), «Вероятностное исследование комбинаторных расширителей и хеширования» (PDF) , SIAM Journal on Computing , 37 (1): 83–111, doi : 10.1137/S009753970444630X , MR 2306284 , заархивировано из оригинала (PDF) от 25 января 2016 г. , получено 19 января 2016 г.

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

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

[11] Коэн, Джеффри С. и Дэниел М. Кейн. «Границы независимости, необходимые для хеширования с кукушкой». Транзакции ACM в алгоритмах (2009).

[12] Путрашку, Михай и Миккель Торуп. «Сила простого хеширования таблиц». Журнал ACM (JACM) 59.3 (2012): 1-50.

[13] Аумюллер, Мартин, Мартин Дитцфельбингер и Филипп Вельфель. «Явных и эффективных хэш-семейств достаточно для кукушкиного хеширования с помощью тайника». Алгоритмика 70.3 (2014): 428-456.

[14] Кейн, Дэниел М., Джелани Нельсон и Дэвид П. Вудрафф. «Оптимальный алгоритм решения задачи о различных элементах». Материалы двадцать девятого симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных. 2010.

[15] Индик, Петр. «Небольшое приблизительно минимальное независимое семейство хэш-функций». Журнал алгоритмов 38.1 (2001): 84-90.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]