Протокол Шнорра: схема доказательства знания и подпись

Протокол Шнорра - это интерактивная схема, в которой одна сторона (доказывающий) убеждает другую (проверяющего) в том, что знает секрет - дискретный логарифм $x$ публичного значения $y = g^x$, - ни на бит не раскрывая сам секрет. Это канонический пример доказательства с нулевым разглашением и одновременно основа целого семейства цифровых подписей: убрав интерактивность приёмом Фиата - Шамира, из протокола получают компактную подпись Шнорра, которая лежит в основе EdDSA и обновления Bitcoin Taproot. В этой статье разберём тройку обязательство - вызов - ответ, уравнение проверки, три свойства протокола (полнота, корректность, нулевое разглашение) и переход к неинтерактивной подписи. Чтобы пройти раунд по шагам с конкретными числами, воспользуйтесь конструктором ниже.

Что доказывает протокол Шнорра

Зафиксируем циклическую группу $G$ порядка $q$ с генератором $g$ - обычно это подгруппа простого порядка в $\mathbb{Z}_p^*$ или группа точек эллиптической кривой. Доказывающий знает секретный ключ $x \in \{1, \dots, q-1\}$, а публичным является $y = g^x$. Перейти от $x$ к $y$ легко, а восстановить $x$ по $y$ - это задача дискретного логарифма, для которой в правильно выбранной группе не известно эффективного алгоритма. Именно на этой односторонности держится вся конструкция.

Задача протокола - убедить проверяющего, что доказывающий действительно знает $x$, не передавая ни $x$, ни даже частичной информации о нём. Это сильнее, чем просто «знать пароль и показать его»: проверяющий после диалога не сможет ни сам выдать себя за доказывающего, ни убедить кого-то третьего. Похожая идея односторонней функции и пары ключей лежит и в основе цифровой подписи ECDSA, но там схема сразу неинтерактивна, тогда как Шнорр начинается с честного диалога из трёх сообщений.

Тройка обязательство - вызов - ответ

Один раунд протокола Шнорра - это три сообщения между доказывающим (П) и проверяющим (В). Их традиционно обозначают $(t, c, s)$ и называют обязательством, вызовом и ответом.

1. Обязательство. Доказывающий выбирает случайный одноразовый секрет $r \in \{1, \dots, q-1\}$ (его называют нонсом или маскирующим), вычисляет $t = g^r$ и отправляет $t$ проверяющему. Это «заявка», которую нельзя будет изменить задним числом.
2. Вызов. Проверяющий выбирает случайный вызов $c$ из множества допустимых значений и отправляет его доказывающему.
3. Ответ. Доказывающий вычисляет $s = r + c \cdot x \bmod q$ и отправляет $s$. В этом ответе секрет $x$ присутствует, но он спрятан под слагаемым $r$, которое проверяющий не знает.

Рассчитать для своей задачи

Вся соль в том, что $r$ - свежий случайный для каждого раунда. Без него ответ $s$ был бы просто функцией от $x$, и секрет можно было бы извлечь. С ним $s$ выглядит для проверяющего как равномерно случайное число.

Уравнение проверки

Получив тройку $(t, c, s)$, проверяющий принимает решение по единственному равенству:

$$g^s \stackrel{?}{=} t \cdot y^c.$$

Если оно выполняется, проверка пройдена. Почему это работает, видно из прямой подстановки. У честного доказывающего $s = r + c x$, поэтому

$$\begin{aligned} g^s &= g^{r + c x} \\ &= g^r \cdot (g^x)^c \\ &= t \cdot y^c. \end{aligned}$$

Равенство - тождество, значит честный доказывающий всегда проходит проверку. Это свойство называют полнотой (completeness): кто знает $x$, тот гарантированно убеждает проверяющего. Заметьте, что проверяющему для расчёта нужны только публичные $g$, $y$ и пришедшие $t$, $c$, $s$ - секрет $x$ в проверку не входит.

Почему секрет не раскрывается

Главное обещание протокола - нулевое разглашение (zero-knowledge): из диалога проверяющий не узнаёт об $x$ ничего, чего не мог бы вычислить сам. Формально это доказывают через симулятор: можно сгенерировать тройку $(t, c, s)$ с тем же распределением, что у настоящего диалога, вообще не зная $x$. Достаточно выбрать случайные $c$ и $s$, а затем положить $t = g^s \cdot y^{-c}$ - такая тройка пройдёт проверку и неотличима от честной. Раз поддельный протокол с правильным распределением строится без секрета, значит настоящий протокол секрета и не выдаёт.

Рассчитать для своей задачи

Здесь важно условие честного проверяющего: он выбирает $c$ независимо от $t$. Если бы проверяющий мог подсмотреть $t$ и хитро подобрать $c$, схема в базовом виде уже не была бы строго нулевого разглашения - для общего случая нужны дополнительные приёмы. В учебных задачах почти всегда подразумевают честно-проверяющую модель.

Корректность: почему нельзя обмануть

