В криптографии случайным оракулом называется идеализированная хеш-функция, которая на каждый новый запрос выдает случайный ответ, равномерно распределенный по области значений, с условием: если один и тот же запрос поступит дважды, то ответ должен быть одинаковым. Другими словами, случайный оракул — это математическая функция, выбранная случайным образом, которая отображает каждый возможный запрос в фиксированный случайный ответ из заранее заготовленной области ответов.
Случайные оракулы как математическая абстракция были впервые использованы в строгих криптографических доказательствах в публикации 1993 года Михира Белларе[en] и Филиппа Рогэвея[en]. Они обычно используются в случаях, когда доказательство не может быть выполнено с использованием более слабых предположений о криптографической хеш-функции. Система, которая доказала свою безопасность, когда каждая хеш-функция заменена случайным оракулом, описывается как безопасная в модели случайного оракула, в отличие от безопасной в стандартной модели криптографии[en].
Случайный оракул является весьма мощным, поскольку обладает тремя свойствами: детерминированность, эффективность и обеспечение равномерного распределения результирующих значений[1].
Случайные оракулы обычно используются в качестве идеализированной замены криптографических хеш-функций в схемах, где необходимы сильные предположения о случайности выходных данных хеш-функции[1]. Такое доказательство обычно показывает, что система или протокол безопасны, показывая, что злоумышленник должен требовать невозможного поведения от оракула или должен решить какую-то математическую задачу, которую, как считают, трудно решить. Не все виды использования криптографических хеш-функций требуют случайных оракулов[2]: схемы, которые требуют только одного или нескольких свойств, имеющих определение в стандартной модели (таких как сопротивление столкновению, сопротивление прообразу, сопротивление второму прообразу и т. д.), часто могут быть доказаны как безопасные в стандартной модели (например, криптосистема Крамера – Шоупа).
Случайные оракулы уже давно рассматриваются в теории вычислительной сложности, и многие схемы доказали свою безопасность в модели случайного оракула, например, оптимальное асимметричное шифрование, RSA-FDH[3] и схема вероятностной подписи. В 1986 году Амос Фиат[en] и Ади Шамир[4] показали основное применение случайных оракулов — удаление взаимодействия из протоколов для создания подписей.
В 1989 году Рассел Импальяццо и Стивен Рудич[5] продемонстрировали ограничение случайных оракулов, а именно, что одного их существования недостаточно для обмена секретным ключом.
В 1993 году Михир Белларе и Филипп Рогавей[6] были первыми, кто выступил за их использование в криптографических конструкциях. По их определению, случайный оракул создаёт битовую строку бесконечной длины, которая может быть усечена до желаемой длины.
Когда случайный оракул используется в качестве доказательства безопасности, он становится доступным для всех игроков, включая противника или противников. Один оракул можно рассматривать как несколько оракулов, предварительно ожидая фиксированную битовую строку в начале каждого запроса (например, запросы, отформатированные как «1 | x» или «0 | x», могут рассматриваться как вызовы двух отдельных случайных чисел). Оракулы, аналогично «00 | x», «01 | x», «10 | x» и «11 | x» могут использоваться для представления вызовов четырём отдельным случайным оракулам).
Случайный оракул представляет мощную гипотетическую детерминированную функцию, эффективно вычисляющую равномерно распределенные случайные величины. В модели случайного оракула предполагается существование не только случайного оракула, но и специального агента — имитатора. Предполагается, что имитатор может имитировать любого случайного оракула (даже злоумышленника). Таким образом, если кто-то захочет применить случайного оракула G к числу a, то он автоматически пошлет имитатору запрос случайному оракулу и получит от него результат G(a). Имитатор всегда честно выполняет любой запрос и всегда возвращает его результат.
Благодаря этому правилу имитатор может точно имитировать поведение случайного оракула. Пусть имитатор поддерживает G-список для оракула G, содержащий пары (a, G(a)), где хранятся предыдущие запросы а. Имитация выполняется просто: получив запрос а, имитатор проверяет, хранится ли он в списке и если да, то возвращает значение G(a) (детерминированный результат запроса), в противном случае имитатор извлекает из генеральной совокупности равномерно распределенных чисел новую величину G(a), отправляет ответ и заносит данную пару (a, G(a)) в сортированный список, поиск по которому занимает log N единиц времени (из-за этой особенности случайный оракул является эффективным).
Таким образом, случайный оракул точно имитируется полиномиально ограниченным алгоритмом[7].
Известны некоторые искусственные схемы подписи и шифрования, которые доказали свою безопасность в модели случайного оракула, но они тривиально небезопасны, когда любая реальная функция заменяет случайный оракул.[8] Тем не менее, для любого более естественного протокола доказательство безопасности в модели случайного оракула дает очень убедительные доказательства практической безопасности протокола.[9]
В целом, если протокол доказан как безопасный, атаки на этот протокол должны либо выходить за рамки доказанного, либо нарушать одно из предположений в доказательстве; например, если доказательство опирается на сложность целочисленной факторизации, чтобы нарушить это предположение, необходимо найти алгоритм быстрой целочисленной факторизации. Вместо этого, чтобы нарушить предположение о случайном оракуле, нужно обнаружить какое-то неизвестное и нежелательное свойство фактической хеш-функции; для хороших хеш-функций, где такие свойства считаются маловероятными, рассматриваемый протокол можно считать безопасным.[10]
Хотя теорема Бейкера — Гилла — Соловея[11][12] показала, что существует оракул A такой, что PA = NPA, последующие работы Беннетта и Гилла[13] показали, что для случайного оракула B (функция из {0,1}n n к {0,1} так, что каждый входной элемент отображается на каждый из 0 или 1 с вероятностью 1/2, независимо от отображения всех других входных данных), PB ⊊ NPB с вероятностью 1. Подобные разделения, а также факт что случайные оракулы разделяют классы с вероятностью 0 или 1 (как следствие закона Колмогорова ноль — один), что привело к созданию гипотезы случайного Оракула, что два «приемлемых» класса сложности C1 и C2 равны тогда и только тогда, когда они равны (с вероятностью 1) под случайным оракулом (приемлемость класса сложности определена в BG81[14] Позднее было показано, что эта гипотеза неверна, поскольку два приемлемых класса сложности IP и PSPACE были показаны равными, несмотря на то, что IPA ⊊ PSPACEA для случайного оракула A с вероятностью 1.
Идеальный шифр — это оракул со случайной перестановкой, который используется для моделирования идеализированного блочного шифра[15].
Произвольная перестановка расшифровывает каждый блок зашифрованного текста в один и только один блок открытого текста и наоборот, поэтому существует однозначное соответствие. Некоторые криптографические доказательства делают не только «прямую» перестановку доступной для всех игроков, но и «обратную» перестановку.
Недавние работы показали, что идеальный шифр может быть построен из случайного оракула с использованием 10-раундовых[16] или даже 8-раундовых[17] сетей Фейстеля.
Канетти, Голдрайх и Халеви высказали негативное отношение к доказательствам, построенными на модели со случайным оракулом[18]. Они продемонстрировали, что существуют схемы цифровой подписи и шифрования, доказуемо стойкие в рамках в рамках модели случайного оракула, но уязвимые при реализации в реальных приложениях. Их основная идея заключалась в изобретении плохих схем цифровой подписи или шифрования. В обычных условиях данные схемы работают хорошо, но при некоторых условиях (в основном, нарушение случайности) становятся плохими. Однако три автора пришли к разным выводам относительно полезности модели случайного оракула
Канетти считает, что модель случайного оракула представляет неудачную абстракцию и снижает ценность метода «сведения к противоречию». Он предложил направить научные исследования на поиск специфических полезных свойств модели случайного оракула[19].
Голдрайх считает, что проблема заключается в неполноте модели и рекомендует на включать доказательства, использующие данный метод. Однако, он полагает, что модель случайного оракула имеет определённую ценность для проверки криптосистем на стойкость[19].
Халеви считает, что нынешние успехи метода сведения к противоречию являются случайными: «Нет никаких оснований утверждать, что все существующие схемы, стойкость которых доказана с помощью модели случайного оракула, в действительности являются стойкими»[19].
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .