Кольцевая подпись - Ring signature

В криптография, а кольцевая подпись это тип цифровой подписи который может быть выполнен любым членом группы пользователей, у каждого из которых есть ключи. Следовательно, сообщение, подписанное кольцевой подписью, одобряется кем-то из определенной группы людей. Одно из свойств безопасности кольцевой подписи заключается в том, что определение который ключей членов группы использовались для создания подписи. Кольцевые подписи похожи на групповые подписи но отличаются двумя ключевыми способами: во-первых, нет способа отменить анонимность отдельной подписи, а во-вторых, любую группу пользователей можно использовать как группу без дополнительных настроек. Кольцевые подписи были изобретены Рон Ривест, Ади Шамир, и Яэль Тауман Калаи, и представлен на ASIACRYPT в 2001.^[1] Название, кольцевая подпись, происходит от кольцевой структуры подписи алгоритм.

Определение

Предположим, что каждая группа объектов имеет пары открытого / закрытого ключей, (п₁, S₁), (п₂, S₂), ..., (п_п, S_п). Партия я может вычислить кольцевую подпись σ для сообщения м, на входе (м, S_я, п₁, ..., п_п). Любой может проверить действительность кольцевой подписи при условии σ, м, и задействованные открытые ключи, п₁, ..., п_п. Если кольцевая подпись рассчитана правильно, она должна пройти проверку. С другой стороны, кому-либо должно быть трудно создать действительную кольцевую подпись для любого сообщения для любой группы, не зная каких-либо закрытых ключей для этой группы.^[2]

Приложения и модификации

Поведение схемы кольцевой подписи Ривест, Шамир, Тауман

В оригинальной статье Ривест, Шамир и Тауман описали кольцевые подписи как способ утечки секрета. Например, кольцевая подпись может использоваться для предоставления анонимной подписи от высокопоставленного белый дом официальный », не раскрывая, какое должностное лицо подписало сообщение. Кольцевые подписи подходят для этого приложения, поскольку анонимность кольцевой подписи не может быть отменена, и поскольку группа для кольцевой подписи может быть импровизирована.

Другое приложение, также описанное в исходной статье, предназначено для отрицательные подписи. Здесь отправитель и получатель сообщения образуют группу для кольцевой подписи, тогда подпись действительна для получателя, но кто-либо еще не будет уверен, был ли получатель или отправитель фактическим подписавшим. Таким образом, такая подпись убедительна, но не может быть передана за пределы предполагаемого получателя.

Были разные работы, вводящие новые функции и основанные на разных предположениях:

Пороговые кольцевые подписи: ^[3] В отличие от стандартного "т-снаружи-п" пороговая подпись, куда т из п пользователи должны сотрудничать, чтобы расшифровать сообщение, этот вариант кольцевой подписи требует т пользователей сотрудничать в подписании протокол. А именно, т стороны (я₁, я₂, ..., я_т) может вычислить (т, п) -кольцо сигнатуры, σ, в сообщении, м, на входе (м, S_я₁, S_я₂, ..., S_{я_т}, п₁, ..., п_п).
Связанные кольцевые подписи: ^[4] Свойство связываемости позволяет определить, были ли какие-либо две подписи созданы одним и тем же членом (под одним и тем же закрытым ключом). Тем не менее личность подписавшего сохраняется. Одним из возможных приложений может быть офлайн электронная кассовая система.
Прослеживаемая кольцевая подпись: ^[5] В дополнение к предыдущей схеме раскрывается открытый ключ подписывающей стороны (если они выдают более одной подписи под одним и тем же закрытым ключом). An система электронного голосования могут быть реализованы с использованием этого протокола.

Эффективность

