Прежде чем я задам свой фактический вопрос, позвольте мне сначала немного терминологии, чтобы мы все были на одной странице:
Позволять $U=\{k_1,...,k_u\}$ вселенная возможных ключей, $|U|=u$.
Мы используем хеш-таблицу $Т$ с $м$ клеток, считая от $0$ к $м-1$.
Мы используем семейство хеш-функций $Ч$, такой, что каждый $ч\в ч$ имеет вероятность $1/м$ что два разных ключа $к$ и $к'$ hash, поэтому одно и то же значение, т. е. $P(ч(к)=ч(к'))=1/м$.
Наконец, универсальное хеширование означает, что для хеширования используется случайная хеш-функция (удовлетворяющая $1/м$ упомянутое выше требование) выбирается из H. Согласно моим исследованиям (и это, кажется, согласуется с известным учебником по алгоритмам CLRS), мы всегда используем только не замужем хэш-функции на протяжении всего времени выполнения нашей хэш-таблицы. Таким образом, другие элементы в семействе хэшей актуальны только во время создания таблицы (т. е. при первом вызове программы), но одна эта функция была выбрана фиксированной, а все остальные больше не актуальны. Это также имеет смысл, потому что если бы вы выбрали разные хеш-функции для разных ключей, вам снова нужно было бы иметь сопоставление ключа с используемой функцией, что не имело бы особого смысла, это проблема, которую мы собираемся решить. : знать, где хранить ключ; но выбранная хэш-функция будет зависеть от ключа, так что мы получим парадокс. :) Так что вполне логично, что мы выбираем только одну функцию за все время выполнения.
Выяснив это, мой вопрос:
Как выбор случайной хэш-функции помогает нам затем защищаться от злоумышленника, если она по-прежнему фиксирована в течение всего времени существования таблицы? Я не вижу никакой разницы в том, чтобы заранее зафиксировать одну хэш-функцию.
Единственная мотивация, упомянутая в любой отдельной лекции и академическом материале, — усложнить жизнь противнику, потому что для любой фиксированной хэш-функции мы можем разработать последовательность ключей, которые хешируют одно и то же значение, что приводит к наихудшему поведению хеш-таблицы. Таким образом, утверждение состоит в том, что, поскольку теперь мы выбираем случайную хэш-функцию, которую вы больше не знаете, которая используется, вы также не можете разработать такую последовательность клавиш атаки. Я просто не верю этому аргументу.
После создания вашей хеш-таблицы с универсальным хешированием вы также есть одна-единственная хеш-функция, для которой можно найти такую последовательность, так что мы действительно не решили проблему. Я считаю, что важный вопрос заключается в том, откуда противник должен знать, какая хеш-функция используется!
Итак, если мы используем только одну хеш-функцию и даже делаем ее общедоступной, то вас, конечно, могут атаковать. Но почему эта функция должна быть общедоступной? Код почти никогда не публикуется, не так ли? Таким образом, предполагая, что код не является общедоступным, злоумышленник все равно не знает, какая хэш-функция используется — независимо от того, есть ли у вас одна единственная или выбранная наугад из целого семейства.
Таким образом, если мы предположим, что функция не является общедоступной, и злоумышленник может вывести ее «каким-то образом» (возможно ли это вообще? например, путем измерения времени выполнения?), то опять же не имеет значения, существует ли функция, фиксированная заранее. или это было исправлено только после инициализации таблицы.
Таким образом, в любом случае, аргумент противника просто не работает - он кажется неверным, если только используемая хеш-функция не является общедоступной, во что я просто не могу поверить. Так что же здесь происходит?
