# Протокол Килиана — Микали: Сжатие PCP с помощью хеш-функций

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

---

В лекции профессора Яэль Калай из Массачусетского технологического института (MIT), представленной на платформе MIT OpenCourseWare, подробно рассматривается фундаментальный криптографический протокол Килиана — Микали. Этот протокол позволяет преобразовывать громоздкие вероятностно проверяемые доказательства (PCP) в лаконичные интерактивные аргументы с полилогарифмической сложностью коммуникации. В ходе занятия подробно разбираются теоретические основы вычислительной надежности, требования к хеш-функциям с локальным раскрытием и тонкости доказательства безопасности системы.

## 🔄 Рекап: Как протокол GKR помогает создавать вероятностно проверяемые доказательства (PCP)
[[JUMP:0:12]]

Лекция начинается с краткого повторения материала двухнедельной давности, поскольку предыдущая неделя была посвящена «дню криптографии». Яэль Калай напоминает, как использовать протокол GKR для построения вероятностно проверяемых доказательств (PCP — Probabilistically Checkable Proofs). Суть PCP заключается в том, чтобы взять доказательство для любого языка из класса NP (например, для задачи выполнения булевых формул 3-SAT), содержащее удовлетворяющее присваивание (свидетельство), и расширить его. Вместо сжатия доказательство искусственно удлиняется, однако для его верификации нет необходимости читать текст целиком — достаточно изучить лишь несколько случайно выбранных позиций, что обеспечивает экспоненциальное улучшение эффективности проверки.

Процесс генерации PCP строится на гипотетическом сценарии, в котором доказывающий (prover) запускает в уме протокол GKR для проверки формулы 3-SAT. Любая задача из класса NP может быть сведена к 3-SAT, поскольку она является NP-полной. Далее рассматривается схема $C_\phi$, которая принимает на вход присваивание переменных и возвращает 0 или 1 в зависимости от того, является ли оно удовлетворяющим. Эта схема имеет очень малую глубину. Применение GKR в данном контексте может показаться контринтуитивным, ведь классический протокол GKR предполагает, что и доказывающий, и проверяющий (verifier) изначально знают входные данные, а сама схема огромна. В случае же с 3-SAT верификатор не обладает знанием свидетельства, а размер схемы сопоставим с размером самого свидетельства.

Чтобы преодолеть это ограничение, в рамках PCP верификатору «предоставляют» входные данные, записывая в доказательство их низкостепенное расширение (low-degree extension). Полное PCP-доказательство состоит из двух ключевых элементов:

* Низкостепенное расширение свидетельства, размещенное в самом начале.
* Огромное дерево всех возможных ответов доказывающего на любые потенциальные вопросы верификатора.

Калай поясняет структуру этого дерева: доказывающий отправляет одномерный многочлен, верификатор отвечает элементом поля, и для каждого возможного элемента поля в PCP заранее фиксируется ответ. Несмотря на экспоненциальный объем такого дерева, протокол GKR обладает свойством «отсутствия памяти» (memoryless property). Каждое сообщение доказывающего зависит исключительно от последних нескольких реплик верификатора в рамках последовательности протоколов суммирования (sum-check protocols). В частности, размер этой зависимости определяется как $\log n / \log \log n$ сообщений от верификатора. Благодаря этому свойству всю структуру GKR удается развернуть в доказательство полиномиального размера $\text{poly}(n)$.

При верификации этого PCP проверяющий случайным образом выбирает путь в дереве ответов, а в самом конце обращается к низкостепенному расширению свидетельства, чтобы сопоставить финальную точку, как это предусмотрено стандартным протоколом GKR.

## 🌲 Проблема гигантского размера PCP и необходимость обязательства (Commitment)
[[JUMP:11:22]]

Несмотря на то, что верификация гигантского PCP требует прочтения всего лишь полилогарифмического числа позиций (что соответствует коммуникационной сложности GKR для схем логарифмической глубины), само доказательство остается чрезмерно большим. Возникает закономерный вопрос: как именно верификатор может работать с объектом такого масштаба?. Простая идея — попросить верификатора прислать свои запросы, а доказывающего — вернуть ответы только на них, не пересылая все дерево — полностью разрушает надежность системы. Если доказывающий видит вопросы верификатора заранее, он получает возможность подделать ответы динамически: для запроса в позиции $i$ совместно с $j$ он выдаст один результат, а совместно с $j'$ — совершенно другой.

