Русская Википедия:Случайный оракул

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

Применение

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

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

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

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

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

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

Ограничения

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

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

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

Хотя теорема Бейкера — Гилла — Соловея[8][9] показала, что существует оракул A такой, что PA = NPA, последующие работы Беннетта и Гилла[10] показали, что для случайного оракула B (функция из {0,1}n n к {0,1} так, что каждый входной элемент отображается на каждый из 0 или 1 с вероятностью 1/2, независимо от отображения всех других входных данных), PB ⊊ NPB с вероятностью 1. Подобные разделения, а также факт что случайные оракулы разделяют классы с вероятностью 0 или 1 (как следствие закона Колмогорова ноль — один), что привело к созданию гипотезы случайного Оракула, что два «приемлемых» класса сложности C1 и C2 равны тогда и только тогда, когда они равны (с вероятностью 1) под случайным оракулом (приемлемость класса сложности определена в BG81[10] Позднее было показано, что эта гипотеза неверна, поскольку два приемлемых класса сложности IP и PSPACE были показаны равными, несмотря на то, что IPA ⊊ PSPACEA для случайного оракула A с вероятностью 1.

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

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

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

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

Критика

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

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

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

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

Примечания

Шаблон:Примечания

Литература

Ссылки

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite web
  2. ↑ Шаблон:Cite news
  3. ↑ Шаблон:Статья
  4. ↑ Шаблон:Статья
  5. ↑ Ran Canetti, Oded Goldreich and Shai Halevi, The Random Oracle Methodology Revisited, STOC 1998, pp. 209—218 (PS and PDF).
  6. ↑ Шаблон:Статья
  7. ↑ Craig Gentry and Zulfikar Ramzan. «Eliminating Random Permutation Oracles in the Even-Mansour Cipher». 2004.
  8. ↑ Шаблон:Cite web
  9. ↑ Шаблон:Cite news
  10. ↑ 10,0 10,1 Шаблон:Cite news
  11. ↑ Шаблон:Статья
  12. ↑ Шаблон:Cite conference
  13. ↑ Шаблон:Cite conference
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Случайный_оракул&oldid=10813695