В лекции Гарвардского/MIT курса, опубликованной проектом MIT OpenCourseWare, подробно разбирается продвинутый криптографический аппарат, развивающий парадигму Фиата — Шамира (Fiat-Shamir paradigm). Профессор объясняет, как этот подход позволяет преобразовывать интерактивные протоколы в неинтерактивные доказательства с нулевым разглашением (NIZK). В центре внимания находится обобщение этой техники через концепцию корреляционной устойчивости (Correlation Intractability) и её применение к фундаментальным многораундовым протоколам, таким как Sum-check.
🔐 От Fiat-Shamir к неинтерактивному нулевому разглашению (NIZK) 0:12
Применение парадигмы Фиата — Шамира к интерактивным протоколам с параллельным повторением позволяет полностью устранить необходимость интерактивного взаимодействия между доказывающим (prover) и проверяющим (verifier). Вместо классического трехшагового обмена сообщениями формируется единое неинтерактивное доказательство.
В этой схеме верификатор больше не отправляет вызов индивидуально. Все участники могут самостоятельно вычислить его, используя общую хеш-функцию, привязанную к ключу хеширования (hash key). Полное неинтерактивное сообщение включает в себя элементы $\alpha$, $\beta$ и $\gamma$, которые отправляются доказывающим одновременно. При этом значение вызова $\beta$ жестко привязано к исходному графу $G$ и первому сообщению $\alpha$ через уравнение $\beta = H(G, \alpha)$. В результате полученный протокол обладает свойствами полноты (completeness) и обоснованности (soundness) при условии использования криптографически безопасной хеш-функции.
📝 Определение NIZK и сила общей случайной строки (CRS) 4:08
Переход к неинтерактивному формату меняет саму модель безопасности протоколов с нулевым разглашением. В интерактивной среде нулевое разглашение доказывается через симуляцию взгляда верификатора, однако в неинтерактивной схеме классическое определение требует корректировки из-за появления модели общей справочной строки (Common Reference String, CRS). В данном контексте CRS состоит из публичного ключа, используемого для обязательств, и ключа хеш-функции Фиата — Шамира.
Формальное определение неинтерактивного нулевого разглашения (NIZK) для языка $L$ формулируется следующим образом: для любого вероятностного полиномиального (PPT) верификатора существует PPT-симулятор, способный воссоздать всё, что верификатор узнает в реальном мире. В реальном мире верификатор наблюдает:
- Строку CRS, которая неявно включает в себя параметр безопасности.
- Само неинтерактивное доказательство $\pi$, сгенерированное честным доказывающим на основе CRS, утверждения $x \in L$ и секретного свидетельства (witness).
Для усиления безопасности обычно вводится требование устойчивости к вспомогательной информации (auxiliary input zero knowledge). Это гарантирует, что даже при наличии у верификатора или симулятора дополнительных данных $aux$, симулированное доказательство остаётся неотличимым от реального.
Возникает закономерный вопрос: почему существование симулятора не нарушает свойство обоснованности и не позволяет доказывать ложные утверждения? Профессор объясняет этот парадокс фундаментальным различием в правах участников: симулятор обладает эксклюзивной властью самостоятельно выбирать и программировать структуру CRS. Честный или атакующий доказывающий в реальном мире этой силой не наделены и обязаны работать с уже фиксированной строкой CRS. Именно эта асимметрия полномочий позволяет совместить строгую обоснованность Фиата — Шамира и свойства нулевого разглашения.
🛠️ Модификация хэш-функции и симуляция протокола 10:47
Построение работающего симулятора для схемы Фиата — Шамира — это сложная задача, поскольку симулятору приходится иметь дело с утверждениями $x$, о принадлежности которых к языку $L$ ему ничего не известно. Чтобы успешно симулировать доказательство для ложного утверждения, симулятору необходимо сгенерировать «плохой» вызов $\beta$, что в обычной ситуации заблокировано механизмами шифрования. Чтобы обойти это ограничение, профессор предлагает слегка модифицировать стандартную хеш-функцию Фиата — Шамира, добавив к её выходу случайную константу. Это изменение никак не влияет на обоснованность, но открывает возможности для симуляции.
Процесс симуляции транскрипта $(\alpha, \beta, \gamma)$ опирается на идею симулятора для честного верификатора (Honest Verifier Zero Knowledge, HVZK) и состоит из следующих шагов:
- Симулятор генерирует случайную последовательность вызовов $\beta = (b_1, b_2, \dots, b_\lambda)$.
- Зная заранее значения $\beta$, симулятор подстраивает под них первое сообщение $\alpha$. Если очередной бит $b_i = 0$, он создаёт обязательство для случайного гамильтонова цикла; если $b_i = 1$, он честно коммитит граф, зная, что его не попросят открыть запрещённые ребра. Это позволяет симулятору намеренно попадать в нужные («плохие») значения.
- На заключительном этапе симулятор программирует ключ хеширования в CRS. Новая хеш-функция определяется как исходная функция плюс фиксированная случайная строка $z \in {0, 1}^\lambda$. Чтобы выполнялось равенство $H(\alpha) = \beta$, симулятор просто вычисляет $z = \beta \oplus \text{eval}(HK, \alpha)$.
По словам профессора, такая симуляция обеспечивает вычислительное нулевое разглашение (computational zero knowledge). Она не является статистической, так как в сообщениях $\alpha$ содержится «мусор» вместо реальных данных. Обоснованность схемы также остаётся вычислительной, поскольку добавление случайного сдвига $z$ математически не меняет структуру доказательства противоречия при дешифровании.
🌐 Корреляционная устойчивость (Correlation Intractability) 27:32
Рассмотренная техника программирования ключей имеет гораздо более широкое значение для криптографии, выходящее за рамки конкретного интерактивного протокола. Профессор отмечает, что долгое время получение NIZK на основе допущения LWE (Learning With Errors) оставалось важной открытой проблемой. Данный метод позволяет элегантно обобщить результаты через призму концепции корреляционной устойчивости (Correlation Intractability).
Формально семейство хеш-функций называется корреляционно устойчивым относительно некоторого бинарного отношения $R \subseteq X \times Y$, если для любого полиномиального противника (adversary) крайне трудно подобрать такой вход $x$, чтобы пара входа и выхода хеш-функции попала в это отношение. Противник получает случайно сгенерированный ключ хеш-функции $HK$, и его цель — выдать $x$, для которого $(x, \text{Eval}(HK, x)) \in R$. Вероятность успеха такого противника должна быть пренебрежимо малой (negligible).
Чтобы концепция имела смысл, отношение $R$ должно обладать свойством разреженности (sparse) или ускользаемости (evasive). Это означает, что для любого фиксированного $x$ вероятность того, что случайный $y$ удовлетворяет отношению $(x, y) \in R$, ничтожно мала. В контексте парадигмы Фиата — Шамира отношение $R$ связывает первое сообщение $\alpha$ с «плохими» вызовами $\beta$, для которых у фальшивого доказывающего существует принимаемый верификатором ответ $\gamma$. Корреляционная устойчивость гарантирует, что атакующий не сможет найти такое сообщение $\alpha$, которое захешируется в выигрышный для него «плохой» вызов $\beta$.
🔍 Теорема Канетти-Ломбарди-Ви (CLW) и поиск за полиномиальное время 39:19
Исторически концепция корреляционной устойчивости была предложена ещё в районе 2004 года, однако исследователи долгое время не могли продвинуться дальше доказательства её существования в модели случайного оракула (Random Oracle Model). Прорыв произошёл благодаря работе исследователей Канетти, Ломбарди и Ви (Canetti-Lombardi-Wee, CLW). Они доказали, что корреляционно устойчивые хеш-функции в стандартной модели существуют для любого отношения, допускающего эффективный поиск за полиномиальное время $t$ (searchable in time $t$).
Свойство «поисковости» (searchability) накладывает два условия на отношение $R$:
- Для каждого входа $\alpha$ существует не более одного (уникального) значения $\beta$, переводящего пару в разряд «плохих».
- Функция $f(\alpha) = \beta$, находящая этот уникальный плохой вызов, гарантированно вычисляется за строго ограниченное полиномиальное время $t$.
Профессор указывает на важнейший нюанс теоремы CLW, связанный с порядком кванторов. Построить отдельную хеш-функцию под одно конкретное отношение легко — достаточно взять алгоритм поиска плохого ответа и прибавить к нему единицу: $H(\alpha) = f(\alpha) + 1$. Однако достижение Канетти, Ломбарди и Ви заключается в доказательстве существования единого универсального семейства хеш-функций, которое остаётся корреляционно устойчивым для всех отношений, вычисляемых за время $t$.
В основе этой конструкции лежит полностью гомоморфное шифрование (Fully Homomorphic Encryption, FHE) и предположение о циклической безопасности (circular security). Генерация ключей создает публичный ключ FHE и шифрует строку из нулей. Функция вычисления гомоморфно выполняет универсальную схему над входом.
В анализе безопасности, если бы противник мог взломать схему, криптографы могли бы заменить ключ хеширования на альтернативный ($HK^$), содержащий зашифрованную «фальшивую» схему $g^$ с зашитым секретным ключом. Эта схема $g^*$ на лету расшифровывала бы функцию $f(\alpha)$, инвертировала один бит результата и выдавала значение, математически исключающее равенство $H(\alpha) = f(\alpha)$. Благодаря семантической безопасности шифрования противник не способен отличить реальный ключ от фальшивого, что переводит доказательство в область статистической невозможности обмана.
🧮 Применение к протоколу Sum-check и множественные плохие вызовы 45:25
Универсальность подхода CLW позволяет применять его к сложным многораундовым интерактивным протоколам, таким как Sum-check или интерактивные доказательства Голдвассер — Калаи — Ротблюма (GKR). На примере первого раунда Sum-check профессор демонстрирует, как доказывающий, заявляя ложное значение суммы многочлена $v$, вынужден предоставлять искажённый одновариантный полином $g_1^*$, поскольку истинный полином не даёт в сумме нужного значения. «Плохими» вызовами $\beta$ здесь становятся точки поля $t$, в которых искажённый полином совпадает с истинным.
Однако в таких сценариях возникает математическое усложнение: плохой вызов больше не является строго уникальным. Число опасных точек ограничено степенью полинома $d$. Профессор объясняет, что архитектура доказательства легко расширяется на случай $d$ плохих вызовов через механизм вероятностного угадывания (guessing).
Анализ безопасности в этом случае включает следующие аспекты:
- В процессе редукции симулятор наугад выбирает один из $d$ возможных плохих ответов, с которыми доказывающий может попытаться смухлевать.
- Вероятность успешного угадывания составляет $1/d$, что пропорционально снижает (деградирует) изначальное допущение безопасности.
- Применяя оценку объединения (union bound), криптографы доказывают, что общая вероятность обмана со стороны доказывающего составляет $d \times \text{negligible}$. До тех пор, пока величина $d$ остаётся полиномиальной, итоговая вероятность остаётся пренебрежимо малой, гарантируя общую надёжность системы.
Главная сложность реального применения к Sum-check заключается в том, что в последующих раундах новые плохие точки начинают зависеть от вызовов верификатора из предыдущих этапов, что не позволяет зашить их в систему заранее. Тем не менее, надстраивая над методом CLW дополнительные криптографические приёмы, учёные успешно создают неинтерактивные аргументы. Профессор завершает лекцию анонсом выступления исследователя Чжэнчжуна Цзиня (Zhengzhong Jin), который на следующем занятии представит развитие этой технологии для пакетных неинтерактивных аргументов (batch non-interactive arguments).