Следовательно, критически важно, чтобы доказывающий сначала жестко зафиксировал (committed) всё PCP-доказательство целиком, и лишь затем верификатор отправлял свои запросы. Поскольку верификатор представляет собой слабое вычислительное устройство, неспособное хранить огромные объемы данных, на помощь приходит криптография. Современные системы используют криптографические методы для того, чтобы «сжать» гигантское доказательство с помощью коллизионно-стойких хеш-функций (collision resistant hash functions).

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

В этом домашнем задании студентам предстоит подробно разобрать проблему надежности (soundness) PCP. Если доказывающий передает корректное низкостепенное расширение свидетельства, которое не удовлетворяет формуле, надежность гарантируется математикой GKR. Однако злонамеренный доказывающий может предоставить некоторую функцию $W^*$, обладающую чрезвычайно высокой степенью. В домашней работе студентам нужно будет найти реальную атаку, демонстрирующую нарушение надежности в таком сценарии, и реализовать тест низкой степени (low-degree test). Верификатор не может гарантировать, что функция строго низкостепенная, но он проверяет, что она совпадает с низкостепенным многочленом на доле точек $1 - \epsilon$.

## 🔐 Переход к аргументам: Вычислительная надежность и субэкспоненциальные допущения
[[JUMP:14:36]]

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

Для интерактивного аргумента на языке $L$ справедливы следующие свойства:

* **Полнота (Completeness):** Если утверждение $x$ принадлежит языку $L$, то честный и эффективный доказывающий убедит верификатора с вероятностью 1.
* **Вычислительная надежность (Computational Soundness):** Любой реальный вредоносный доказывающий $P^*$, чье время работы ограничено полиномом от параметра безопасности $\lambda$, может обмануть верификатора лишь с пренебрежимо малой вероятностью $\mu(\lambda)$.

В рамках курса параметр безопасности обозначается греческой буквой $\lambda$, чтобы избежать путаницы с размером входных данных $n$. Все участники протокола знают этот параметр и работают за время, полиномиальное от его значения. Отвечая на вопрос из аудитории, Калай подчеркивает, что на данном этапе протокол не преследует цель скрыть свидетельство или обеспечить свойство нулевого разглашения — фокус сделан исключительно на лаконичности верификации.

Далее профессор обращает внимание на глубокий теоретический парадокс: если размер входных данных $n$ огромен, а параметр безопасности $\lambda$ выбран как $\text{polylog}(n)$ для обеспечения максимальной лаконичности, то гарантия безопасности против злоумышленника, ограниченного временем $\text{poly}(\lambda)$, становится бессмысленной. Противник в реальном мире обладает возможностью прочитать входные данные, то есть потратить время $n$, что значительно превосходит $\text{poly}(\lambda)$. Студент из аудитории замечает, что при таком раскладе схема злоумышленника даже не сможет физически считать строку $x$.

Калай соглашается с критикой и предлагает два пути решения этой проблемы:

1.  Установить параметр безопасности как полином от размера входа (например, $\lambda = n^\epsilon$ или $n^{0.001}$). В этом случае баланс восстанавливается, злоумышленнику разрешено работать за время $\text{poly}(n)$, а объем доказательства все равно остается меньше $n$, хотя лаконичность ухудшается.
2.  Использовать более сильные субэкспоненциальные криптографические допущения. В таком сценарии предполагается, что коллизии невозможно найти даже за время $2^{\lambda^\epsilon}$. Это позволяет выбирать очень маленький параметр безопасности $\lambda = \text{polylog}(n)$, сохраняя устойчивость системы против полноразмерных реалистичных атак уровня $\text{poly}(n)$.

## 📦 Хеширование с локальным раскрытием: Новый криптографический примитив
[[JUMP:33:51]]

Для реализации сжатия PCP стандартной коллизионно-стойкой хеш-функции недостаточно. Если верификатор получит обычный хеш от огромного PCP, он не сможет проверить отдельные биты доказательства, не затребовав прообраз целиком, что превышает его емкость памяти. Требуется специальный примитив — коллизионно-стойкое хеширование с локальным раскрытием (collision-resistant hash with local opening). Этот примитив формально описывается набором из пяти алгоритмов:

