stringtranslate.com

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

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

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

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

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

Приложения

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

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

Случайные оракулы давно рассматривались в теории сложности вычислений [ 4], и многие схемы были признаны безопасными в модели случайных оракулов, например, Optimal Asymmetric Encryption Padding , RSA-FDH и PSS . В 1986 году Амос Фиат и Ади Шамир [5] показали важное применение случайных оракулов — удаление взаимодействия из протоколов для создания подписей.

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

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

Когда в доказательстве безопасности используется случайный оракул, он становится доступен всем игрокам, включая противника или противников.

Разделение доменов

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

Ограничения

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

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

Источники