Войти
В криптографии случайный оракул - это оракул (теоретический черный ящик ), который отвечает на каждый уникальный запрос (действительно) случайным ответом, выбранным равномерно из его выходной области. Если запрос повторяется, он отвечает одинаково каждый раз при отправке этого запроса.
Другими словами, случайный оракул - это математическая функция, выбираемая равномерно случайным образом, то есть функция, отображающая каждый возможный запрос в (фиксированный) случайный ответ из его выходной области.
Случайные оракулы как математическая абстракция были впервые использованы в строгих криптографических доказательствах в публикации 1993 г. Михиром Белларе и Филипом Рогавэем (1993). Обычно они используются, когда доказательство не может быть выполнено с использованием более слабых предположений о криптографической хеш-функции . Система, которая доказала свою безопасность, когда каждая хеш-функция заменена случайным оракулом, описывается как защищенная в модели случайного оракула, в отличие от стандартной модели криптографии.
Случайные оракулы обычно используются в качестве идеализированной замены для криптографических хэш-функций в схемах, где требуются строгие предположения о случайности выходных данных хэш-функции. Такое доказательство часто показывает, что система или протокол являются безопасными, показывая, что злоумышленник должен потребовать от оракула невозможного поведения или решить некую математическую задачу, которая считается сложной, чтобы взломать ее. Однако он только подтверждает такие свойства в случайной модели оракула, гарантируя отсутствие серьезных недостатков дизайна. Вообще говоря, неверно, что такое доказательство подразумевает те же свойства в стандартной модели. Тем не менее, доказательство в модели случайного оракула считается лучше, чем полное отсутствие формального доказательства безопасности.
Не все виды использования криптографических хеш-функций требуют случайных оракулов: схем, требующих только одного или нескольких свойств, имеющих определение в стандартная модель (например, сопротивление столкновению, сопротивление прообразу, сопротивление второму прообразу и т. Д.) Часто может быть доказана надежностью в стандарте модель (например, криптосистема Крамера – Шупа ).
Случайные оракулы давно рассматриваются в теории вычислительной сложности, и многие схемы доказали свою безопасность в модели случайных оракулов, например, Оптимальное асимметричное шифрование, RSA-FDH и. В 1986 году Амос Фиат и Ади Шамир продемонстрировали главное применение случайных оракулов - удаление взаимодействия из протоколов для создания подписей.
В 1989 году Рассел Импаглиаццо и Стивен Рудич показали ограничение случайных оракулов, а именно, что их существования недостаточно для обмена секретными ключами.
В 1993 году Михир Белларе и Филип Рогавей первыми выступили за их использование в криптографических конструкциях. В их определении случайный оракул создает битовую строку бесконечной длины, которая может быть усечена до желаемой длины.
Когда случайный оракул используется в доказательстве безопасности, он становится доступным для всех игроков, включая противника или противников. Один оракул можно рассматривать как несколько оракулов, предварительно добавляя фиксированную битовую строку в начало каждого запроса (например, запросы, отформатированные как «1 | x» или «0 | x», могут рассматриваться как вызовы двух отдельных случайных оракулы, аналогично «00 | x», «01 | x», «10 | x» и «11 | x» могут использоваться для представления вызовов четырем отдельным случайным оракулам).
Согласно тезису Черча – Тьюринга, никакая функция, вычисляемая конечным алгоритмом, не может реализовать истинный случайный оракул (который по определению требует бесконечного описания, потому что он имеет бесконечно много возможных входов, и все его выходы независимы друг от друга и должны быть индивидуально указаны в любом описании).
На самом деле известны определенные искусственные схемы подписи и шифрования, которые доказали свою безопасность в модели случайного оракула, но которые тривиально небезопасны, когда любая реальная функция заменяется случайным оракулом. Тем не менее, для любого более естественного протокола доказательство безопасности в модели случайного оракула дает очень убедительные доказательства практической безопасности протокола.
В целом, если протокол доказал свою безопасность, атаки на этот протокол должны либо выходить за рамки того, что было доказано, или нарушать одно из предположений доказательства; например, если доказательство опирается на твердость целочисленной факторизации, чтобы опровергнуть это предположение, необходимо открыть алгоритм быстрой целочисленной факторизации. Вместо этого, чтобы сломать предположение о случайном оракуле, нужно обнаружить какое-то неизвестное и нежелательное свойство фактической хэш-функции; для хороших хэш-функций, где такие свойства маловероятны, рассматриваемый протокол можно считать безопасным.
Хотя теорема Бейкера – Гилла – Соловея показала, что существует такой оракул A, что P = NP, последующая работа Беннета и Гилла показала, что для случайного оракула B (функция от {0,1} до {0,1}, такая, что каждый входной элемент отображается на каждый из 0 или 1 с вероятностью 1/2, независимо от отображения всех других входов), P ⊊ NP с вероятностью 1. Подобные разделения, а также тот факт, что случайные оракулы разделяют классы с вероятностью 0 или 1 (как следствие закона нуля – единицы Колмогорова ), привели к созданию гипотезы случайного оракула, что два «приемлемых» класса сложности C 1 и C 2 равны тогда и только тогда, когда они равны (с вероятностью 1) при случайном оракуле (приемлемость класс сложности определен в BG81). Позже было показано, что эта гипотеза неверна, поскольку два приемлемых класса сложности IP и PSPACE оказались равными, несмотря на IP ⊊ PSPACE для случайного оракула A с вероятностью 1.
Идеальный шифр - это оракул со случайной перестановкой, который используется для моделирования идеализированного блочного шифра. Случайная перестановка расшифровывает каждый блок зашифрованного текста в один и только один блок открытого текста и наоборот, поэтому существует взаимно-однозначное соответствие. Некоторые криптографические доказательства делают доступной для всех игроков не только «прямую» перестановку, но и «обратную» перестановку.
Недавние работы показали, что идеальный шифр может быть построен из случайного оракула с использованием 10 или даже 8 раундов сети Фейстеля.
Постквантовая криптография изучает квантовые атаки на классические криптографические схемы. Поскольку случайный оракул является абстракцией хэш-функции , имеет смысл предположить, что квантовый злоумышленник может получить доступ к случайному оракулу в квантовой суперпозиции. Многие из классических доказательств безопасности не работают в этой квантовой случайной модели оракула и нуждаются в пересмотре.
