stringtranslate.com

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

Ограничения

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

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

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

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

Хотя теорема Бейкера–Гилла–Соловея [12] показала, что существует оракул A такой, что PA = 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. дои : 10.1137/0210008 .
  2. ^ аб Белларе, Михир ; Рогауэй, Филипп (1993). «Случайные оракулы практичны: парадигма разработки эффективных протоколов». Конференция ACM по компьютерной и коммуникационной безопасности : 62–73. дои : 10.1145/168588.168596 . S2CID  3047274.
  3. ^ Кац, Джонатан; Линделл, Иегуда (2015). Введение в современную криптографию (2-е изд.). Бока-Ратон: Чепмен и Холл/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). «Как проявить себя: практические решения проблем идентификации и подписи». КРИПТО . стр. 186–194.
  6. ^ Импальяццо, Рассел; Рудич, Стивен (1989). «Ограничения на доказуемые последствия односторонних перестановок». СТОК : 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». СИАМ Дж. Компьютер . 4 (4). СИАМ: 431–442. дои : 10.1137/0204037.
  13. ^ аб Беннетт, Чарльз; Гилл, Джон (1981). «Относительно случайного оракула A, P != NP != co-NP с вероятностью 1». СИАМ Дж. Компьютер . 10 (1). СИАМ: 96–113. дои : 10.1137/0210008.
  14. ^ Шамир, Ади (октябрь 1992 г.). «IP = PSPACE». Журнал АКМ . 39 (4): 869–877. дои : 10.1145/146585.146609 . S2CID  315182.
  15. ^ Чанг, Ричард; Чор, Бенни ; Гольдрейх, Одед; Хартманис, Юрис; Хастад, Йохан; Ранджан, Деш; Рохатги, Панкадж (август 1994 г.). «Гипотеза случайного оракула ложна». Журнал компьютерных и системных наук . 49 (1): 24–39. дои : 10.1016/S0022-0000(05)80084-4 . ISSN  0022-0000.
  16. ^ Дахман-Солед, Дана; Кац, Джонатан; Тирувенгадам, Айшвария (2016). «10-раундовый Фейстель неотличим от идеального шифра». ЕВРОКРИПТ 2016 . Спрингер. стр. 649–678. дои : 10.1007/978-3-662-49896-5_23.
  17. ^ Дай, Юаньси; Стейнбергер, Джон (2016). «Бездифференцируемость 8-раундовых сетей Фейстеля». КРИПТО 2016 . Спрингер.
  18. ^ Дэн Бонех, Озгюр Дагделен, Марк Фишлин, Аня Леманн, Кристиан Шаффнер и Марк Жандри (2011). «Случайные оракулы в квантовом мире». Достижения в криптологии – ASIACRYPT 2011 . Конспекты лекций по информатике. Том. 7073. Спрингер. стр. 41–69. arXiv : 1008.0931 . дои : 10.1007/978-3-642-25385-0_3. ISBN 978-3-642-25384-3.{{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка )

Источники