# Яэль Калай об открытой проблеме PSPACE и криптографических аргументах

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

---

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

## 🧩 Проверка низкой степени в PCP и её ограничения
[[JUMP:0:12]]

Профессор Яэль Калай начала лекцию с указания на то, что рассматриваемая система PCP является неадаптивной. Это означает, что вопросы, которые верификатор задает доказывающему (проверу), не зависят от получаемых ответов, поскольку протокол суммы (sum-check) является протоколом с публичными монетами (public coin).

Тем не менее верификатору необходимо удостовериться, что свидетель (witness), находящийся в PCP, имеет низкую степень. В честном сценарии доказывающий строит расширение низкой степени, которое должно иметь степень $H - 1$ по каждой координате. Однако верификатор физически не может полностью проверить это свойство из-за жесткого ограничения на количество запросов.

Вместо этого верификатор проверяет близость полинома к полиному низкой степени. Математически гарантируется, что с высокой вероятностью существует истинный полином низкой степени $\tilde{W}$, который совпадает с предоставленным в большинстве точек. Разница между ними составляет малую величину $\epsilon$.

## 📏 Тестирование случайных прямых и оптимизация GKR
[[JUMP:5:32]]

Для реализации проверки близости к низкой степени используется метод случайных выборок. Верификатор выбирает случайную прямую в пространстве $\mathbb{F}^m$ и проверяет, составляет ли её степень величину $m \times (H - 1)$. Если степень не совпадает, доказывающий немедленно отвергается.

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

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

## 🔢 Лимиты запросов: от полилогарифма к трем битам
[[JUMP:10:58]]

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

Снизить количество запросов до двух бит при условии идеальной полноты (perfect completeness) невозможно. По мнению профессора, интуитивная причина этого кроется в том, что задача 2-SAT легко разрешима алгоритмически. Добиться двух запросов можно только в двух специфических случаях:

* Если ответы верификатору возвращаются большими «блоками» (словами) полилогарифмического размера.
* Если допустить неидеальную полноту, снизив порог успешного прохождения для честного доказывающего до уровня $1 - \epsilon$.

Для повышения надежности системы (снижения вероятности ошибки) верификатору достаточно перезапускать проверку независимо, используя свежую случайность. Провер при этом не участвует в повторениях и не меняет само доказательство PCP. Если начальная вероятность ошибки равна $1/2$, то после $k$ повторений она падает до $1/2^k$.

## 💰 Открытая проблема PSPACE и премия в $500
[[JUMP:17:25]]

Завершая теоретико-информационный блок, Яэль Калай выделила фундаментальную проблему, остающуюся нерешенной в полной мере. В 2016–2018 годах ученые Рейнгольд, Ротблум и Ротблум разработали дважды эффективные протоколы для вычислений с ограниченной глубиной. Однако создание аналогичного эффективного протокола для вычислений с ограниченной памятью (bounded space) сталкивается с препятствиями.

Известно, что класс интерактивных доказательств IP равен классу PSPACE, и переход от вычислений с ограниченной глубиной к ограниченной памяти возможен, но он разрушает полиномиальную эффективность доказывающего, делая её экспоненциальной. Цель исследователей — создать дважды эффективное интерактивное доказательство для PSPACE, где время работы верификатора и сложность коммуникации зависели бы только от объема памяти $S$, но не от времени вычислений $T$.

В работе Рейнгольда и братьев Ротблум время верификатора все еще умножается на фактор $T^\epsilon$, что делает верификатора неэффективным при сверхполиномиальном времени $T$. Профессор Калай эмоционально обратилась к студентам MIT, Гарварда и других бостонских вузов с просьбой решить эту задачу, пообещав личную денежную премию:

> «Помимо очевидного признания и возможной награды ACM за лучшую докторскую диссертацию, я готова выплатить из своего кармана приз в размере $500 тому, кто избавится от этого фактора $T$ в уравнениях».

## 🔒 Переход к криптографии: вычислительно надежные аргументы
[[JUMP:25:02]]

Основной недостаток классических PCP заключается в их гигантском размере. Доказательство должно быть физически записано в разделяемой памяти, иначе злонамеренный доказывающий сможет адаптировать свои ответы в процессе диалога и обмануть верификатора. Поскольку хранить такие объемы данных на практике невозможно, ученые обратились к криптографии.

Первым шагом стало изменение модели надежности и переход к вычислительно надежным доказательствам, которые в литературе называют «аргументами». В отличие от статистических доказательств, аргументы гарантируют защиту от обмана только в том случае, если вычислительные ресурсы доказывающего ограничены.

По словам Яэль Калай, в реальном мире нет смысла требовать абсолютной статистической надежности против доказывающего, способного совершить $2^{1000}$ операций, ведь во Вселенной даже нет стольки молекул. Если ограничить время работы злоумышленника реалистичной верхней планкой (например, менее $2^{500}$ операций), открывается возможность внедрения мощных криптографических допущений.

## 🤝 Теорема Килиана — Микали и сжатие доказательств
[[JUMP:35:03]]

Фундаментом для нового класса сжатых доказательств послужила классическая теорема Джо Килиана и Сильвио Микали (1992–1994 годы). Они доказали, что используя систему PCP и криптографический инструмент — хеш-функцию, устойчивую к коллизиям, — можно сжать гигантское доказательство PCP в компактный четырехсообщенный аргумент.

Криптографические примитивы всегда функционируют в связке с параметром безопасности $\lambda$. В теоретической информатике этот параметр задается в унарной системе счисления ($1^\lambda$), чтобы алгоритмы оставались полиномиальными относительно длины входа. Теорема Килиана — Микали обеспечивает следующие параметры эффективности:

* Время работы честного доказывающего составляет $poly(N, \lambda)$, где $N$ — длина экземпляра задачи, а $\lambda$ — параметр безопасности.
* Время работы верификатора полиномиально зависит исключительно от параметра безопасности $\lambda$ и времени работы стандартного PCP-верификатора.
* Вероятность успешного обмана со стороны ограниченного в ресурсах провера является пренебрежимо малой (negligible) величиной, которая затухает быстрее любого полинома с ростом $\lambda$.

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

## 🔑 Семейства хеш-функций и концепция локального открытия
[[JUMP:56:09]]

Для строгого математического описания криптографического аргумента вводится семейство хеш-функций, устойчивых к коллизиям (CRHF). Оно состоит из двух ключевых алгоритмов: `Gen` (генерация ключа хеширования на основе параметра безопасности) и `Eval` (вычисление хеш-значения фиксированной длины $\lambda$ для любого входного слова любой длины).

Наличие ключа хеширования критически важно для защиты от неоднородных (non-uniform) противников. Профессор Калай пояснила, что если бы ключа не было, злоумышленник мог бы заранее вычислить коллизию (два разных входа с одинаковым хешем), «зашить» её в свою структуру и гарантированно обмануть систему. Ключ делает этот процесс вычислительно невозможным, сводя вероятность нахождения коллизии к пренебрежимо малой.

Для реализации теоремы Килиана — Микали стандартная хеш-функция дополняется свойством локального открытия (local opening). Это позволяет доказывающему «сжать» всё огромное PCP-доказательство в один короткий хеш-корень и отправить его верификатору. Когда верификатор запрашивает случайные биты в позициях $i_1, i_2, \dots, i_l$, доказывающему не нужно раскрывать всё доказательство. Он присылает лишь значения этих бит вместе с компактными локальными доказательствами (локальными открытиями) того, что данные биты действительно соответствуют исходному общему хешу.