Симметричное свойство - корректность (soundness, особая корректность): жулик, не знающий $x$, не сможет систематически проходить проверку. Доказывают это так. Предположим, доказывающий с одним и тем же обязательством $t$ сумел ответить на два разных вызова $c_1 \ne c_2$ корректными ответами $s_1$ и $s_2$. Тогда

$$\begin{aligned} g^{s_1} &= t \cdot y^{c_1}, \\ g^{s_2} &= t \cdot y^{c_2}. \end{aligned}$$

Поделив одно на другое, получаем $g^{s_1 - s_2} = y^{c_1 - c_2}$, откуда

$$x = \frac{s_1 - s_2}{c_1 - c_2} \bmod q.$$

То есть любой, кто отвечает на два вызова при одном $t$, тем самым вычисляет секрет $x$. Раз вычислить дискретный логарифм нельзя, нельзя и отвечать на два вызова, - значит, на случайный единственный вызов жулик угадывает ответ лишь с пренебрежимо малой вероятностью. Этот же приём «извлечения секрета из двух ответов» дословно повторяет логику атаки на повтор нонса в алгоритме обмена ключами Диффи - Хеллмана и в ECDSA.

От диалога к подписи: эвристика Фиата - Шамира

Интерактивность неудобна: подписать файл «один раз для всех» в диалоге нельзя. Приём Фиата - Шамира убирает проверяющего, заменяя его случайный вызов на хэш. Доказывающий сам вычисляет

$$c = H(g, y, t, m),$$

где $m$ - подписываемое сообщение, а $H$ - криптографическая хэш-функция. Поскольку $c$ зависит от $t$ непредсказуемым образом, доказывающий не может заранее подогнать $t$ под удобный $c$ - хэш играет роль честного проверяющего. Подпись Шнорра - это пара $(c, s)$ или $(t, s)$, а проверка остаётся той же: пересчитать $c = H(g, y, t, m)$ и убедиться, что $g^s = t \cdot y^c$.

Именно так из учебного протокола вырастает практичная подпись: компактная, с простым и линейным уравнением, поддающаяся агрегации нескольких подписей в одну. Поэтому Шнорр выбрали для EdDSA (Ed25519) и для Bitcoin Taproot.

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

• Повтор нонса $r$. Если переиспользовать одно $r$ для двух подписей, по двум ответам $s_1, s_2$ мгновенно вычисляется $x = (s_1 - s_2)/(c_1 - c_2)$ - ровно как в доказательстве корректности. Нонс обязан быть свежим и непредсказуемым для каждого раунда.
• Путать порядок группы $q$ и модуль $p$. Степени и $t = g^r$ считают по модулю $p$, а показатели $s = r + cx$ - по модулю $q$ (порядка генератора). Смешение модулей - самая частая арифметическая ошибка в задачах.
• Считать, что $s$ что-то выдаёт об $x$. Слагаемое $r$ маскирует секрет: при честном случайном $r$ ответ $s$ распределён равномерно и сам по себе об $x$ не говорит ничего.
• Забывать про честно-проверяющую модель. Нулевое разглашение базового протокола доказано для проверяющего, который выбирает $c$ независимо от $t$; это условие нужно явно оговаривать.
• Брать вызов $c$ из слишком маленького множества. Если вызовов всего несколько, жулик угадывает ответ с заметной вероятностью; стойкость требует большого пространства вызовов.

FAQ

Чем протокол Шнорра отличается от подписи Шнорра? Протокол - это интерактивный диалог из трёх сообщений (обязательство, вызов, ответ), доказывающий знание дискретного логарифма. Подпись Шнорра получается из него приёмом Фиата - Шамира: вызов $c$ заменяют на хэш $H(g, y, t, m)$, и диалог сворачивается в неинтерактивную пару чисел.

Почему протокол Шнорра считают доказательством с нулевым разглашением? Потому что существует симулятор, который строит тройку $(t, c, s)$ с тем же распределением, что и настоящий диалог, не зная секрета $x$ (выбирает $c, s$ и кладёт $t = g^s y^{-c}$). Раз правдоподобный протокол собирается без секрета, настоящий диалог секрета не выдаёт.

Где протокол Шнорра применяется на практике? Его неинтерактивная форма - подпись Шнорра - лежит в основе схемы EdDSA (Ed25519) и обновления Bitcoin Taproot, где ценят компактность подписи, простое линейное уравнение проверки и возможность агрегировать несколько подписей в одну.

Коротко

Протокол Шнорра доказывает знание дискретного логарифма $x$ публичного $y = g^x$ через диалог обязательство - вызов - ответ $(t, c, s)$ с проверкой $g^s = t \cdot y^c$. Он полон (честный всегда проходит), корректен (ответ на два вызова при одном обязательстве выдаёт секрет, значит обмануть нельзя) и нулевого разглашения (тройку подделывает симулятор без секрета). Заменив случайный вызов на хэш по Фиату - Шамиру, из протокола получают компактную подпись Шнорра - основу EdDSA и Bitcoin Taproot.