1.  $\text{Gen}(1^\lambda) \rightarrow hk$ — вероятностный алгоритм полиномиального времени (PPT), генерирующий ключ хеширования $hk$ на основе параметра безопасности.
2.  $\text{Eval}(hk, x) \rightarrow v$ — детерминированный алгоритм, принимающий строку $x$ произвольной длины и сжимающий ее в хеш-значение $v$ фиксированного размера $\lambda$.
3.  $\text{Open}(hk, x, v, i) \rightarrow (b, \rho)$ — алгоритм, используемый доказывающим для генерации значения бита $b = x_i$ в позиции $i$ и короткого доказательства раскрытия (сертификата) $\rho$ размера $\text{poly}(\lambda)$.
4.  $\text{Verify}(hk, v, i, b, \rho) \rightarrow \{0, 1\}$ — детерминированный алгоритм верификации, проверяющий валидность раскрытия бита за время $\text{poly}(\lambda)$, полностью независимое от длины исходной строки $n$.

Профессор поясняет физический смысл алгоритма $\text{Open}$: доказывающий выполняет роль владельца данных, а значение $\rho$ служит доказательством для верификатора, что в исходной строке на $i$-м месте находился именно этот бит. Один из студентов выражает удивление тем, что доказывающему приходится хранить и помнить исходную строку $x$ целиком для выполнения раскрытия. Калай подтверждает, что совокупность всех возможных сертификатов раскрытия $\rho_i$ фактически содержит в себе всю информацию о строке $x$, поэтому хранение исходного текста неизбежно.

Математическое свойство корректности (correctness) гарантирует, что если все участники следуют протоколу честно, то алгоритм $\text{Verify}$ всегда вернет 1. Длина строки $x$ при этом ограничена значением $2^\lambda$. Свойство надежности (collision resistance) постулирует, что никакой ограниченный во времени противник, получив случайный ключ $hk$, не способен сгенерировать такое хеш-значение $v$ и индекс $i$, для которых можно было бы одновременно построить два валидных доказательства раскрытия — $\rho_0$ для бита 0 и $\rho_1$ для бита 1. Вероятность такого события пренебрежимо мала.

## 🤝 Протокол Килиана — Микали: Пошаговая структура и логика взаимодействия
[[JUMP:50:43]]

Описанные компоненты объединяются в знаменитый протокол Килиана — Микали (Kilian-Micali protocol), предназначенный для построения лаконичных интерактивных аргументов для NP. В качестве основы авторы используют два независимых ингредиента: PCP-систему с пренебрежимо малой ошибкой надежности и коллизионно-стойкое хеширование с локальным раскрытием.

Пошаговый алгоритм взаимодействия доказывающего ($P$) и верификатора ($V$) выглядит следующим образом:

1.  Верификатор генерирует криптографический ключ хеширования $hk \leftarrow \text{Gen}(1^\lambda)$ и отправляет его доказывающему.
2.  Доказывающий берет свидетельство $w$ для формулы 3-SAT и вычисляет в уме полное PCP-доказательство $\pi$. Затем он хеширует эту гигантскую строку: $v = \text{Eval}(hk, \pi)$, и отсылает короткий дайджест $v$ верификатору.
3.  Верификатор, получив $v$, запускает внутренний алгоритм PCP-верификации $V_{\text{PCP}}$. Этот алгоритм определяет набор случайных индексов запросов $i_1, i_2, \dots, i_l$, которые верификатор отправляет доказывающему.
4.  Доказывающий извлекает значения битов доказательства в запрошенных позициях $\pi_{i_1}, \dots, \pi_{i_l}$ и для каждой из них вычисляет сертификаты локального раскрытия $\rho_{i_1}, \dots, \rho_{i_l}$ с помощью алгоритма $\text{Open}$. Эти данные пересылаются обратно верификатору.
5.  Верификатор принимает окончательное решение на основе двух проверок: он удостоверяется в корректности каждого криптографического раскрытия через $\text{Verify}(hk, v, i_j, \pi_{i_j}, \rho_{j}) = 1$ и оценивает комбинацию полученных битов через стандартный логический верификатор $V_{\text{PCP}}$.

