В лекционных залах Массачусетского технологического института (MIT) продолжается глубокое погружение в мир современной криптографии. В рамках восьмой лекции курса Чженчжун Цзинь (Zhengzhong Jin) представляет концепцию BARGs — кратких неинтерактивных аргументов для пакетных NP-языков, объясняя, как эффективно доказать истинность сразу множества утверждений, не раздувая размер доказательства.
📦 Пакетные аргументы: когда опт выгоднее розницы 0:12
Понятие «батчинга» (пакетной обработки) — фундаментальная концепция в информатике, позволяющая объединять множество элементов в одну коллекцию для совместной обработки. В контексте систем доказательств это превращается в BARGs (Batch Arguments) или SNARGs for Batch NP.
Вместо того чтобы доказывать каждое утверждение $x$ по отдельности, проувер (доказывающая сторона) стремится убедить верификатора в том, что весь список инстансов ${x_1, \dots, x_k}$ принадлежит некому NP-языку $L$. Ключевая характеристика такой системы — лаконичность (succinctness).
По определению Чженчжуна Цзиня, система считается лаконичной, если размер доказательства $\pi$ строго меньше суммарной длины всех свидетельств (witnesses) для данного пакета. В тривиальной системе проувер мог бы просто отправить все свидетельства верификатору, но цель BARGs — сделать передачу данных значительно эффективнее.
Основные свойства BARG:
- Полнота (Completeness): честно сгенерированное доказательство всегда принимается.
- Надежность (Soundness): если хотя бы одно утверждение в пакете ложно, обмануть верификатора должно быть практически невозможно.
🧱 Зачем это нужно и как обойти «невозможное» 6:30
На первый взгляд BARGs могут показаться узкоспециализированным инструментом, но Чженчжун Цзинь подчеркивает их важность как строительных блоков. По его словам, аналогичные концепции уже успешно применяются в других областях криптографии, например, в агрегированных подписях, где множество подписей сжимаются в одну короткую.
Более того, лектор анонсирует, что BARGs являются критически важным компонентом для создания SNARGs для всего класса NP. Однако на пути исследователей стоит теоретическое препятствие — результат Гентри и Викса (Gentry-Wichs).
Суть ограничения Гентри-Викса:
Невозможно построить SNARGs для произвольного сложного языка с размером доказательства существенно меньше, чем логарифм времени проверки этого языка, используя только «фальсифицируемые» (falsifiable) предположения.
Чженчжун Цзинь объясняет, что для общего случая NP это означает невозможность создания доказательства короче длины свидетельства $w$. Однако BARGs элегантно обходят это ограничение: даже если размер доказательства сопоставим с $w$, он все равно будет «лаконичным» по отношению к пакету из $k$ утверждений, так как $w \ll k \times w$.
🛠 Теорема и первая попытка построения 12:43
Главная цель лекции — доказать существование конструкции BARGs на основе задачи LWE (Learning With Errors). Согласно представленной теореме, размер доказательства в такой системе определяется размером схемы отношения $C$, а время верификации состоит из фиксированной части для обработки инстансов и короткой «онлайн-фазы», не зависящей от количества утверждений в пакете $k$.
Для построения Чженчжун Цзинь предлагает использовать модифицированный протокол Килиана (Kilian's protocol).
Алгоритм начальной схемы:
- Генерация PCP: Проувер создает вероятностно проверяемое доказательство (PCP) для каждого из $k$ инстансов.
- Матрица доказательств: Эти PCP-строки можно представить в виде матрицы, где строки — это доказательства для отдельных инстансов, а столбцы — соответствующие биты этих доказательств.
- Хеширование по столбцам: Вместо использования дерева Меркла, лектор предлагает хешировать каждый столбец матрицы отдельно, получая набор значений $h_1, \dots, h_L$.
- Запрос и ответ: Верификатор присылает случайный запрос $Q$ (набор индексов), и проувер открывает соответствующие столбцы хеш-матрицы.
🧩 Проблема интерактивности и CI-хеширование 32:35
Чтобы превратить интерактивный протокол в SNARG (неинтерактивный аргумент), обычно используется парадигма Фиата-Шамира. Однако здесь требуется особый инструмент — корреляционно-неуязвимые хеш-функции (Correlation-Intractable Hash, CI Hash).
По словам Цзиня, CI-хеш должен гарантировать, что для заданного отношения $R$ злоумышленнику будет сложно найти такой вход $x$, чтобы пара $(x, H(x))$ попала в это отношение. В нашем случае отношение $R$ — это условия, при которых верификатор принимает доказательство.
Ключевая проблема здесь заключается в разреженности (sparsity) отношения. Чтобы CI-хеш существовал, для любого фиксированного первого сообщения проувера лишь ничтожная доля ответов верификатора должна приводить к принятию ложного доказательства. Но в схеме с обычным сжимающим хешем у одного значения $h$ может быть множество прообразов, что «засоряет» отношение и мешает доказательству надежности.
🛡 Решение: Somewhere Statistical Binding (SSB) хеш 49:40
Для преодоления проблемы разреженности Чженчжун Цзинь вводит понятие Somewhere Statistical Binding (SSB) хеш-функции. Это особый тип хеширования, который обладает двумя свойствами:
- Скрытность индекса (Key Indistinguishability): Ключ хеша создается для конкретной позиции (индекса) $i$, но глядя на ключ, невозможно понять, какой именно индекс был выбран.
- Статистическая привязка (Statistical Binding): Хеш-значение статистически фиксирует входные данные именно в позиции $i$. Если хеши двух строк совпали, то их элементы в позиции $i$ гарантированно идентичны.
Лектор демонстрирует элегантный способ построения SSB на основе полностью гомоморфного шифрования (FHE).
Как работает SSB через FHE:
- Ключ: Это зашифрованный с помощью FHE индекс $i$.
- Хеширование: Чтобы хешировать данные $x_1, \dots, x_n$, мы гомоморфно вычисляем функцию, которая «выбирает» $i$-й элемент из массива под каподом шифра.
- Результат: Хешем является сам криптотекст FHE. Поскольку FHE скрывает то, что внутри, свойство скрытности индекса выполняется автоматически из безопасности шифрования.
⚖️ Финальный аккорд: Доказательство надежности 1:06:17
Использование SSB-хеша позволяет «привязать» проувера к конкретной строке в матрице PCP. Если в пакете есть хотя бы одно ложное утверждение $x_{i^}$, мы можем сгенерировать CRS (общую строку параметров) с SSB-ключом, настроенным именно на этот индекс $i^$.
Благодаря свойствам SSB, хеши столбцов теперь жестко фиксируют именно $i^$-ю строку матрицы — ту самую, которая соответствует ложному утверждению. Теперь отношение для CI-хеша становится разреженным: оно сводится к проверке того, примет ли PCP-верификатор конкретное (уже фиксированное в хеше) ложное доказательство для $x_{i^}$.
По словам Чженчжуна Цзиня, такая гибридная структура — переключение CRS на индекс ошибки и использование экстракции из SSB — позволяет свести надежность всей системы к безопасности базовых примитивов (LWE и FHE).