Большинство предложенных алгоритмов имеют асимптотический размер вывода ${displaystyle O (n)}$ ; то есть размер результирующей подписи увеличивается линейно с размером ввода (количества открытых ключей). Это означает, что такие схемы неприменимы для реальных случаев использования с достаточно большими ${displaystyle n}$ (например, электронное голосование с миллионами участников). Но для некоторых приложений с относительно небольшими медиана размер ввода такая оценка может быть приемлемой. CryptoNote орудия ${displaystyle O (n)}$ схема кольцевой подписи от Fujisaki и Suzuki^[5] в p2p-платежах, чтобы избежать отслеживания отправителя.

В последнее время появились более эффективные алгоритмы. Есть схемы с сублинейным размером подписи,^[6] а также с постоянным размером.^[7]

Выполнение

Оригинальная схема

В исходной статье описывается ЮАР схема на основе кольцевой подписи, а также схема на основе Подписи Рабина. Они определяют ключ "функция комбинирования" ${displaystyle C_ {k, v} (y_ {1}, y_ {2}, dots, y_ {n})}$ который берет ключ ${displaystyle k}$ , значение инициализации ${displaystyle v}$ , и список произвольных значений ${displaystyle y_ {1}, точки y_ {n}}$ . Он выводит одно значение ${displaystyle z}$ . Уравнение ${displaystyle C_ {k, v} (y_ {1}, y_ {2}, dots, y_ {n})}$ разрешимо для любого отдельного входа, но невозможно решить ${displaystyle C_ {k, v} (g_ {1} (x_ {1}), g_ {2} (x_ {2}), точки, g_ {n} (x_ {n}))}$ за ${displaystyle x_ {1}, x_ {2}, dots, x_ {n}}$ если злоумышленник не может инвертировать какой-либо из (здесь на основе RSA) люк функции ${displaystyle g_ {1}, g_ {2}, dots, g_ {n}}$ . Функция ${displaystyle C_ {k, v} (y_ {1}, y_ {2}, dots, y_ {n})}$ называется уравнением кольца и определяется ниже. Уравнение основано на функция симметричного шифрования ${displaystyle E_ {k}}$ :

{displaystyle C_ {k, v} (y_ {1}, y_ {2}, dots, y_ {n}) = E_ {k} (y_ {n} oplus E_ {k} (y_ {n-1} oplus E_ {k} (точки oplus E_ {k} (y_ {1} oplus v) точки))) = v}

В схеме кольцевой подписи на выходе ${displaystyle v}$ совпадает с входом. Эта функция тривиально обратима, если ${displaystyle n-1}$ параметры.

Генерация подписи

Генерация кольцевой подписи включает шесть шагов. Открытый текст обозначается ${displaystyle m}$ , открытые ключи кольца ${displaystyle P_ {1}, P_ {2}, точки, P_ {n}}$ .

Рассчитать ключ ${displaystyle k = {mathcal {H}} (m)}$ , используя криптографическая хеш-функция. Этот шаг предполагает случайный оракул за ${displaystyle {mathcal {H}}}$ , поскольку ${displaystyle k}$ будет использоваться как ключ для ${displaystyle E_ {k}}$ .
Выберите случайное значение клея ${displaystyle v}$ .
Выбрать случайный ${displaystyle x_ {i}}$ для всех участников кольца, кроме себя ( ${displaystyle x_ {s}}$ будет рассчитываться с использованием sзакрытый ключ igner) и вычислить соответствующий ${displaystyle y_ {i} = g_ {i} (x_ {i})}$ .
Решите уравнение кольца для ${displaystyle y_ {s}}$
Рассчитать ${displaystyle x_ {s}}$ используя закрытый ключ подписывающей стороны: ${displaystyle x_ {s} = g_ {s} ^ {- 1} (y_ {s})}$
Кольцевая подпись теперь - ${displaystyle (2n + 1)}$ пара ${displaystyle (P_ {1}, P_ {2}, dots, P_ {n}; v; x_ {1}, x_ {2}, dots, x_ {n})}$

Проверка подписи

Проверка подписи включает три этапа.

