Протоколы Сигмы и идентификация Шнорра

Сигма-протокол содержит 3 сообщения: (1) Фиксация: доказывающий отправляет коммитмент случайного значения. (2) Вызов: проверяющий отправляет случайный вызов. (3) Ответ: доказывающий отправляет ответ, вычисленный на основе вызова и секрета. Проверяющий принимает или отклоняет доказательство.

Доказывающий знает секрет x (закрытый ключ); открытый ключ = g^x по модулю p (или точка X = x*G на эллиптической кривой). Цель — доказать знание x, не раскрывая его. Это доказательство знания дискретного логарифма.

(1) Доказывающий выбирает случайное r и отправляет коммитмент R = r*G. (2) Проверяющий отправляет вызов c (случайное целое число). (3) Доказывающий отправляет ответ s = r + c*x. (4) Проверяющий проверяет s*G == R + c*X. Если равенство выполнено, он принимает доказательство. Доказывающий знает x; ответ s можно вычислить только зная x.

Полнота: честный доказывающий всегда удовлетворяет равенству s*G = r*G + c*x*G = R + c*X. Состоятельность: из двух транскриптов с одним и тем же R, но разными вызовами c и c', получаются s и s', из которых можно восстановить x = (s-s')/(c-c'), — поэтому мошенник не может создать два допустимых ответа для одного R.

Симулятор (не знающий x): выбирает случайные s и c, задаёт R = s*G - c*X. Получившийся набор (R, c, s) имеет распределение допустимого транскрипта. Проверяющий не может отличить реальные транскрипты от смоделированных — протокол Schnorr обладает нулевым разглашением для честного проверяющего.

Сделаем протокол Schnorr неинтерактивным: заменим вызов проверяющего на c = хеш(R || сообщение). Доказывающий самостоятельно вычисляет c и отправляет ответ. Результат: двухэлементное доказательство (R, s), которое может проверить любой. Это схема подписи Schnorr.

Подписать(x, m): r ← случайное значение; R = r*G; c = хеш(R||m); s = r + c*x. Подпись = (R, s). Проверить: s*G == R + хеш(R||m)*X. Компактная (64 байта для P-256), допускает пакетную проверку и доказуемо безопасна в ROM. Применяется в Bitcoin Taproot (BIP-340).

C = r*G + v*H, где H — второй независимый генератор. Коммитмент фиксирует значение v с использованием случайности r. Связывающее свойство: невозможно раскрыть коммитмент для другого v (из-за дискретного логарифма). Скрывающее свойство: C распределено равномерно. Используется в доказательствах диапазона на основе Schnorr и Bulletproofs.

Доказать одновременное знание x1 AND x2 можно, запустив два протокола Schnorr с одним и тем же вызовом (вызов передаётся через Fiat-Shamir). Проверяющий принимает доказательство только в том случае, если оба поддоказательства допустимы. Это позволяет доказывать несколько утверждений за одно взаимодействие.

Доказать знание x1 OR x2, не раскрывая, какого именно, можно следующим образом: использовать симулятор для одной ветви, чтобы вычислить поддельный транскрипт, а затем разделить вызов между обеими ветвями. Проверяющий видит два похожих на допустимые транскрипта, сумма вызовов которых равна настоящему вызову. Такие доказательства называют «кольцевыми подписями».

Идентификация Schnorr: электронные паспорта (протокол PACE). Подписи Schnorr: Bitcoin Taproot, Monero (RingCT использует доказательства OR на основе Schnorr), протокол Signal (согласование ключей X3DH). Коммитменты Pedersen: конфиденциальные транзакции, Bulletproofs, шифрование записей Zcash Sapling.

Что проверяющий проверяет на последнем шаге протокола идентификации Schnorr?

Сигма-протоколы: фиксация — вызов — ответ. Schnorr доказывает знание дискретного логарифма. Fiat-Shamir делает протокол неинтерактивным (подпись Schnorr). Далее: zk-SNARK для кратких неинтерактивных доказательств.