# Как гомоморфное шифрование сделало неинтерактивные доказательства надежными?

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

---

В лекции MIT OpenCourseWare профессор Яэль Т. Калаи подробно разбирает одну из фундаментальных проблем современной теоретической криптографии — доказательство надежности парадигмы Фиата — Шамира в стандартной модели. Опираясь на прорывную работу 2019 года авторов Канетти, Ломбарди и Викса, исследователь демонстрирует, как с помощью полностью гомоморфного шифрования можно превратить интерактивные протоколы в неинтерактивные доказательства с нулевым разглашением. Этот подход устраняет давнее противоречие между теоретической безопасностью и практической реализацией криптографических схем.

## 🔄 От интерактивных протоколов к неинтерактивным аргументам
[[JUMP:2:13]]

Ранее криптографы разработали целый спектр интерактивных протоколов, таких как GKR (предназначенный для вычислений ограниченной глубины) или протокол Килиана — Микали. Последний позволял сжать длинный witness (свидетельство) для любого NP-языка до четырех сообщений, размер которых пропорционален параметру безопасности $\lambda$. Однако конечная цель исследователей — свести это взаимодействие к абсолютному минимуму: всего к одной реплике.

Для решения этой задачи используется парадигма Фиата — Шамира (Fiat-Shamir paradigm), суть которой заключается в замене проверяющего (верификатора) специальной хэш-функцией. Долгое время надежность этой схемы удавалось доказать только в модели случайного оракула (Random Oracle Model), где функция идеализирована. В реальном мире криптографам приходится заменять этот «оракул в небесах» конкретными вычислимыми схемами (цепями), что ставило открытый вопрос: остается ли протокол надежным в стандартной модели?

## 🎯 Задача о гамильтоновом цикле и проблема параллельного повторения
[[JUMP:6:56]]

В качестве базового примера профессор Калаи рассматривает трехсообщеночную систему доказательства для NP-полной задачи определения гамильтонова цикла в графе $G$. Протокол устроен следующим образом:

1. Доказывающий (prover) выбирает случайную перестановку $\pi$ вершин графа и отправляет верификатору обязательство (commitment) — запертый сейф, содержащий матрицу смежности переставленного графа $\pi(G)$ размером $n^2$.
2. Верификатор отправляет случайный бит вызова $b \in \{0, 1\}$.
3. Если $b=0$, доказывающий открывает только ребра гамильтонова цикла в $\pi(G)$. Если $b=1$, доказывающий раскрывает саму перестановку $\pi$ и открывает только не-ребра (нули матрицы), подтверждая соответствие исходному графу.

Этот протокол обладает свойством нулевого разглашения (Zero-Knowledge): при $b=0$ верификатор видит просто случайный цикл, а при $b=1$ — случайную перестановку и набор нулей, что не дает информации о самом цикле. 

Проблема заключается в том, что ошибка надежности (soundness error) здесь составляет $1/2$ — нечестный доказывающий может угадать бит вызова и обмануть верификатора. Для снижения ошибки до пренебрежимо малой протокол необходимо повторить параллельно $\lambda$ раз, каждый раз выбирая абсолютно новую перестановку $\pi$.

## ⚖️ Криптографический парадокс: нулевое разглашение против Фиата — Шамира
[[JUMP:15:47]]

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

Во-первых, параллельное повторение протокола (в отличие от последовательного) само по себе не гарантирует сохранение свойства нулевого разглашения в классическом смысле. 

Во-вторых, конечной целью является получение неинтерактивного доказательства с нулевым разглашением (NIZK). В неинтерактивной среде симулятор (механизм доказательства безопасности) наделяется дополнительной силой — возможностью выбирать строку общего доверия (Common Reference String, CRS). Изменение модели позволяет преодолеть теоретический запрет и построить надежную схему на базе решеток, что оставалось неразрешенной задачей многие годы до публикации работы Канетти, Ломбарди и Викса в 2019 году.

## 🔑 Первый шаг: шифрование с лазейкой в строке общего доверия
[[JUMP:21:51]]

Для построения надежной хэш-функции в парадигме Фиата — Шамира авторы предлагают проанализировать структуру обмана. Если утверждение ложно ($x \notin L$), то для любого первого сообщения $\alpha$ существует очень мало вызовов $\beta$, на которые доказывающий способен ответить. В рассматриваемом протоколе для каждого $\alpha$ существует ровно один «плохой» вызов $\beta_{bad}(\alpha)$, который позволяет злоумышленнику смухлевать. Задача хэш-функции — гарантированно уклониться от этого значения: 

$$h(\alpha) \neq \beta_{bad}(\alpha)$$

