Случайные оракулы в криптографии и теории сложности

Введение

случайные ответы на случайные вопросы

В криптографии случайный оракул — это оракул (теоретический «черный ящик»), который отвечает на каждый уникальный запрос истинно случайным ответом, выбранным равномерно из области его значений. При повторном запросе он всегда выдает один и тот же ответ. Иными словами, случайный оракул — это математическая функция, выбранная случайным образом, то есть функция, сопоставляющая каждому возможному запросу фиксированный случайный ответ из области его значений. Случайные оракулы впервые появились в контексте теории сложности, где использовались для аргументации о том, что разделение классов сложности может столкнуться с барьерами релятивизации, наиболее известным примером является проблема P vs NP, два класса, показанные в 1981 году, почти наверняка различные относительно случайного оракула. Они вошли в криптографию благодаря публикации Михира Белларе и Филиппа Рогавея в 1993 году, которая представила их как формальную криптографическую модель для использования в доказательствах сведения. Обычно они используются, когда доказательство невозможно провести, опираясь на более слабые предположения о криптографической хеш-функции. Система, безопасность которой доказана при замене каждой хеш-функции на случайный оракул, считается безопасной в модели случайного оракула, в отличие от безопасности в стандартной модели криптографии.

Приложения

Случайные оракулы обычно используются в качестве идеализированной замены криптографических хеш-функций в схемах, где требуются строгие предположения о случайности выходных данных хеш-функции. Такое доказательство часто показывает, что система или протокол безопасны, демонстрируя, что злоумышленнику потребуется добиться невозможного поведения от оракула или решить сложную математическую задачу, чтобы их взломать. Однако оно доказывает эти свойства только в модели случайного оракула, удостоверяясь в отсутствии серьезных дефектов в конструкции. В общем случае, такое доказательство не подразумевает тех же свойств в стандартной модели. Тем не менее, доказательство в модели случайного оракула считается лучше, чем отсутствие какого-либо формального доказательства безопасности. Не все применения криптографических хеш-функций требуют случайных оракулов: схемы, требующие лишь одного или нескольких свойств, имеющих определение в стандартной модели (таких как устойчивость к коллизиям, стойкость к прообразам, стойкость ко второму прообразу и т.д.), часто могут быть доказаны безопасными в стандартной модели (например, криптосистема Крэмера — Шупа). Случайные оракулы давно изучаются в теории вычислительной сложности, и безопасность многих схем доказана в модели случайного оракула, например, Optimal Asymmetric Encryption Padding, RSA FDH и схема вероятностной подписи. В 1986 году Амос Фиат и Ади Шамир показали важное применение случайных оракулов — устранение интерактивности из протоколов создания подписей. В 1989 году Рассел Импаглиаццо и Стивен Рудич показали ограничение случайных оракулов, а именно, что одного лишь их существования недостаточно для обмена секретными ключами. В 1993 году Михир Белларе и Филипп Рогавей. Тем не менее, для любого более естественного протокола доказательство безопасности в модели случайного оракула предоставляет очень веские доказательства практической безопасности протокола. В общем случае, если безопасность протокола доказана, то атаки на этот протокол должны либо выходить за рамки доказанного, либо нарушать одно из предположений в доказательстве; например, если доказательство опирается на сложность целочисленной факторизации, для нарушения этого предположения необходимо открыть быстрый алгоритм факторизации целых чисел. Вместо этого, чтобы взломать предположение о случайном оракуле, необходимо обнаружить какое-либо неизвестное и нежелательное свойство фактической хеш-функции; для хороших хеш-функций, где такие свойства считаются маловероятными, рассматриваемый протокол можно считать безопасным.

Random oracles are typically used as an idealised replacement for cryptographic hash functions in schemes where strong randomness assumptions are needed of the hash function's output. Such a proof often shows that a system or a protocol is secure by showing that an attacker must require impossible behavior from the oracle, or solve some mathematical problem believed hard in order to break it. However, it only proves such properties in the random oracle model, making sure no major design flaws are present. It is in general not true that such a proof implies the same properties in the standard model. Still, a proof in the random oracle model is considered better than no formal security proof at all. Not all uses of cryptographic hash functions require random oracles: schemes that require only one or more properties having a definition in the standard model (such as collision resistance, preimage resistance, second preimage resistance, etc.) can often be proven secure in the standard model (e. g., the Cramer–Shoup cryptosystem). Random oracles have long been considered in computational complexity theory, and many schemes have been proven secure in the random oracle model, for example Optimal Asymmetric Encryption Padding, RSA FDH and Probabilistic Signature Scheme. In 1986, Amos Fiat and Adi Shamir showed a major application of random oracles – the removal of interaction from protocols for the creation of signatures. In 1989, Russell Impagliazzo and Steven Rudich showed the limitation of random oracles – namely that their existence alone is not sufficient for secret key exchange. In 1993, Mihir Bellare and Phillip Rogaway Nonetheless, for any more natural protocol a proof of security in the random oracle model gives very strong evidence of the practical security of the protocol. In general, if a protocol is proven secure, attacks to that protocol must either be outside what was proven, or break one of the assumptions in the proof; for instance if the proof relies on the hardness of integer factorization, to break this assumption one must discover a fast integer factorization algorithm. Instead, to break the random oracle assumption, one must discover some unknown and undesirable property of the actual hash function; for good hash functions where such properties are believed unlikely, the considered protocol can be considered secure.

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

Хотя теорема Бейкера — Гилла — Соловея показала, что существует оракул A, такой что PA = NPA, последующая работа Беннетта и Гилла показала, что для случайного оракула B (функция из {0,1}ⁿ в {0,1}, такая, что каждый входной элемент отображается в 0 или 1 с вероятностью 1/2, независимо от отображения всех остальных входов), PB ⊂ NPB с вероятностью 1. Подобные разделения, а также тот факт, что случайные оракулы разделяют классы с вероятностью 0 или 1 (как следствие закона Колмогорова о нуле и единице), привели к формулированию гипотезы случайного оракула, согласно которой два "допустимых" класса сложности C1 и C2 равны тогда и только тогда, когда они равны (с вероятностью 1) при случайном оракуле (допустимость класса сложности определена в BG81, несмотря на то, что IPA ⊂ PSPACEA для случайного оракула A с вероятностью 1.

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

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

Идеальная перестановка

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

Квантово-доступные случайные оракулы

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