Случайный оракул

В криптографии случайным оракулом называется идеализированная хеш-функция, которая на каждый новый запрос выдает случайный ответ, равномерно распределенный по области значений, с условием: если один и тот же запрос поступит дважды, то ответ должен быть одинаковым. Другими словами, случайный оракул — это математическая функция, выбранная случайным образом, которая отображает каждый возможный запрос в фиксированный случайный ответ из заранее заготовленной области ответов.

Случайные оракулы как математическая абстракция были впервые использованы в строгих криптографических доказательствах в публикации 1993 года Михира Белларе и Филиппа Рогэвея. Они обычно используются в случаях, когда доказательство не может быть выполнено с использованием более слабых предположений о криптографической хеш-функции. Система, которая доказала свою безопасность, когда каждая хеш-функция заменена случайным оракулом, описывается как безопасная в модели случайного оракула, в отличие от безопасной в стандартной модели криптографии.

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

Источник: Википедия