Случайный оракул - Random oracle

Случайные ответы на случайные вопросы см. Интернет Oracle.

В криптография, а случайный оракул является оракул (теоретический черный ящик ), который реагирует на каждое уникальный запрос с (действительно) случайный выбранный ответ равномерно из его выходной области. Если запрос повторяется, он отвечает одинаково каждый раз при отправке этого запроса.

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

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

Приложения

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

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

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

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

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

Когда случайный оракул используется в доказательстве безопасности, он становится доступным для всех игроков, включая противника или противников. Один оракул может рассматриваться как несколько оракулов, предварительно добавляя фиксированную битовую строку в начало каждого запроса (например, запросы, отформатированные как «1 | x» или «0 | x», могут рассматриваться как вызовы двух отдельных случайных оракулы, аналогично «00 | x», «01 | x», «10 | x» и «11 | x» могут использоваться для представления вызовов четырем отдельным случайным оракулам).

Ограничения

Согласно Тезис Черча – Тьюринга, никакая функция, вычисляемая конечным алгоритмом, не может реализовать истинный случайный оракул (который по определению требует бесконечного описания, потому что он имеет бесконечно много возможных входов, а его выходы все независимы друг от друга и должны быть индивидуально определены любым описанием).

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

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

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

Хотя теорема Бейкера – Гилла – Соловея[9] показал, что существует такой оракул A, что PА = NPА, последующая работа Беннета и Гилла,[10] показал, что для случайный оракул B (функция из {0,1}п в {0,1}, так что каждый входной элемент отображается на каждый из 0 или 1 с вероятностью 1/2, независимо от отображения всех других входов), PB ⊊ НПB с вероятностью 1. Подобные разделения, а также тот факт, что случайные оракулы разделяют классы с вероятностью 0 или 1 (как следствие Закон нуля или единицы Колмогорова ), привела к созданию Гипотеза случайного оракула, что два «приемлемых» класса сложности C1 и C2 равны тогда и только тогда, когда они равны (с вероятностью 1) при случайном оракуле (приемлемость класса сложности определяется в BG81[10]). Позднее было показано, что эта гипотеза неверна, поскольку два приемлемых класса сложности IP и PSPACE оказались равными[11] несмотря на IPА ⊊ PSPACEА для случайного оракула A с вероятностью 1.[12]

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

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

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

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

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

Смотрите также

Рекомендации

  1. ^ а б Белларе, Михир; Рогавей, Филипп (1993). «Случайные оракулы практичны: парадигма для разработки эффективных протоколов». Конференция ACM по компьютерной и коммуникационной безопасности: 62–73.
  2. ^ Кац, Джонатан; Линделл, Иегуда (2015). Введение в современную криптографию (2-е изд.). Бока-Ратон: Чепмен и Холл / CRC. С. 174–175, 179–181. ISBN  978-1-4665-7027-6.
  3. ^ Беннет, Чарльз Х.; Джилл, Джон (1981), "Относительно случайного оракула A, P ^ A! = NP ^ A! = Co-NP ^ A с вероятностью 1", SIAM Журнал по вычислениям, 10 (1): 96–113, Дои:10.1137/0210008, ISSN  1095-7111
  4. ^ Фиат, Амос; Шамир, Ади (1986). «Как проявить себя: практические решения проблем идентификации и подписи». КРИПТО. С. 186–194.
  5. ^ Impagliazzo, Рассел; Рудич, Стивен (1989). "Пределы доказываемых последствий односторонних перестановок". STOC: 44–61.
  6. ^ Ран Канетти, Одед Голдрейх и Шай Халеви, Повторение методологии случайного оракула, STOC 1998, стр. 209–218 (PS и PDF).
  7. ^ Крейг Джентри и Зульфикар Рамзан. "Устранение оракулов случайной перестановки в шифре четного Мансура". 2004.
  8. ^ Коблиц, Нил; Менезеш, Альфред Дж. (2015). «Модель случайного оракула: 20-летняя ретроспектива» (PDF). Другой взгляд. Получено 6 марта 2015.
  9. ^ Бейкер, Теодор; Джилл, Джон; Соловей, Роберт (1975). "Релятивизации вопроса P =? NP". SIAM J. Comput. СИАМ. 4 (4): 431–442. Дои:10.1137/0204037.
  10. ^ а б Беннет, Чарльз; Гилл, Джон (1981). «Относительно случайного оракула A, P! = NP! = Co-NP с вероятностью 1». SIAM J. Comput. СИАМ. 10 (1): 96–113. Дои:10.1137/0210008.
  11. ^ Шамир, Ади (октябрь 1992 г.). "IP = PSPACE". Журнал ACM. 39 (4): 869–877. Дои:10.1145/146585.146609. S2CID  315182.
  12. ^ Чанг, Ричард; Одед Гольдрайх, Бенни Чор; Хартманис, Юрис; Хастад, Йохан; Ранджан, Деш; Рохатги, Панкадж (август 1994 г.). «Гипотеза случайного оракула неверна». Журнал компьютерных и системных наук. 49 (1): 24–39. Дои:10.1016 / S0022-0000 (05) 80084-4. ISSN  0022-0000.
  13. ^ Дахман-Солед, Дана; Кац, Джонатан; Тирувенгадам, Айшвария (2016). «10-раундовый Фейстел неотличим от идеального шифра». ЕВРОКРИПТ 2016. Springer. С. 649–678. Дои:10.1007/978-3-662-49896-5_23.
  14. ^ Дай, Юаньси; Штейнбергер, Джон (2016). «Не дифференцируемость 8-раундовых сетей Фейстеля». КРИПТО 2016. Springer.
  15. ^ Дэн Боне, Озгюр Дагделен, Марк Фишлин, Аня Леманн, Кристиан Шаффнер и Марк Жандри (2011). Случайные оракулы в квантовом мире. Springer. С. 41–69. arXiv:1008.0931. Дои:10.1007/978-3-642-25385-0_3.CS1 maint: несколько имен: список авторов (связь)