Кольцевая подпись¶

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

¶История

Концепция кольцевой подписи была впервые предложена в 2001 году группой криптографов: Роном Ривестом, Ади Шамиром и Яэль Тауман. В своей работе «How to Leak a Secret» они описали схему, позволяющую одному человеку публично раскрыть секрет, сохраняя анонимность. Основной мотивацией стало создание механизма для безопасного слива информации (whistleblowing), при котором источник не может быть идентифицирован, но подпись гарантирует, что сообщение исходит от члена определённой группы (например, сотрудников компании или правительства).

Первоначальная схема Ривеста-Шамира-Тауман была построена на основе алгоритма RSA и использовала комбинацию асимметричного шифрования и хеш-функций. Впоследствии были разработаны варианты на основе эллиптических кривых, дискретного логарифмирования и других криптографических примитивов.

¶Определение и свойства

Кольцевая подпись обладает следующими ключевыми свойствами:

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

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

¶Схема работы

Общая схема кольцевой подписи включает три алгоритма:

1. Генерация ключей: каждый участник генерирует пару ключей (секретный и публичный) с использованием стандартных криптографических алгоритмов (например, RSA, ECDSA, EdDSA).
2. Создание подписи: подписант выбирает набор из \(n\) публичных ключей (включая свой), формирует кольцо. Затем он использует свой секретный ключ и публичные ключи остальных участников для вычисления подписи, которая не раскрывает его личность. Процесс обычно включает комбинацию хеширования, шифрования и решения системы уравнений (например, в схеме Ривеста-Шамира-Тауман — это решение полиномиального уравнения).
3. Верификация: проверяющий, зная только сообщение, подпись и набор публичных ключей кольца, может убедиться, что подпись создана одним из владельцев этих ключей, но не может определить, каким именно.

¶Виды кольцевых подписей

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

• Классическая кольцевая подпись (Rivest-Shamir-Tauman): основана на RSA, обеспечивает анонимность и неподделываемость.
• Кольцевая подпись на основе эллиптических кривых: использует ECDSA или EdDSA, более эффективна по размеру подписи и скорости вычислений.
• Связываемая кольцевая подпись (linkable ring signature): позволяет проверить, были ли две подписи созданы одним и тем же участником кольца (без раскрытия его личности). Используется в системах электронных голосований и криптовалютах для предотвращения двойных трат.
• Кольцевая подпись с отслеживанием (traceable ring signature): позволяет при определённых условиях (например, при наличии специального ключа) раскрыть личность подписанта. Применяется в системах с контролем доступа.
• Кольцевая подпись с пороговым доступом (threshold ring signature): подпись действительна, если её создала коалиция из \(t\) участников кольца.

¶Применение

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

• Защита конфиденциальности при сливе информации: как в исходной работе Ривеста-Шамира-Тауман, кольцевые подписи позволяют источнику подтвердить, что он является членом определённой организации, не раскрывая свою личность.
• Криптовалюты и блокчейн: кольцевые подписи используются в криптовалюте Monero для обеспечения анонимности транзакций. В Monero применяется связываемая кольцевая подпись (RingCT), которая скрывает отправителя и сумму перевода, но позволяет проверять отсутствие двойных трат.
• Электронные голосования: связываемые кольцевые подписи позволяют избирателю подтвердить, что он является членом избирательного списка, и проголосовать анонимно, при этом система может проверить, что каждый избиратель проголосовал только один раз.
• Децентрализованные системы: в протоколах консенсуса и децентрализованных приложениях (dApps) кольцевые подписи используются для анонимного подтверждения членства в группе.
• Безопасность сообщений: в системах анонимной переписки (например, Whisper, Signal) кольцевые подписи могут применяться для подтверждения авторства сообщения без раскрытия отправителя.

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

Основные недостатки кольцевых подписей связаны с их размером и вычислительной сложностью. Размер подписи обычно линейно зависит от размера кольца (\(O(n)\)), что делает их неэффективными для больших групп. В криптовалюте Monero, например, размер кольца ограничен (обычно 10–16 участников) для поддержания приемлемой производительности. Кроме того, классические схемы кольцевых подписей не обеспечивают устойчивости к квантовым атакам, хотя существуют постквантовые варианты на основе решёток.

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

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

• Термин «кольцевая подпись» происходит от того, что в схеме Ривеста-Шамира-Тауман подпись образует замкнутый цикл (кольцо) вычислений, где каждый участник «замыкает» цепочку.
• В 2014 году исследователи из Массачусетского технологического института (MIT) предложили схему кольцевой подписи на основе эллиптических кривых, которая уменьшает размер подписи до \(O(\log n)\).
• Кольцевые подписи являются одним из ключевых компонентов криптовалюты Monero (XMR), которая признана анонимной и используется в различных юрисдикциях, включая Россию, где оборот криптовалют не запрещён, но подлежит регулированию.

¶Источники

• 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.
• Monero Research Lab. (2017). Ring Confidential Transactions. Ledger.
• Liu, J. K., & Wong, D. S. (2005). Linkable Ring Signatures: Security Models and New Schemes. International Conference on Computational Science and Its Applications.