Универсальная односторонняя хэш-функция

В криптографии универсальная односторонняя хэш-функция ( UOWHF , часто произносится как «гав») — это тип универсальной хеш-функции, имеющей особое значение для криптографии . UOWHF предлагаются в качестве альтернативы устойчивым к коллизиям хеш-функциям (CRHF). CRHF обладают сильным свойством устойчивости к коллизиям: при случайно выбранных параметрах хеш-функции трудно обнаружить любое столкновение хеш-функции. Напротив, UOWHF требует, чтобы было трудно найти коллизию, когда один прообраз выбирается независимо от параметров хэш-функции. Примитив был предложен Мони Наором и Моти Юнгом и также известен как хэш-функции с «целевой устойчивостью к коллизиям»; он использовался для создания общих схем цифровой подписи без функций лазейки, а также в схемах безопасного шифрования с открытым ключом с выбранным зашифрованным текстом.

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

Определение

Охранное свойство UOWHF заключается в следующем. Позволять $A$ быть алгоритмом, который работает в два этапа:

• Изначально, $A$ не получает никаких входных данных (или просто параметр безопасности) и выбирает значение $x$.
• Хэш-функция $H$ выбирается случайным образом из семьи. $A$ затем получает $H$ и должен вывести $y\neq x$ такой, что $H(x)=H(y)$.

Тогда для всех полиномиальных времен $A$ вероятность того, что $A$ успех ничтожен.

Приложения

Считается, что UOWHF менее затратны в вычислительном отношении, чем CRHF, и чаще всего используются в целях повышения эффективности в схемах, где выбор хеш-функции происходит на каком-то этапе выполнения, а не заранее. Например, криптосистема Крамера-Шоупа использует UOWHF как часть проверки достоверности своих зашифрованных текстов.

См. также

• Атака прообраза

Дальнейшее чтение

• Гольдрейх, Одед (2004). Основы криптографии . Том. 2. Издательство Кембриджского университета.

Внешние ссылки

• Мони Наор и Моти Юнг , « Универсальные односторонние хэш-функции и их криптографические приложения », 1989.