Идея вычислять $h(\alpha) = \beta_{bad}(\alpha) \oplus 1$ напрямую неосуществима, поскольку вычисление «плохого» вызова без знания секретов — это NP-трудная задача. Первая ключевая догадка (a-ha moment) авторов работы заключается в модификации схемы обязательств. 

Вместо обычного обязательства доказывающий использует схему шифрования с открытым ключом (PKE), побитово шифруя матрицу смежности графа. Открытый ключ генерируется доверенной стороной и помещается в CRS. Теперь у схемы появляется математическая лазейка (trapdoor) — секретный ключ шифрования, знание которого позволяет мгновенно расшифровать обязательство и вычислить $\beta_{bad}(\alpha)$.

## 🎭 Второй шаг: магия полностью гомоморфного шифрования
[[JUMP:48:33]]

Раскрывать секретную лазейку в составе хэш-функции нельзя, так как это полностью уничтожит конфиденциальность данных и свойство нулевого разглашения. Вместо использования тяжеловесных инструментов обфускации, Канетти, Ломбарди и Викс предложили поместить в ключ хэш-функции зашифрованную версию лазейки. Для этого привлекается полностью гомоморфное шифрование (Fully Homomorphic Encryption, FHE), позволяющее выполнять произвольные математические вычисления прямо над зашифрованными битами с помощью функции `eval`.

В реальной схеме ключ хэш-функции Фиата — Шамира содержит открытый ключ FHE и зашифрованную строку из одних нулей («пустую» схему размера $T$). Когда функция вычисляется от сообщения $\alpha$, она гомоморфно выполняет эту пустую операцию под покровом шифра. Секрет надежности раскрывается в теоретическом анализе безопасности (security analysis).

## 🧙‍♂️ Инвариант дешифрования и математическое противоречие
[[JUMP:1:16:41]]

В анализе безопасности криптографы используют гибридный аргумент (hybrid argument). В силу семантической слепоты шифра (semantic security), злоумышленник не способен отличить реальный ключ хэш-функции (где зашифрованы нули) от гибридного ключа, где зашифрована специальная схема $g^*$. Внутрь схемы $g^*$ жестко встраиваются (hardwired) как лазейка от обязательств, так и секретный ключ самого гомоморфного шифрования.

Логика схемы $g^*$ на входе $\alpha$ выглядит так:

1. Используя лазейку обязательства, она эффективно вычисляет уникальное плохое значение $\beta_{bad}(\alpha)$.
2. Полученную строку она гомоморфно расшифровывает с помощью встроенного секретного ключа FHE.
3. Результат инвертируется (XOR с единицей).

Магия доказательства заключается в следующем: если бы гипотетический эффективный взломщик смог подобрать такое сообщение $\alpha$, для которого выход гомоморфного вычисления совпал бы с плохим вызовом ($FHE.Eval(g^*, \alpha) = \beta_{bad}(\alpha)$), то применив дешифрование к обеим частям равенства, мы получили бы уравнение:

$$FHE.Dec(FHE.Eval(g^*, \alpha)) = FHE.Dec(\beta_{bad}(\alpha))$$

По определению гомоморфизма, левая часть раскрывается как работа самой схемы $g^*$ над аргументом $\alpha$, что дает:

$$FHE.Dec(\beta_{bad}(\alpha)) \oplus 1$$

В итоге возникает тождество:

$$FHE.Dec(\beta_{bad}(\alpha)) \oplus 1 = FHE.Dec(\beta_{bad}(\alpha))$$

Это математически невозможно, так как выражение $x \oplus 1 = x$ всегда ложно. Таким образом, в гибридной модели возможность обмана исключена информационно-теоретически. Из-за вычислительной неотличимости (требующей предположения о циклической безопасности FHE — circular security) эта надежность переносится и на реальный протокол.

## 🔮 Значение результатов и перспективы применения метода
[[JUMP:14:42]]

Описанный метод выходит далеко за рамки конкретной задачи о гамильтоновых циклах. Профессор Калаи подчеркивает, что данная техника гомоморфного уклонения от плохих вызовов применима к огромному классу интерактивных систем доказательств, включая протокол GKR и алгоритмы sum-check, где никаких обязательств изначально нет. Это открывает прямой путь к построению компактных неинтерактивных аргументов (SNARGs) на основе решеточных допущений (LWE).

В завершение лекции Калаи анонсирует выступление приглашенного автора Джайна Джина (Jain Jin), который представит развитие этой технологии для пакетных аргументов (batch arguments, BARGs) для всего класса NP. Полная картина семестра сложится на финальном занятии, где все изученные инструменты объединятся в единую лаконичную конструкцию.