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

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

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

Применение

Случайные оракулы обычно используются в качестве идеализированной замены криптографических хеш-функций в схемах, где необходимы сильные предположения о случайности выходных данных хеш-функции . Такое доказательство обычно показывает, что система или протокол безопасны, показывая, что злоумышленник должен требовать невозможного поведения от оракула или должен решить какую-то математическую задачу, которую, как считают, трудно решить. Не все виды использования криптографических хеш-функций требуют случайных оракулов : схемы, которые требуют только одного или нескольких свойств, имеющих определение в стандартной модели (таких как сопротивление столкновению , сопротивление прообразу, сопротивление второму прообразу и т. д.), часто могут быть доказаны как безопасные в стандартной модели (например, криптосистема Крамера – Шоупа ).

Случайные оракулы уже давно рассматриваются в теории вычислительной сложности , и многие схемы доказали свою безопасность в модели случайного оракула, например, оптимальное асимметричное шифрование , RSA-FDH и схема вероятностной подписи . В 1986 году и Ади Шамир показали основное применение случайных оракулов — удаление взаимодействия из протоколов для создания подписей.

В 1989 году Рассел Импальяццо и Стивен Рудич продемонстрировали ограничение случайных оракулов, а именно, что одного их существования недостаточно для обмена секретным ключом .

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

Когда случайный оракул используется в качестве доказательства безопасности, он становится доступным для всех игроков, включая противника или противников. Один оракул можно рассматривать как несколько оракулов, предварительно ожидая фиксированную битовую строку в начале каждого запроса (например, запросы, отформатированные как «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 единиц времени (из-за этой особенности случайный оракул является эффективным).

Таким образом, случайный оракул точно имитируется полиномиально ограниченным алгоритмом .

Ограничения

Известны некоторые искусственные схемы подписи и шифрования, которые доказали свою безопасность в модели случайного оракула, но они тривиально небезопасны, когда любая реальная функция заменяет случайный оракул. Тем не менее, для любого более естественного протокола доказательство безопасности в модели случайного оракула дает очень убедительные доказательства практической безопасности протокола.

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

Гипотеза Случайного оракула

Хотя теорема Бейкера — Гилла — Соловея показала, что существует оракул A такой, что P ^A = NP ^A , последующие работы Беннетта и Гилла показали, что для случайного оракула B (функция из {0,1} ⁿ n к {0,1} так, что каждый входной элемент отображается на каждый из 0 или 1 с вероятностью 1/2, независимо от отображения всех других входных данных), P ^B ⊊ NP ^B с вероятностью 1. Подобные разделения, а также факт что случайные оракулы разделяют классы с вероятностью 0 или 1 (как следствие закона Колмогорова ноль — один ), что привело к созданию гипотезы случайного Оракула, что два «приемлемых» класса сложности C ₁ и C ₂ равны тогда и только тогда, когда они равны (с вероятностью 1) под случайным оракулом (приемлемость класса сложности определена в BG81 Позднее было показано, что эта гипотеза неверна, поскольку два приемлемых класса сложности IP и PSPACE были показаны равными, несмотря на то, что IP ^A ⊊ PSPACE ^A для случайного оракула A с вероятностью 1.

Идеальный шифр

Идеальный шифр — это оракул со случайной перестановкой , который используется для моделирования идеализированного блочного шифра .

Произвольная перестановка расшифровывает каждый блок зашифрованного текста в один и только один блок открытого текста и наоборот, поэтому существует однозначное соответствие. Некоторые криптографические доказательства делают не только «прямую» перестановку доступной для всех игроков, но и «обратную» перестановку.

Недавние работы показали, что идеальный шифр может быть построен из случайного оракула с использованием 10-раундовых или даже 8-раундовых сетей Фейстеля .

Критика

Канетти, Голдрайх и Халеви высказали негативное отношение к доказательствам, построенными на модели со случайным оракулом . Они продемонстрировали, что существуют схемы цифровой подписи и шифрования , доказуемо стойкие в рамках в рамках модели случайного оракула, но уязвимые при реализации в реальных приложениях. Их основная идея заключалась в изобретении плохих схем цифровой подписи или шифрования . В обычных условиях данные схемы работают хорошо, но при некоторых условиях (в основном, нарушение случайности) становятся плохими. Однако три автора пришли к разным выводам относительно полезности модели случайного оракула

Канетти считает, что модель случайного оракула представляет неудачную абстракцию и снижает ценность метода «сведения к противоречию». Он предложил направить научные исследования на поиск специфических полезных свойств модели случайного оракула .

Голдрайх считает, что проблема заключается в неполноте модели и рекомендует на включать доказательства, использующие данный метод. Однако, он полагает, что модель случайного оракула имеет определённую ценность для проверки криптосистем на стойкость .

Халеви считает, что нынешние успехи метода сведения к противоречию являются случайными: «Нет никаких оснований утверждать, что все существующие схемы, стойкость которых доказана с помощью модели случайного оракула, в действительности являются стойкими» .

Примечания

Литература

• Венбо Мао. Современная криптография: теория и практика. — Москва: Издательский дом «Вильямс», 2005. — 768 с. — ISBN 5-8459-0847-7 .

Ссылки