Универсальная односторонняя хэш-функция
 | Эта статья нуждается в дополнительных цитатах для проверки . ( ноябрь 2018 г. ) |
В криптографии универсальная односторонняя хеш-функция ( UOWHF , часто произносится как «гав») — это тип универсальной хеш-функции, имеющей особое значение для криптографии . UOWHF предлагаются в качестве альтернативы устойчивым к коллизиям хеш-функциям (CRHF). CRHF обладают сильным свойством устойчивости к коллизиям: при случайно выбранных параметрах хеш-функции трудно обнаружить любое столкновение хеш-функции. Напротив, UOWHF требует, чтобы было трудно найти коллизию, когда один прообраз выбирается независимо от параметров хэш-функции. Примитив был предложен Мони Наором и Моти Юнгом и также известен как хэш-функции с «целевой устойчивостью к коллизиям»; он использовался для создания общих схем цифровой подписи без функций лазейки, а также в схемах безопасного шифрования с открытым ключом с выбранным зашифрованным текстом.
Семейство UOWHF содержит конечное число хеш-функций, каждая из которых иметь одинаковую вероятность использования.
Определение
[ редактировать ]Охранное свойство UOWHF заключается в следующем. Позволять быть алгоритмом, который работает в два этапа:
- Изначально, не получает никаких входных данных (или просто параметр безопасности) и выбирает значение .
- Хэш-функция выбирается случайным образом из семьи. затем получает и должен вывести такой, что .
Тогда для всех полиномиальных времен вероятность того, что успех ничтожен.
Приложения
[ редактировать ]Считается, что UOWHF менее затратны в вычислительном отношении, чем CRHF, и чаще всего используются в целях повышения эффективности в схемах, где выбор хеш-функции происходит на каком-то этапе выполнения, а не заранее. Например, криптосистема Крамера-Шоупа использует UOWHF как часть проверки достоверности своих зашифрованных текстов.
См. также
[ редактировать ]Дальнейшее чтение
[ редактировать ]- Гольдрейх, Одед (2004). Основы криптографии . Том. 2. Издательство Кембриджского университета.