Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Приложения [ править ]

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

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

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

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

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

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

Ограничения [ править ]

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

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

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

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

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

Идеальный шифр [ править ]

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

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

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

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

См. Также [ править ]

  • Функция губки
  • Машина Oracle
  • Темы в криптографии

Ссылки [ править ]

  1. ^ a b Белларе, Михир ; Rogaway, Филипп (1993). «Случайные оракулы практичны: парадигма для разработки эффективных протоколов» . Конференция ACM по компьютерной и коммуникационной безопасности : 62–73.
  2. ^ Кац, Джонатан; Линделл, Иегуда (2015). Введение в современную криптографию (2-е изд.). Бока-Ратон: Chapman & Hall / CRC. С. 174–175, 179–181. ISBN 978-1-4665-7027-6.
  3. ^ Беннетт, Чарльз Х .; Джилл, Джон (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 
  4. ^ Fiat, Амос; Шамир, Ади (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. DOI : 10.1137 / 0204037 .
  10. ^ а б Беннет, Чарльз; Гилл, Джон (1981). «Относительно случайного оракула A, P! = NP! = Co-NP с вероятностью 1». SIAM J. Comput . СИАМ. 10 (1): 96–113. DOI : 10.1137 / 0210008 .
  11. Шамир, Ади (октябрь 1992 г.). «IP = PSPACE» . Журнал ACM . 39 (4): 869–877. DOI : 10.1145 / 146585.146609 . S2CID 315182 . 
  12. ^ Чанг, Ричард; Одед Гольдрайх, Бенни Чор; Хартманис, Юрис; Хастад, Йохан; Ранджан, Деш; Рохатги, Панкадж (август 1994 г.). «Гипотеза случайного оракула неверна» . Журнал компьютерных и системных наук . 49 (1): 24–39. DOI : 10.1016 / S0022-0000 (05) 80084-4 . ISSN 0022-0000 . 
  13. ^ Дахман-Солед, Дана; Кац, Джонатан; Тирувенгадам, Айшвария (2016). «10-раундовый Фейстел неотличим от идеального шифра». ЕВРОКРИПТ 2016 . Springer. С. 649–678. DOI : 10.1007 / 978-3-662-49896-5_23 .
  14. ^ Дай, Юаньси; Штейнбергер, Джон (2016). «Не дифференцируемость 8-раундовых сетей Фейстеля». КРИПТО 2016 . Springer.
  15. ^ Дэн Боне, Özgür Dağdelen, Марк Fischlin, Anja Lehmann, Кристиан Шафнер и Марк Zhandry (2011). Случайные оракулы в квантовом мире . Springer. С. 41–69. arXiv : 1008.0931 . DOI : 10.1007 / 978-3-642-25385-0_3 .CS1 maint: multiple names: authors list (link)