Применить люк открытого ключа ко всем ${displaystyle x_ {i}}$ : ${displaystyle y_ {i} = g_ {i} (x_ {i})}$ .
Вычислить симметричный ключ ${displaystyle k = {mathcal {H}} (m)}$ .
Убедитесь, что уравнение кольца выполнено ${displaystyle C_ {k, v} (y_ {1}, y_ {2}, dots, y_ {n}) = v}$ .

Реализация Python

Вот Python реализация оригинальной статьи с использованием ЮАР.

импорт Операционные системы, хэшлиб, случайный, Крипто.Публичный ключ.RSAучебный класс Звенеть:    "" "Реализация RSA." ""    def __в этом__(себя, k, L: int = 1024) -> Никто:        себя.k = k        себя.л = L        себя.п = len(k)        себя.q = 1 << (L - 1)    def знак(себя, м: ул, z: int):        "" "Подпишите сообщение." ""        себя._пермут(м)        s = [Никто] * себя.п        ты = случайный.Randint(0, себя.q)        c = v = себя._E(ты)        за я в классифицировать(z + 1, себя.п) + классифицировать(z):            s[я] = случайный.Randint(0, себя.q)            е = себя._грамм(s[я], себя.k[я].е, себя.k[я].п)            v = себя._E(v ^ е)            если (я + 1) % себя.п == 0:                c = v        s[z] = себя._грамм(v ^ ты, себя.k[z].d, себя.k[z].п)        возвращаться [c] + s    def проверять(себя, м: ул, Икс) -> bool:        "" "Проверить сообщение." ""        себя._пермут(м)        def _f(я):            возвращаться себя._грамм(Икс[я + 1], себя.k[я].е, себя.k[я].п)        у = карта(_f, классифицировать(len(Икс) - 1))        def _грамм(Икс, я):            возвращаться себя._E(Икс ^ у[я])        р = уменьшать(_грамм, классифицировать(себя.п), Икс[0])        возвращаться р == Икс[0]    def _пермут(себя, м):        себя.п = int(хэшлиб.sha1("% s" % м).hexdigest(), 16)    def _E(себя, Икс):        сообщение = "%SS" % (Икс, себя.п)        возвращаться int(хэшлиб.sha1(сообщение).hexdigest(), 16)    def _грамм(себя, Икс, е, п):        q, р = divmod(Икс, п)        если ((q + 1) * п) <= ((1 << себя.л) - 1):            результат = q * п + пау(р, е, п)        еще:            результат = Икс        возвращаться результат

Чтобы подписать и проверить 2 сообщения в кольце из 4 пользователей:

размер = 4msg1, msg2 = "Привет", "Мир!"def _rn(_):    возвращаться Крипто.PublicKey.ЮАР.генерировать(1024, Операционные системы.случайный)ключ = карта(_rn, классифицировать(размер))р = Звенеть(ключ)за я в классифицировать(размер):    s1 = р.знак(msg1, я)    s2 = р.знак(msg2, я)    утверждать р.проверять(msg1, s1) и р.проверять(msg2, s2) и нет р.проверять(msg1, s2)

Криптовалюты

В CryptoNote технология использует кольцевые подписи.^[8] Впервые он был реализован Bytecoin.

ShadowCash

Криптовалюта ShadowCash использует отслеживаемую кольцевую подпись, чтобы анонимизировать отправителя транзакции.^[9] Однако изначально они были реализованы неправильно, что привело к частичной деанонимизации ShadowCash с момента их первой реализации до февраля 2016 г. Монеро Исследователь исследовательских лабораторий Шен Нётер.^[10] К счастью, только 20% всех одноразовых ключей в системе были затронуты этой ошибкой, анонимность отправителя была нарушена, но анонимность получателя осталась неизменной. Своевременно был отправлен патч для устранения ошибки.^[11]

Монеро

В период с 10 января 2017 года по 18 октября 2018 года Monero использовала технологию Ring Confidential Transaction, чтобы скрыть суммы транзакций в блокчейне. Это позволяло только отправителю и получателю средств узнать истинное количество отправленных средств.^[12] С тех пор валюта перешла на Bulletproofs.^[13]