Доказательство с нулевым разглашением: как это работает

Доказательство с нулевым разглашением (zero-knowledge proof, ZKP) - это криптографический протокол, в котором одна сторона (доказывающий) убеждает другую (проверяющего) в истинности утверждения, не раскрывая при этом никакой информации, кроме самого факта истинности. Идею в 1985 году предложили Голдвассер, Микали и Ракофф; за неё Голдвассер и Микали позже получили премию Тьюринга. На практике концепция лежит в основе анонимных платёжных систем, протоколов аутентификации и масштабирования блокчейнов. В этой статье разбираем формальное определение, три обязательных свойства, классический протокол и характерные ошибки, которые студенты допускают на коллоквиумах по криптографии.

Что такое доказательство с нулевым разглашением

Формально доказательство с нулевым разглашением строится вокруг языка $L$ - множества утверждений, которые «истинны». Доказывающий $P$ (Prover) знает секрет - свидетеля (witness) $w$ для утверждения $x \in L$. Проверяющий $V$ (Verifier) хочет удостовериться, что $x \in L$, но не должен узнать $w$ и вообще ничего, что нельзя было бы вычислить самостоятельно.

Классическая иллюстрация - «пещера Али-Бабы». Кольцевая пещера имеет два прохода (A и B), соединённых дверью, открываемой секретным словом. Доказывающий заходит в один из проходов, проверяющий кричит, из какого прохода тот должен выйти. Если доказывающий знает слово, он всегда выходит из нужного; если не знает - угадывает с вероятностью $1/2$. Повторив раунд $k$ раз, мы загоняем вероятность обмана до $2^{-k}$, при этом проверяющий ни разу не услышал само секретное слово.

Чтобы перейти от метафоры к рабочему протоколу аутентификации, удобно собрать конкретный сценарий и посмотреть, как раскладываются роли и сообщения. Воспользуйтесь конструктором ниже.

Три свойства: полнота, корректность, нулевое разглашение

Протокол считается доказательством с нулевым разглашением, только если выполнены три свойства одновременно.

Полнота (completeness). Если утверждение истинно и обе стороны честны, проверяющий принимает доказательство с подавляющей вероятностью. Формально: для $x \in L$ $\Pr[\langle P, V\rangle(x) = \text{accept}] \ge 1 - \text{negl}(n).$

Корректность (soundness). Если утверждение ложно ($x \notin L$), то никакой, даже жульничающий, доказывающий $P^*$ не убедит честного проверяющего, кроме как с пренебрежимо малой вероятностью: $\Pr[\langle P^*, V\rangle(x) = \text{accept}] \le \text{negl}(n).$

Нулевое разглашение (zero-knowledge). Существует эффективный симулятор $S$, который без доступа к свидетелю $w$ порождает протокольную выписку (transcript), статистически неотличимую от настоящей. Если такая выписка генерируется без секрета, значит, проверяющий не узнаёт из неё ничего нового - он мог бы получить то же самое сам. Это и есть формальный смысл фразы «никакой информации не раскрывается».

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

Интерактивный протокол: commitment - challenge - response

Канонический интерактивный ZKP состоит из трёх сообщений и называется $\Sigma$-протоколом:

1. Commitment ($t$): доказывающий посылает обязательство, фиксируя случайность, но не раскрывая секрет.
2. Challenge ($c$): проверяющий шлёт случайный вызов.
3. Response ($s$): доказывающий отвечает так, что ответ проходит проверку только при знании свидетеля.

Рассмотрим протокол Шнорра для доказательства знания дискретного логарифма. Пусть $g$ - генератор группы порядка $q$, открытый ключ $y = g^x$, секрет - показатель $x$. Доказывающий:

1. Выбирает случайное $r$, отправляет $t = g^r$.
2. Получает вызов $c$.
3. Отправляет $s = r + c x \bmod q$.

Проверяющий принимает, если $g^s = t \cdot y^c$. Подстановка показывает полноту: $g^{r + cx} = g^r \cdot (g^x)^c = t \cdot y^c$. Корректность доказывается через извлекатель (extractor): из двух принятых выписок с одним $t$, но разными $c_1 \ne c_2$ восстанавливается $x = (s_1 - s_2)(c_1 - c_2)^{-1} \bmod q$. Нулевое разглашение - симулятор выбирает $s$ и $c$ заранее и вычисляет $t = g^s y^{-c}$, получая корректную выписку без знания $x$.

Протокол Фиаге-Фиата-Шамира

Историчеcки первый практичный протокол идентификации, основанный на сложности извлечения квадратных корней по модулю составного числа. Пусть $n = pq$ - модуль RSA, секрет $s$, открытый параметр $v = s^2 \bmod n$. Один раунд:

1. Доказывающий выбирает случайное $r$, шлёт $x = r^2 \bmod n$.
2. Проверяющий шлёт бит $c \in \{0, 1\}$.
3. Доказывающий отвечает $y = r \cdot s^c \bmod n$.
4. Проверка: $y^2 \equiv x \cdot v^c \pmod n$.

При $c = 0$ ответ $y = r$ ничего не раскрывает; при $c = 1$ ответ $y = r s$ маскирует секрет случайным $r$. Каждый раунд снижает вероятность обмана вдвое, поэтому за $k$ раундов корректность достигает $2^{-k}$. Это типичная задача на семинаре: посчитать вероятность успешного обмана и число раундов для заданной стойкости.

Неинтерактивные доказательства и эвристика Фиата-Шамира

Интерактивность неудобна: нужно живое общение между сторонами. Эвристика Фиата-Шамира превращает $\Sigma$-протокол в неинтерактивный, заменяя случайный вызов проверяющего на хеш от обязательства: $c = H(t)$ (или $c = H(t \,\|\, m)$ для подписи). Поскольку хеш-функция $H$ моделируется как случайный оракул, доказывающий не может подобрать $t$ под удобный $c$. Так из протокола Шнорра получается схема цифровой подписи Шнорра, а сама конструкция NIZK (non-interactive zero-knowledge) лежит в основе zk-SNARK и zk-STARK - компактных доказательств для блокчейнов.

Современные системы вроде zk-SNARK дают доказательства знания (proof of knowledge): проверяется не только истинность утверждения, но и то, что доказывающий действительно владеет свидетелем. Поскольку неинтерактивные схемы опираются на хеш-функции, полезно вспомнить механику полиномиального хеширования в алгоритме Рабина-Карпа, а число теоретико-числовых предположений рядом - в теореме Дирихле о простых числах.

Где применяется

Доказательства с нулевым разглашением вышли далеко за пределы теории. Анонимная криптовалюта Zcash использует zk-SNARK, чтобы подтверждать корректность транзакции, не раскрывая отправителя, получателя и сумму. Протоколы аутентификации позволяют доказать знание пароля, не передавая его. Системы голосования подтверждают, что бюллетень засчитан правильно, сохраняя тайну волеизъявления. Решения масштабирования (rollup) сжимают тысячи транзакций в одно короткое доказательство.

Частые ошибки

• Путают нулевое разглашение с шифрованием. ZKP не скрывает сообщение - он доказывает утверждение, не выдавая свидетеля. Это разные задачи.
• Забывают про симулятор. Свойство нулевого разглашения доказывается существованием симулятора, а не словами «секрет не передаётся». Без симулятора доказательство неполное.
• Считают один раунд достаточным. В протоколах с битовым вызовом один раунд даёт вероятность обмана $1/2$. Нужное число раундов выводится из требуемой стойкости $2^{-k}$.
• Повторно используют случайность $r$. В протоколе Шнорра два разных вызова при одном $r$ позволяют извлечь секрет $x$ - это уязвимость, а не свойство.
• Смешивают корректность и полноту. Полнота - про честные стороны и истинные утверждения; корректность - про защиту от жульничающего доказывающего на ложных утверждениях.

FAQ

Чем доказательство знания отличается от обычного ZKP? Обычное доказательство убеждает, что утверждение $x \in L$ истинно. Доказательство знания дополнительно гарантирует через извлекатель, что доказывающий владеет конкретным свидетелем $w$, а не просто знает о его существовании.

Почему нужен случайный оракул в эвристике Фиата-Шамира? Замена вызова на $c = H(t)$ безопасна, только если доказывающий не способен предсказать или подстроить выход $H$. Модель случайного оракула формализует это предположение и позволяет доказать стойкость подписи.

Что значит «вычислительное» нулевое разглашение? Это означает, что выписка симулятора неотличима от настоящей не абсолютно, а лишь для любого алгоритма с полиномиальным временем работы. Опирается на вычислительные предположения, например на трудность дискретного логарифма.

Коротко

Доказательство с нулевым разглашением - протокол, в котором доказывающий убеждает проверяющего в истинности утверждения, не раскрывая свидетеля. Оно обязано удовлетворять трём свойствам: полноте, корректности и нулевому разглашению (последнее доказывается существованием симулятора). Классические $\Sigma$-протоколы Шнорра и Фиаге-Фиата-Шамира строятся по схеме commitment - challenge - response, а эвристика Фиата-Шамира делает их неинтерактивными, открывая путь к zk-SNARK и анонимным платёжным системам.