Случайный оракул
В криптографии случайный оракул — это оракул (теоретический черный ящик ), который отвечает на каждый уникальный запрос (действительно) случайным выбранным ответом, равномерно из его выходной области. Если запрос повторяется, он отвечает одинаково каждый раз, когда этот запрос отправляется.
Другими словами, случайный оракул — это математическая функция, выбранная равномерно случайным образом, то есть функция, отображающая каждый возможный запрос в (фиксированный) случайный ответ из ее выходной области.
Случайные оракулы впервые появились в контексте теории сложности, в которой они использовались для доказательства того, что разделение классов сложности может сталкиваться с барьерами релятивизации, причем наиболее ярким примером является проблема 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» могут использоваться для представления вызовов четырех отдельных случайных оракулов). Эту практику обычно называют разделением доменов . Клонирование Oracle — это повторное использование однажды созданного случайного оракула в рамках одного и того же доказательства (на практике это соответствует многократному использованию одного и того же криптографического хеша в одном алгоритме для разных целей). [ 7 ] Клонирование Oracle с неправильным разделением доменов нарушает доказательства безопасности и может привести к успешным атакам. [ 8 ]
Ограничения
[ редактировать ]Согласно тезису Чёрча-Тьюринга , ни одна функция, вычислимая конечным алгоритмом, не может реализовать истинно случайный оракул (который по определению требует бесконечного описания, поскольку имеет бесконечно много возможных входных данных, а все его выходные данные независимы друг от друга и должны быть индивидуально оговаривается любым описанием).
Фактически известны некоторые надуманные схемы подписи и шифрования, которые доказали свою безопасность в модели случайного оракула, но которые тривиально небезопасны, когда случайный оракул заменяется какой-либо реальной функцией. [ 9 ] [ 10 ] Тем не менее, для любого более естественного протокола доказательство безопасности в модели случайного оракула дает очень убедительное доказательство практической безопасности протокола. [ 11 ]
В общем, если безопасность протокола доказана, атаки на этот протокол должны либо выходить за рамки того, что было доказано, либо нарушать одно из предположений доказательства; например, если доказательство основано на сложности факторизации целых чисел , чтобы разрушить это предположение, необходимо найти быстрый алгоритм факторизации целых чисел. Вместо этого, чтобы разрушить предположение случайного оракула, необходимо обнаружить какое-то неизвестное и нежелательное свойство фактической хеш-функции; для хороших хэш-функций, где такие свойства считаются маловероятными, рассматриваемый протокол можно считать безопасным.
Гипотеза случайного оракула
[ редактировать ] | Возможно, этот раздел придется переписать, Википедии чтобы он соответствовал стандартам качества . ( февраль 2024 г. ) |
Хотя теорема Бейкера–Гилла–Соловея [ 12 ] показал, что существует оракул A такой, что P А = Н.П. А , последующая работа Беннета и Гилла, [ 13 ] показал, что для случайного оракула B (функция из {0,1} н в {0,1} так, что каждый входной элемент сопоставляется с каждым из 0 или 1 с вероятностью 1/2, независимо от отображения всех других входных данных), P Б ⊊ Э.Г. Б с вероятностью 1. Подобные разделения, а также тот факт, что случайные оракулы разделяют классы с вероятностью 0 или 1 (как следствие закона нуля–единицы Колмогорова ), привели к созданию гипотезы случайного оракула , согласно которой два «приемлемых» Классы сложности C 1 и C 2 равны тогда и только тогда, когда они равны (с вероятностью 1) под действием случайного оракула (приемлемость класса сложности определена в BG81). [ 13 ] ). Позже было показано, что эта гипотеза ложна, поскольку два приемлемых класса сложности IP и PSPACE оказались равными. [ 14 ] несмотря на IP А ⊊ ПРОСТРАНСТВО А для случайного оракула A с вероятностью 1. [ 15 ]
Идеальный шифр
[ редактировать ]Идеальный . шифр — это оракул случайной перестановки , который используется для моделирования идеализированного блочного шифра Случайная перестановка расшифровывает каждый блок зашифрованного текста в один и только один блок открытого текста и наоборот, поэтому существует взаимно однозначное соответствие . Некоторые криптографические доказательства делают не только «прямую» перестановку доступной для всех игроков, но и «обратную» перестановку.
Недавние работы показали, что идеальный шифр можно построить на основе случайного оракула, используя 10-раундовый алгоритм. [ 16 ] или даже 8-раундовый [ 17 ] Сети Фейстеля .
Идеальная перестановка
[ редактировать ]Идеальная перестановка — это идеализированный объект, который иногда используется в криптографии для моделирования поведения перестановки, выходные данные которой неотличимы от результатов случайной перестановки. В модели идеальной перестановки дополнительный доступ оракула предоставляется к идеальной перестановке и ее обратной. Идеальную модель перестановки можно рассматривать как частный случай идеальной модели шифрования, где доступ предоставляется только одной перестановке, а не семейству перестановок, как в случае идеальной модели шифрования.
Квантово-доступные случайные оракулы
[ редактировать ]Постквантовая криптография изучает квантовые атаки на классические криптографические схемы. Поскольку случайный оракул является абстракцией хэш-функции , имеет смысл предположить, что квантовый злоумышленник может получить доступ к случайному оракулу в квантовой суперпозиции . [ 18 ] Многие из классических доказательств безопасности не работают в рамках этой квантово-случайной модели оракула и нуждаются в пересмотре.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Беннетт, Чарльз; Гилл, Джон (1981). «Относительно случайного оракула A N^A != NP^A != coNP^A с вероятностью 1» . SIAM Journal on Computing : 96–113. дои : 10.1137/0210008 .
- ^ Jump up to: а б Белларе, Михир ; Рогауэй, Филипп (1993). «Случайные оракулы практичны: парадигма разработки эффективных протоколов» . Конференция ACM по компьютерной и коммуникационной безопасности : 62–73. дои : 10.1145/168588.168596 . S2CID 3047274 .
- ^ Кац, Джонатан; Линделл, Иегуда (2015). Введение в современную криптографию (2-е изд.). Бока-Ратон: Чепмен и Холл/CRC. стр. 174–175, 179–181. ISBN 978-1-4665-7027-6 .
- ^ Беннетт, Чарльз Х .; Гилл, Джон (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
- ^ Фиат, Амос; Шамир, Ади (1986). «Как проявить себя: практические решения проблем идентификации и подписи». КРИПТО . стр. 186–194.
- ^ Импальяццо, Рассел; Рудич, Стивен (1989). «Ограничения на доказуемые последствия односторонних перестановок». СТОК : 44–61.
- ^ Белларе, Дэвис и Гюнтер 2020 , с. 3.
- ^ Белларе, Дэвис и Гюнтер 2020 , с. 4.
- ^ Ран Канетти, Одед Голдрейх и Шай Халеви, Возвращение к методологии случайного оракула, STOC 1998, стр. 209–218 (PS и PDF) .
- ^ Крейг Джентри и Зульфикар Рамзан. «Устранение оракулы случайной перестановки в шифре четного Мансура» . 2004.
- ^ Коблиц, Нил; Менезес, Альфред Дж. (2015). «Модель случайного оракула: двадцатилетняя ретроспектива» (PDF) . Еще один взгляд . Архивировано из оригинала (PDF) 2 апреля 2015 года . Проверено 6 марта 2015 г.
- ^ Бейкер, Теодор; Гилл, Джон; Соловей, Роберт (1975). «Релятивизации вопроса P =? NP». СИАМ Дж. Компьютер . 4 (4). СИАМ: 431–442. дои : 10.1137/0204037 .
- ^ Jump up to: а б Беннетт, Чарльз; Гилл, Джон (1981). «Относительно случайного оракула A, P != NP != co-NP с вероятностью 1». СИАМ Дж. Компьютер . 10 (1). СИАМ: 96–113. дои : 10.1137/0210008 .
- ^ Шамир, Ади (октябрь 1992 г.). «IP = PSPACE» . Журнал АКМ . 39 (4): 869–877. дои : 10.1145/146585.146609 . S2CID 315182 .
- ^ Чанг, Ричард; Чор, Бенни ; Гольдрейх, Одед; Хартманис, Юрис; Хастад, Йохан; Ранджан, Деш; Рохатги, Панкадж (август 1994 г.). «Гипотеза случайного оракула ложна» . Журнал компьютерных и системных наук . 49 (1): 24–39. дои : 10.1016/S0022-0000(05)80084-4 . ISSN 0022-0000 .
- ^ Дахман-Солед, Дана; Кац, Джонатан; Тирувенгадам, Айшвария (2016). «10-раундовый Фейстель неотличим от идеального шифра». ЕВРОКРИПТ 2016 . Спрингер. стр. 649–678. дои : 10.1007/978-3-662-49896-5_23 .
- ^ Дай, Юаньси; Стейнбергер, Джон (2016). «Бездифференцируемость 8-раундовых сетей Фейстеля». КРИПТО 2016 . Спрингер.
- ^ Дэн Боне, Озгюр Дагделен, Марк Фишлин, Аня Леманн, Кристиан Шаффнер и Марк Жандри (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: несколько имен: список авторов ( ссылка )
Источники
[ редактировать ]- Белларе, Михир; Дэвис, Ханна; Гюнтер, Феликс (2020). «Разделяйте свои домены: NIST PQC KEM, клонирование Oracle и недифференцируемость только для чтения» . Достижения в криптологии – EUROCRYPT 2020 . Конспекты лекций по информатике. Том. 12106. Чам: Springer International Publishing. стр. 3–32. дои : 10.1007/978-3-030-45724-2_1 . hdl : 20.500.11850/392433 . ISBN 978-3-030-45723-5 . ISSN 0302-9743 . S2CID 214642193 .