О устойчивых к коллизиям хеш-функциях в книге Каца «Введение в современную криптографию»
6.1 Определения
Хеш-функции — это просто функции, которые принимают входные данные некоторой длины и
сжимайте их в короткие выходные данные фиксированной длины.Классическое использование (не-
криптографические) хэш-функции находятся в структурах данных, где их можно использовать для
создавать хэш-таблицы, которые обеспечивают время поиска O (1) при сохранении набора элементов.
В частности, если диапазон хеш-функции H имеет размер N, то элемент x
хранится в строке H(x) таблицы размера N. Чтобы получить x, достаточно вычислить H(x) и проверить эту строку таблицы на предмет хранящихся там элементов. Хорошая хэш-функция для этой цели та, которая дает мало коллизий, где
коллизия — это пара различных элементов x и x0
для которого H(x) = H(x0);
в этом случае мы также говорим, что x и x0
столкнуться. (При столкновении два
элементы в конечном итоге хранятся в одной и той же ячейке, что увеличивает время поиска.)
Хеш-функции, устойчивые к коллизиям, похожи по духу; опять же цель
во избежание столкновений. Однако есть принципиальные отличия. Для одного,
стремление минимизировать коллизии в настройке структур данных становится
требование избегать коллизий в настройках криптографии. Кроме того, в
В контексте структур данных мы предполагаем, что набор хешируемых элементов
выбирается независимо от H и без какого-либо намерения вызвать коллизии. В
в контексте криптографии, напротив, мы сталкиваемся с противником, который
может выбирать элементы с явной целью вызвать коллизии. Это означает
что хэш-функции, устойчивые к коллизиям, разработать намного сложнее.
О концепции идеального хеширования в CLRS «Введение в алгоритмы»:
11.5 Идеальное хеширование
Мы называем метод хеширования идеальным хешированием, если для выполнения поиска в худшем случае требуется O(1) обращений к памяти.
Чтобы создать идеальную схему хеширования, мы используем два уровня хеширования с универсальным хешированием на каждом уровне.
Первый уровень по существу такой же, как и при хешировании с цепочкой: мы хэшируем n ключей в m слотов, используя хеш-функцию h, тщательно отобранную из семейства хеш-функций.
универсальные хэш-функции.
Однако вместо создания связанного списка ключей, хеширующих слот j, мы используем небольшую вторичную хэш-таблицу Sj с ассоциированной хэш-функцией hj. Выбрав
хэш-функции h j тщательно, мы можем гарантировать отсутствие коллизий на вторичном уровне.
И в https://en.wikipedia.org/wiki/Perfect_hash_function
В информатике идеальная хэш-функция h для множества S — это хеш-функция, которая отображает различные элементы в S в набор из m целых чисел, без столкновений. С математической точки зрения, это инъективная функция.
Верно ли, что в книге Каца хэш-функция, устойчивая к коллизиям, означает именно хэш-функцию без коллизий? (Я так думаю.)
Является ли идеальная хеш-функция в Википедии такой же, как устойчивая к коллизиям хеш-функция в книге Каца? (Я так думаю.)
Является ли идеальная хэш-функция в книге CLRS такой же, как устойчивая к коллизиям хеш-функция в книге Каца? (CLRS определяет идеальную хеш-функцию с точки зрения сложности доступа к памяти, равной O(1), и реализует идеальную хеш-функцию как хэш-функцию, устойчивую к коллизиям, поэтому я думаю, что хеш-функция, устойчивая к коллизиям, также является идеальным хэшем. функция, но я не уверен, что идеальная хэш-функция обязательно устойчива к коллизиям.)
Является ли идеальная хэш-функция в книге CLRS такой же, как и идеальная хэш-функция в Википедии?
Спасибо.
