# Яэль Калаи: «Парадигма Фиата — Шамира — это не доказательство»

Источник: https://www.youtube.com/watch?v=zEf_dECRUjY
Канал: MIT OpenCourseWare
Опубликовано: 29.01.2025

---

## Парадигма Фиата — Шамира и доказательства с нулевым разглашением: Часть 2
[[JUMP:0:00]]

Лекция посвящена критическому анализу применения парадигмы Фиата — Шамира к протоколам с нулевым разглашением. Ведущая Яэль Калаи (Yael Kalai) исследует условия, при которых эта парадигма обеспечивает надежность (soundness) доказательств, и разбирает парадоксальную связь между интерактивными протоколами, их безопасностью и свойством нулевого разглашения.

### 🛡 Проблема надежности в модели случайного оракула
[[JUMP:0:55]]

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

*   **Уязвимость:** Если протокол обладает не пренебрежимо малой вероятностью ошибки (soundness error), злоумышленник (prover) может многократно обращаться к оракулу, пока не получит нужный результат, что позволяет обмануть систему.
*   **Контраргумент:** Даже если вероятность ошибки протокола пренебрежимо мала, «наивное» применение парадигмы Фиата — Шамира всё равно может быть уязвимо.
*   **Пример:** Калаи демонстрирует, как злоумышленник может использовать оракул для «подгонки» транскрипта доказательства, последовательно расширяя его до тех пор, пока каждый этап не будет принят верификатором.

### 📜 Теорема о надежности
[[JUMP:10:11]]

Для обеспечения надежности в модели случайного оракула протокол должен удовлетворять определенным требованиям.

*   **Условия:** Парадигма Фиата — Шамира надежна, если протокол имеет константное число раундов и пренебрежимо малую вероятность ошибки.
*   **Исключения:** Существуют протоколы с большим числом раундов (например, GKR), которые также могут быть защищены, если они обладают так называемой «пораундовой надежностью» (round-by-round soundness).

### ⚔️ Атака на протокол и доказательство от противного
[[JUMP:13:45]]

Калаи подробно разбирает доказательство надежности для протоколов с тремя сообщениями. Основная идея заключается в сведении безопасности к невозможности совершить атаку в исходном интерактивном протоколе.

1.  **Предположение:** Существует полиномиально ограниченный злоумышленник $P^*$, который может успешно «обмануть» систему в модели случайного оракула с вероятностью $\epsilon$.
2.  **Симуляция:** Калаи показывает, что можно сконструировать такого злоумышленника $P^{**}$ для интерактивного протокола, который будет использовать $P^*$ как подпрограмму.
3.  **Вероятностная потеря:** В процессе симуляции оракула происходит потеря вероятности, связанная с необходимостью угадать, на каком именно запросе $P^*$ сгенерирует «успешный» ответ. По мнению Калаи, эта вероятность составляет примерно $\epsilon / q$, где $q$ — количество запросов.
4.  **Вывод:** Поскольку $q$ является полиномом, а $\epsilon$ — не пренебрежимо малой величиной, $\epsilon / q$ также остается значимой величиной, что приводит к противоречию с безопасностью исходного протокола.

### 🏛 Стандартная модель vs Модель случайного оракула
[[JUMP:45:00]]

Дискуссия затрагивает вопрос о том, что именно считается «доказательством» безопасности.

*   **Статус модели:** Калаи подчеркивает, что модель случайного оракула — это лишь «проверка на здравый смысл» (sanity check).
*   **Реальные угрозы:** Хотя криптографические протоколы подвергаются атакам, чаще всего уязвимости кроются в реализации и генерации случайных чисел, а не в самой математике криптографии.
*   **Секретные знания:** Отвечая на вопрос о потенциальном превосходстве спецслужб (таких как АНБ), Калаи отмечает: вполне вероятно, что они обладают глубокими знаниями, которые еще не стали достоянием публичной науки, приводя в пример историю изобретения алгоритма RSA.

### 🧩 Парадокс: Надежность против нулевого разглашения
[[JUMP:53:43]]

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

*   **Причина:** Нулевое разглашение требует возможности симуляции транскрипта. Однако, если злоумышленник-верификатор использует хэширование по Фиату — Шамиру, симулятор оказывается неспособен «обмануть» такого верификатора, не нарушив тем самым надежность протокола.
*   **Вывод:** Любой интерактивный протокол, для которого парадигма Фиата — Шамира обеспечивает надежность, не может быть протоколом с нулевым разглашением (в указанном контексте).