Яэль Калай обращает внимание на критически важную деталь: объем пересылаемых данных (ключ, корень хеша, индексы и доказательства раскрытия) зависит исключительно от параметра безопасности $\lambda$ и не растет вместе с размером задачи $n$. Если $\lambda = \text{polylog}(n)$, то коммуникация строго полилогарифмична. При этом сам верификатор обязан работать за время, линейное от размера входа $x$, поскольку он должен хотя бы прочитать формулировку доказываемого утверждения. Существуют теоретические концепции вроде PCP близости (PCP of proximity), позволяющие верификатору проверять истинность за сублинейное время, однако они дают более слабую гарантию — уверенность лишь в том, что утверждение «близко» к истинному.

Профессор просит студентов зафиксировать в памяти еще одно свойство: вместо перечисления конкретных индексов верификатор может просто отправить доказывающему случайную битовую строку (энтропию), на основе которой тот сам детерминированно вычислит индексы. Тот факт, что сообщения верификатора состоят из чистой случайности, имеет фундаментальное значение для исключения интерактивности в будущем с помощью парадигмы Фиата — Шамира (Fiat-Shamir paradigm). Первая реплика с передачей ключа $hk$ может иметь сложную структуру (например, связанную с задачей обучения с ошибками LWE), но все последующие шаги верификатора абсолютно случайны.

## 🔬 Анализ надежности протокола и скрытые ловушки в доказательстве
[[JUMP:1:13:31]]

Проверка полноты протокола тривиальна, так как при честном исполнении обе базовые системы (PCP и хеширование) гарантируют успех с вероятностью 1. Основной аналитический интерес представляет доказательство надежности. Калай предлагает использовать классический метод редукции от противного: предположим, что существует эффективный злонамеренный доказывающий $P^*$, способный убедить верификатора в истинности ложного утверждения $x \notin L$ с некоторой небрежимо малой, но заметной вероятностью $\epsilon$.

Для деконструкции защиты строится алгоритм-взломщик $A$, цель которого — найти коллизию в хеш-функции за полиномиальное время, используя силу $P^*$. Схема взлома выглядит следующим образом:

1.  Алгоритм $A$ передает доказывающему $P^*$ случайный ключ хеширования $hk$ и фиксирует полученный в ответ дайджест $v$.
2.  Затем применяется процедура «перемотки» (rewinding): алгоритм $A$ запускает доказывающего множество раз (порядка $\text{poly}(n) \cdot \epsilon^{-3}$), каждый раз генерируя новые случайные запросы верификатора $r_j$ при неизменном значении $v$.
3.  Все ответы, где доказательства раскрытия $\rho$ оказываются невалидными, отбрасываются (это составляет долю $1-\epsilon$). Из оставшихся успешных ответов алгоритм пытается извлечь коллизию.

Здесь возникает развилка. Если для какого-то индекса $i$ доказывающий в разных сессиях выдал валидные подтверждения и для бита 0, и для бита 1, коллизия найдена, и криптографическая стойкость опровергнута. Если же коллизий нет, это означает, что доказывающий ведет себя абсолютно последовательно. В таком случае алгоритм $A$ может полностью реконструировать по его ответам единое, статичное PCP-доказательство $\pi$. Пустые или неотвеченные места заполняются нулями. Однако, поскольку исходное утверждение ложно ($x \notin L$), существование такого PCP, принимаемого с высокой вероятностью, напрямую противоречит математической надежности исходной PCP-системы. Следовательно, доказывающий неизбежно должен производить коллизии.

В финале лекции Яэль Калай раскрывает концептуальную уловку, к которой она прибегла в ходе этого доказательства: «Я вас обманула», — признается профессор. Описанная редукция безупречно работает только в том случае, если верхняя граница времени работы злоумышленника $T(\lambda)$ строго больше, чем размер PCP-доказательства $n$. Если же временной ресурс противника меньше $n$, то алгоритм $A$ физически не успеет провести нужное количество перемоток для реконструкции гигантского PCP, и доказательство разваливается. Этот нюанс долгое время беспокоил криптографов. Проблема была элегантно решена лишь в 2002 году в работе Барака и Голдрейха (Barak, Goldreich), которые предложили метод доказательства без полной реконструкции PCP. Подробный разбор этой логики и конструкции коллизионно-стойких хеш-функций переносится на вторую часть лекции после объявленного пятиминутного перерыва.