Случайный оракул (Vlrcgwudw kjgtrl)
В криптографии случайным оракулом называется идеализированная хеш-функция, которая на каждый новый запрос выдает случайный ответ, равномерно распределённый по области значений, с условием: если один и тот же запрос поступит дважды, то ответ должен быть одинаковым. Другими словами, случайный оракул — это математическая функция, выбранная случайным образом, которая отображает каждый возможный запрос в фиксированный случайный ответ из заранее заготовленной области ответов.
Случайные оракулы как математическая абстракция были впервые использованы в строгих криптографических доказательствах в публикации 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 2 Современная Криптография, 2005, с. 351.
- ↑ Современная Криптография, 2005, с. 578—585.
- ↑ RSA-FDH (Full Domain Hash). www.iacr.org. Дата обращения: 23 декабря 2018. Архивировано 5 июня 2019 года.
- ↑ Fiat, Amos; Shamir, Adi (1986). "How to Prove Yourself: Practical Solutions to Identification and Signature Problems". CRYPTO. pp. 186—194.
- ↑ Impagliazzo, Russell; Rudich, Steven. Limits on the Provable Consequences of One-Way Permutations (англ.) // STOC[англ.] : journal. — 1989. — P. 44—61.
- ↑ 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 года.
- ↑ Современная Криптография, 2005, с. 559—560.
- ↑ Ran Canetti, Oded Goldreich and Shai Halevi, The Random Oracle Methodology Revisited, STOC 1998, pp. 209—218 (PS and PDF).
- ↑ Koblitz, Neal; Menezes, Alfred J. The Random Oracle Model: A Twenty-Year Retrospective (англ.) // Another Look : journal. — 2015. Архивировано 2 апреля 2015 года.
- ↑ Craig Gentry and Zulfikar Ramzan. «Eliminating Random Permutation Oracles in the Even-Mansour Cipher» Архивная копия от 10 августа 2017 на Wayback Machine. 2004.
- ↑ Теорема Бейкера — Гилла — Соловэя — Викиконспекты. neerc.ifmo.ru. Дата обращения: 14 декабря 2018. Архивировано 28 января 2023 года.
- ↑ 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.
- ↑ 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.
- ↑ Jean-Sebastien Coron, Jacques Patarin, Yannick Seurin. The Random Oracle Model and the Ideal Cipher Model are Equivalent. — 2008. — № 246. Архивировано 3 января 2019 года.
- ↑ 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.
- ↑ Dai, Yuanxi; Steinberger, John (2016). "Indifferentiability of 8-Round Feistel Networks". CRYPTO 2016. Springer.
- ↑ Современная Криптография, 2005, с. 576.
- ↑ 1 2 3 Современная Криптография, 2005, с. 577.
Литература
[править | править код]- Венбо Мао. Современная криптография: теория и практика. — Москва: Издательский дом «Вильямс», 2005. — 768 с. — ISBN 5-8459-0847-7.