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

• Определение случайного оракула

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

• Применение в криптографии

  • Используется для доказательства безопасности криптографических схем, где требуются строгие предположения о случайности. 
  • Доказательства в модели случайного оракула считаются лучшими, чем отсутствие формальных доказательств. 

• Разделение доменов и клонирование оракула

  • Разделение доменов позволяет рассматривать оракул как несколько отдельных оракулов. 
  • Клонирование оракула – это многократное использование одного и того же оракула в рамках доказательства. 

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

  • Ни одна функция, вычисляемая конечным алгоритмом, не может реализовать истинный случайный оракул. 
  • Гипотеза случайного оракула утверждает, что два “приемлемых” класса сложности равны тогда и только тогда, когда они равны случайному оракулу. 

• Идеальный шифр и идеальная перестановка

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

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

  • В постквантовой криптографии случайный оракул рассматривается как квантовый объект. 
  • Многие классические доказательства безопасности требуют пересмотра в этой модели.