Случайный оракул - Random oracle
В криптографии , случайный оракул является оракул (теоретический черным ящик ) , который отвечает на каждый уникальный запрос с (истинно) случайной реакцией выбранной равномерно от его выходной области. Если запрос повторяется, он отвечает одинаково каждый раз при отправке этого запроса.
Другими словами, случайный оракул - это математическая функция, выбираемая равномерно случайным образом, то есть функция, отображающая каждый возможный запрос в (фиксированный) случайный ответ из его выходной области.
Случайные оракулы как математическая абстракция были впервые использованы в строгих криптографических доказательствах в публикации 1993 года Михира Белларе и Филиппа Рогавея (1993). Обычно они используются, когда доказательство не может быть выполнено с использованием более слабых предположений о криптографической хеш-функции . Система, которая доказала свою безопасность, когда каждая хеш-функция заменена случайным оракулом, описывается как безопасная в модели случайного оракула , в отличие от безопасной в стандартной модели криптографии .
Приложения
Случайные оракулы обычно используются в качестве идеализированной замены криптографических хеш-функций в схемах, где требуются строгие предположения о случайности выходных данных хеш-функции. Такое доказательство часто показывает, что система или протокол безопасны, показывая, что злоумышленник должен потребовать от оракула невозможного поведения или решить некоторую математическую задачу, которая считается трудной , чтобы ее взломать. Однако он только подтверждает такие свойства в случайной модели оракула, гарантируя отсутствие серьезных недостатков конструкции. Вообще говоря, неверно, что такое доказательство подразумевает те же свойства в стандартной модели. Тем не менее, доказательство в модели случайного оракула считается лучше, чем полное отсутствие формального доказательства безопасности.
Не все виды использования криптографических хэш - функции требуют случайных оракулов: схемы , которые требуют только одного или нескольких свойств , имеющих определение в стандартной модели (например, сопротивление столкновения , прообраза сопротивления , второй сопротивления прообраза и т.д.) часто может быть доказано безопасным в стандарте модель (например, криптосистема Крамера – Шупа ).
Случайные оракулы уже давно рассматриваются в теории сложности вычислений , и многие схемы доказали свою безопасность в модели случайных оракулов, например оптимальное асимметричное шифрование , RSA-FDH и схема вероятностной подписи . В 1986 году Амос Фиат и Ади Шамир продемонстрировали главное применение случайных оракулов - удаление взаимодействия из протоколов для создания подписей.
В 1989 году Рассел Импальяццо и Стивен Рудич показали ограниченность случайных оракулов, а именно, что одного их существования недостаточно для обмена секретными ключами.
В 1993 году Михир Белларе и Филипп Рогавей первыми выступили за их использование в криптографических конструкциях. По их определению, случайный оракул создает битовую строку бесконечной длины, которую можно усечь до желаемой длины.
Когда случайный оракул используется в доказательстве безопасности, он становится доступным для всех игроков, включая противника или противников. Один оракул можно рассматривать как несколько оракулов, предварительно добавляя фиксированную строку битов в начало каждого запроса (например, запросы, отформатированные как «1 | x» или «0 | x», могут рассматриваться как вызовы двух отдельных случайных оракулы, аналогично «00 | x», «01 | x», «10 | x» и «11 | x» могут использоваться для представления вызовов четырем отдельным случайным оракулам).
Ограничения
Согласно тезису Чёрча-Тьюринга , никакая функция, вычисляемая с помощью конечного алгоритма, не может реализовать истинный случайный оракул (который по определению требует бесконечного описания, потому что он имеет бесконечно много возможных входов, а его выходы независимы друг от друга и должны быть индивидуально уточняется любым описанием).
Фактически, известны определенные схемы искусственной подписи и шифрования, которые доказали свою безопасность в модели случайного оракула, но которые тривиально небезопасны, когда любая реальная функция заменяется случайным оракулом. Тем не менее, для любого более естественного протокола доказательство безопасности в модели случайного оракула дает очень веские доказательства практической безопасности протокола.
В общем, если протокол доказал свою безопасность, атаки на этот протокол должны либо выходить за рамки того, что было доказано, либо нарушать одно из допущений в доказательстве; например, если доказательство опирается на твердость целочисленной факторизации , чтобы опровергнуть это предположение, необходимо открыть алгоритм быстрой целочисленной факторизации. Вместо этого, чтобы разрушить предположение о случайном оракуле, нужно обнаружить какое-то неизвестное и нежелательное свойство фактической хеш-функции; для хороших хэш-функций, где такие свойства маловероятны, рассматриваемый протокол можно считать безопасным.
Гипотеза случайного оракула
Хотя теорема Бейкера – Гилла – Соловея показала, что существует такой оракул A, что P A = NP A , последующая работа Беннета и Гилла показала, что для случайного оракула B (функция от {0,1} n до {0 , 1} таким образом, что каждый входной элемент отображается на каждый из 0 или 1 с вероятностью 1/2, независимо от отображения всех других входов), P B ⊊ NP B с вероятностью 1. Подобные разделения, а также тот факт, что случайные оракулы разделяют классы с вероятностью 0 или 1 (как следствие закона нуля или единицы Колмогорова ), что привело к созданию гипотезы случайного оракула , согласно которой два «приемлемых» класса сложности C 1 и C 2 равны тогда и только тогда, когда они равны (с вероятностью 1) при случайном оракуле (приемлемость класса сложности определена в BG81). Позднее было показано, что эта гипотеза неверна, поскольку два приемлемых класса сложности IP и PSPACE оказались равными, несмотря на то, что IP A ⊊ PSPACE A для случайного оракула A с вероятностью 1.
Идеальный шифр
Идеальный шифр является случайной перестановкой оракулом , который используется для моделирования идеализированную блочного шифра. Случайная перестановка расшифровывает каждый блок зашифрованного текста в один и только один блок открытого текста и наоборот, поэтому существует взаимно однозначное соответствие . Некоторые криптографические доказательства делают не только «прямую» перестановку доступной для всех игроков, но и «обратную» перестановку.
Недавние работы показали, что идеальный шифр можно построить из случайного оракула, используя 10-раундовые или даже 8-раундовые сети Фейстеля .
Квантово-доступные случайные оракулы
Постквантовая криптография изучает квантовые атаки на классические криптографические схемы. Поскольку случайный оракул - это абстракция хеш-функции , имеет смысл предположить, что квантовый злоумышленник может получить доступ к случайному оракулу в квантовой суперпозиции . Многие из классических доказательств безопасности не работают в этой квантовой случайной модели оракула и нуждаются в пересмотре.