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

Перейти к навигацииПерейти к поиску

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

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

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

Применение

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

Случайные оракулы уже давно рассматриваются в теории вычислительной сложности, и многие схемы доказали свою безопасность в модели случайного оракула, например, оптимальное асимметричное шифрование, RSA-FDH[3] и схема вероятностной подписи. В 1986 году Амос Фиат[англ.] и Ади Шамир[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[13] Позднее было показано, что эта гипотеза неверна, поскольку два приемлемых класса сложности IP и PSPACE были показаны равными, несмотря на то, что IPA ⊊ PSPACEA для случайного оракула A с вероятностью 1.

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

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

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

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

Критика

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

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

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

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

Примечания

  1. ↑ 1 2 Современная Криптография, 2005, с. 351.
  2. ↑ Современная Криптография, 2005, с. 578—585.
  3. ↑ RSA-FDH (Full Domain Hash). www.iacr.org. Дата обращения: 23 декабря 2018. Архивировано 5 июня 2019 года.
  4. ↑ Fiat, Amos; Shamir, Adi (1986). "How to Prove Yourself: Practical Solutions to Identification and Signature Problems". CRYPTO. pp. 186—194.
  5. ↑ Impagliazzo, Russell; Rudich, Steven. Limits on the Provable Consequences of One-Way Permutations (англ.) // STOC[англ.] : journal. — 1989. — P. 44—61.
  6. ↑ Bellare, Mihir[англ.]; Rogaway, Phillip[англ.]. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols (англ.) // ACM Conference on Computer and Communications Security : journal. — 1993. — P. 62—73. Архивировано 4 мая 2008 года.
  7. ↑ Современная Криптография, 2005, с. 559—560.
  8. ↑ Ran Canetti, Oded Goldreich and Shai Halevi, The Random Oracle Methodology Revisited, STOC 1998, pp. 209—218 (PS and PDF).
  9. ↑ Koblitz, Neal; Menezes, Alfred J. The Random Oracle Model: A Twenty-Year Retrospective (англ.) // Another Look : journal. — 2015. Архивировано 2 апреля 2015 года.
  10. ↑ Craig Gentry and Zulfikar Ramzan. «Eliminating Random Permutation Oracles in the Even-Mansour Cipher» Архивная копия от 10 августа 2017 на Wayback Machine. 2004.
  11. ↑ Теорема Бейкера — Гилла — Соловэя — Викиконспекты. neerc.ifmo.ru. Дата обращения: 14 декабря 2018. Архивировано 28 января 2023 года.
  12. ↑ Baker, Theodore; Gill, John; Solovay, Robert (1975). "Relativizations of the P =? NP Question". SIAM J. Comput. Vol. 4, no. 4. SIAM. pp. 431—442. doi:10.1137/0204037.
  13. ↑ 1 2 Bennett, Charles; Gill, John (1981). "Relative to a Random Oracle A, P ≠ NP ≠ co-NP with Probability 1". SIAM J. Comput. Vol. 10, no. 1. SIAM. pp. 96—113.
  14. ↑ Jean-Sebastien Coron, Jacques Patarin, Yannick Seurin. The Random Oracle Model and the Ideal Cipher Model are Equivalent. — 2008. — № 246. Архивировано 3 января 2019 года.
  15. ↑ Dachman-Soled, Dana; Katz, Jonathan; Thiruvengadam, Aishwarya (2016). "10-Round Feistel is Indifferentiable from an Ideal Cipher". EUROCRYPT 2016. Springer. pp. 649—678. doi:10.1007/978-3-662-49896-5_23.
  16. ↑ Dai, Yuanxi; Steinberger, John (2016). "Indifferentiability of 8-Round Feistel Networks". CRYPTO 2016. Springer.
  17. ↑ Современная Криптография, 2005, с. 576.
  18. ↑ 1 2 3 Современная Криптография, 2005, с. 577.

Литература

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

Ссылки