Парадигма Фиата — Шамира и доказательства с нулевым разглашением: Часть 2 0:00
Лекция посвящена критическому анализу применения парадигмы Фиата — Шамира к протоколам с нулевым разглашением. Ведущая Яэль Калаи (Yael Kalai) исследует условия, при которых эта парадигма обеспечивает надежность (soundness) доказательств, и разбирает парадоксальную связь между интерактивными протоколами, их безопасностью и свойством нулевого разглашения.
🛡 Проблема надежности в модели случайного оракула 0:55
Ключевой вопрос заключается в том, сохраняется ли надежность протокола при замене верификатора на хэш-функцию, моделируемую как случайный оракул. Как отмечает Калаи, простое применение этой модели не гарантирует автоматическую защиту.
- Уязвимость: Если протокол обладает не пренебрежимо малой вероятностью ошибки (soundness error), злоумышленник (prover) может многократно обращаться к оракулу, пока не получит нужный результат, что позволяет обмануть систему.
- Контраргумент: Даже если вероятность ошибки протокола пренебрежимо мала, «наивное» применение парадигмы Фиата — Шамира всё равно может быть уязвимо.
- Пример: Калаи демонстрирует, как злоумышленник может использовать оракул для «подгонки» транскрипта доказательства, последовательно расширяя его до тех пор, пока каждый этап не будет принят верификатором.
📜 Теорема о надежности 10:11
Для обеспечения надежности в модели случайного оракула протокол должен удовлетворять определенным требованиям.
- Условия: Парадигма Фиата — Шамира надежна, если протокол имеет константное число раундов и пренебрежимо малую вероятность ошибки.
- Исключения: Существуют протоколы с большим числом раундов (например, GKR), которые также могут быть защищены, если они обладают так называемой «пораундовой надежностью» (round-by-round soundness).
⚔️ Атака на протокол и доказательство от противного 13:45
Калаи подробно разбирает доказательство надежности для протоколов с тремя сообщениями. Основная идея заключается в сведении безопасности к невозможности совершить атаку в исходном интерактивном протоколе.
- Предположение: Существует полиномиально ограниченный злоумышленник $P^*$, который может успешно «обмануть» систему в модели случайного оракула с вероятностью $\epsilon$.
- Симуляция: Калаи показывает, что можно сконструировать такого злоумышленника $P^{*}$ для интерактивного протокола, который будет использовать $P^$ как подпрограмму.
- Вероятностная потеря: В процессе симуляции оракула происходит потеря вероятности, связанная с необходимостью угадать, на каком именно запросе $P^*$ сгенерирует «успешный» ответ. По мнению Калаи, эта вероятность составляет примерно $\epsilon / q$, где $q$ — количество запросов.
- Вывод: Поскольку $q$ является полиномом, а $\epsilon$ — не пренебрежимо малой величиной, $\epsilon / q$ также остается значимой величиной, что приводит к противоречию с безопасностью исходного протокола.
🏛 Стандартная модель vs Модель случайного оракула 45:00
Дискуссия затрагивает вопрос о том, что именно считается «доказательством» безопасности.
- Статус модели: Калаи подчеркивает, что модель случайного оракула — это лишь «проверка на здравый смысл» (sanity check).
- Реальные угрозы: Хотя криптографические протоколы подвергаются атакам, чаще всего уязвимости кроются в реализации и генерации случайных чисел, а не в самой математике криптографии.
- Секретные знания: Отвечая на вопрос о потенциальном превосходстве спецслужб (таких как АНБ), Калаи отмечает: вполне вероятно, что они обладают глубокими знаниями, которые еще не стали достоянием публичной науки, приводя в пример историю изобретения алгоритма RSA.
🧩 Парадокс: Надежность против нулевого разглашения 53:43
В финале лекции обсуждается неожиданный результат: существуют протоколы, которые становятся надежными после применения Фиата — Шамира, но при этом перестают обладать свойством нулевого разглашения при параллельном повторении.
- Причина: Нулевое разглашение требует возможности симуляции транскрипта. Однако, если злоумышленник-верификатор использует хэширование по Фиату — Шамиру, симулятор оказывается неспособен «обмануть» такого верификатора, не нарушив тем самым надежность протокола.
- Вывод: Любой интерактивный протокол, для которого парадигма Фиата — Шамира обеспечивает надежность, не может быть протоколом с нулевым разглашением (в указанном контексте).
