Случайный оракул
-
Определение случайного оракула
- Случайный оракул — это математическая функция, выбирающая случайный ответ из заданной области.
- Он используется в теории сложности для доказательства разделения классов сложности.
-
Применение в криптографии
- Используется для доказательства безопасности криптографических схем, где требуются строгие предположения о случайности.
- Доказательства в модели случайного оракула считаются лучшими, чем отсутствие формальных доказательств.
-
Разделение доменов и клонирование оракула
- Разделение доменов позволяет рассматривать оракул как несколько отдельных оракулов.
- Клонирование оракула — это многократное использование одного и того же оракула в рамках доказательства.
-
Ограничения и гипотеза случайного оракула
- Ни одна функция, вычисляемая конечным алгоритмом, не может реализовать истинный случайный оракул.
- Гипотеза случайного оракула утверждает, что два «приемлемых» класса сложности равны тогда и только тогда, когда они равны случайному оракулу.
-
Идеальный шифр и идеальная перестановка
- Идеальный шифр — это оракул, который расшифровывает каждый блок зашифрованного текста в один блок открытого текста.
- Идеальная перестановка — это идеализированный объект, используемый для моделирования поведения перестановки.
-
Квантово-доступные случайные оракулы
- В постквантовой криптографии случайный оракул рассматривается как квантовый объект.
- Многие классические доказательства безопасности требуют пересмотра в этой модели.