Кольцевые подписи

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

История

Концепция кольцевых подписей была впервые предложена в 2001 году группой исследователей: Роном Ривестом, Ади Шамиром и Яэль Тауман. Изначально механизм был разработан для решения проблемы анонимного раскрытия секретной информации (так называемых «утечек»). Идея возникла как развитие схем групповых подписей, но с существенным отличием: в кольцевых подписях не требуется центральный администратор, который управляет составом группы и может отозвать анонимность.

Первая реализация, известная как схема Ривеста-Шамира-Тауман (RST), основывалась на комбинации симметричного шифрования и асимметричных криптосистем, например RSA. В 2002 году была предложена более эффективная схема на основе эллиптических кривых, а в 2006 году — схема, использующая спаривания (pairing-based cryptography). С развитием технологии блокчейн и криптовалют, начиная с 2010-х годов, кольцевые подписи получили второе рождение, став ключевым элементом анонимных платёжных систем.

Принцип работы

Кольцевая подпись строится на основе набора открытых ключей участников кольца и одного секретного ключа реального подписанта. Процесс создания подписи включает несколько этапов:

1. Формирование кольца. Подписант выбирает произвольный набор открытых ключей (включая свой собственный). Количество ключей может варьироваться от двух до нескольких тысяч.
2. Генерация «зацепки» (ring). Используя свой секретный ключ, подписант создаёт цепочку вычислений, которая «замыкается» в кольцо. Каждый шаг цепочки использует один из открытых ключей, но только для одного из них (секретного) подписант знает соответствующее значение.
3. Вычисление подписи. Результатом является компактная структура данных, включающая само сообщение, список открытых ключей и математическое доказательство (обычно — значение хеш-функции и набор чисел).

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

Свойства

Кольцевые подписи обладают тремя основными свойствами, которые отличают их от других криптографических схем:

• Анонимность. Для стороннего наблюдателя (включая других участников кольца) вероятность того, что подпись создана конкретным участником, не превышает 1/N, где N — размер кольца. Это свойство сохраняется даже в случае компрометации всех остальных секретных ключей кольца.
• Невозможность подделки. Злоумышленник, не знающий ни одного секретного ключа из кольца, не может создать действительную кольцевую подпись от имени этого кольца. Стойкость основана на вычислительной сложности задач дискретного логарифмирования или факторизации.
• Независимость участников. Для создания подписи не требуется согласия или участия других членов кольца. Подписант может использовать любые открытые ключи, включая ключи лиц, которые никогда не давали на это разрешения.

Классификация

Кольцевые подписи классифицируются по нескольким признакам:

По типу используемой криптосистемы

• На основе RSA. Классическая схема RST, использующая асимметричное шифрование. Размер подписи линейно зависит от размера кольца.
• На основе эллиптических кривых (EC-ring). Более эффективные схемы, обеспечивающие меньший размер подписи и более высокую скорость вычислений. Пример — схема, используемая в криптовалюте Monero.
• На основе спариваний (bilinear pairings). Позволяют создавать кольцевые подписи с постоянным размером, не зависящим от числа участников, но требуют более сложных математических операций.

По размеру кольца

• Фиксированные. Размер кольца задаётся до создания подписи и не может быть изменён.
• Динамические. Позволяют добавлять или удалять участников кольца уже после создания подписи, хотя это свойство реализовано лишь в нескольких экспериментальных схемах.

По дополнительным свойствам

• С возможностью связывания (linkable ring signatures). Позволяют определить, что две подписи были созданы одним и тем же участником (без раскрытия его личности). Используются в системах электронного голосования для предотвращения двойного голосования.
• С возможностью отзыва анонимности (traceable ring signatures). Дают возможность специальному арбитру (например, суду) раскрыть личность подписанта при определённых условиях. Применяются в системах, где требуется баланс между анонимностью и подотчётностью.

Применение

Криптовалюты и блокчейн

Наиболее известное применение кольцевых подписей — криптовалюта Monero (XMR). В Monero кольцевые подписи используются для сокрытия отправителя транзакции. Каждая транзакция подписывается кольцом, состоящим из реального входа транзакции и нескольких «декоративных» входов из истории блокчейна. Размер кольца в Monero по умолчанию составляет 16 участников, что обеспечивает высокий уровень анонимности.

Другие криптовалюты, использующие кольцевые подписи: Dash (частично, в функции PrivateSend), а также некоторые проекты на платформе Ethereum, реализующие анонимные смарт-контракты.

Электронное голосование

Кольцевые подписи позволяют создать систему голосования, в которой каждый избиратель доказывает, что он является членом избирательного списка, но его голос остаётся анонимным. Связываемые кольцевые подписи (linkable) дополнительно предотвращают повторное голосование: если один участник попытается проголосовать дважды, система обнаружит, что обе подписи созданы одним и тем же лицом, но не раскроет его личность.

Анонимное раскрытие информации

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

Защита конфиденциальности в децентрализованных системах

В децентрализованных приложениях (dApps) кольцевые подписи используются для аутентификации пользователей без раскрытия их идентичности. Например, в системах децентрализованного управления (DAO) участник может подписать предложение, доказывая, что он является держателем токенов, но не раскрывая свой адрес.

Критика и ограничения

Несмотря на преимущества, кольцевые подписи имеют ряд недостатков:

• Рост размера подписи. В большинстве схем размер подписи линейно зависит от размера кольца. Для кольца из 1000 участников подпись может занимать десятки килобайт, что создаёт нагрузку на сеть и хранилище.
• Вычислительная сложность. Верификация кольцевой подписи требует выполнения операций с каждым открытым ключом в кольце, что замедляет обработку транзакций по сравнению с обычными цифровыми подписями.
• Уязвимость к атакам на анонимность. Если злоумышленник контролирует большинство участников кольца (например, в криптовалюте — создаёт множество «декоративных» входов), он может с высокой вероятностью определить реального подписанта. Для противодействия этому в Monero используется механизм принудительного выбора декоративных входов из случайных транзакций.
• Отсутствие стандартизации. В отличие от схем ЭЦП (например, ECDSA или EdDSA), кольцевые подписи не имеют общепринятых стандартов (ISO, RFC), что затрудняет их внедрение в коммерческие и государственные системы.

Сравнение с другими схемами анонимных подписей

Интересные факты

• Термин «кольцевая подпись» (ring signature) был предложен Ривестом, Шамиром и Тауман в честь математического понятия «кольцо» (ring), а также из-за того, что алгоритм создания подписи напоминает замыкание цепочки в кольцо.
• Первая статья о кольцевых подписях была опубликована в 2001 году, но практическое применение в криптовалютах началось только через 13 лет, с запуском Monero в 2014 году.
• В 2019 году исследователи из Массачусетского технологического института (MIT) предложили схему кольцевых подписей на основе квантово-устойчивых криптосистем, что делает их потенциально применимыми в эпоху квантовых компьютеров.

Источники

• Rivest, R. L., Shamir, A., & Tauman, Y. (2001). How to Leak a Secret. Advances in Cryptology — ASIACRYPT 2001.
• Bender, A., Katz, J., & Morselli, R. (2006). Ring Signatures: Stronger Definitions, and Constructions without Random Oracles. Journal of Cryptology.
• Noether, S. (2015). Ring Signature Confidential Transactions. Monero Research Lab.
• Liu, J. K., & Wong, D. S. (2005). Linkable Ring Signatures: Security Models and New Schemes. International Conference on Computational Science and Its Applications.