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

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

Кольцевые подписи изобрели Рон Ривест, Ади Шамир и Яэль Тауман (англ. Yael Tauman), которые представили свою разработку в 2001 году на международной конференции Asiacrypt.

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

• нет возможности отменить анонимность отдельной подписи;
• любая группа пользователей может использоваться как кольцо без дополнительной настройки.

Описание

Каждая группа участников имеет пары из открытых (приватных) и закрытых (секретных) ключей, P₁, S₁), (P₂, S₂), …, (P_n, S_n. Любой участник i может создать кольцевую подпись σ для сообщения m, используя только свой закрытый ключ и открытые ключи остальных членов группы (даже без их ведома), подав на вход функции (m, S_i, P₁, …, P_n). Любой желающий может убедиться в действительности кольцевой подписи, используя σ, m и список открытых ключей P₁, …, P_n. С другой стороны, для постороннего должно быть невозможно или крайне сложно создать кольцевую подпись для любого сообщения для любой группы, не зная ни одного из закрытых ключей участников этой группы.

Использование

Схема кольцевой подписи

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

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

Позднее появились работы, в которых были предложены новые функции и варианты применения.

Пороговые кольцевые подписи

В отличие от стандартной пороговой подписи «t-out-of-n», когда t из n пользователей должны сотрудничать для дешифрования сообщения, этот вариант кольцевой подписи требует, чтобы t пользователей сотрудничали в процессе подписания. Для этого t участников (i₁, i₂, ..., i_t) должны вычислить сигнатуру σ для сообщения m подав на вход n открытых ключей (m, S_i1, S_i2, ..., S_it, P₁, ..., P_n).

Связываемые кольцевые подписи

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

Прослеживаемая кольцевая подпись

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

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

Система CryptoNote использует кольцевые подписи. Впервые это было использовано в Bytecoin (BCN) в июле 2012 года.

Криптовалюта ShadowCash использует прослеживаемую кольцевую подпись для анонимности отправителя транзакции. Однако они были первоначально реализованы неправильно, что привело к частичной де-анонимизации ShadowCash с их первой реализации до февраля 2016 года. Правда, только 20 % всех ключей в системе были затронуты этой ошибкой, анонимность отправителя была скомпрометирована, но анонимность получателя осталась незатронутой.

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

Большинство предложенных алгоритмов имеют асимптотический размер выхода $O(n)$, то есть размер результирующей подписи увеличивается линейно с размером ввода (количества открытых ключей). Это означает, что такие схемы нецелесообразны для реальных случаев использования с достаточно большими $n$ (например, электронное голосование с миллионами участников). Но для некоторого применения с относительно небольшим средним размером ввода это может быть приемлемо. CryptoNote реализует кольцевые подписи в платежах p2p, чтобы обеспечить возможность отслеживания отправителя.

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

Реализация

Ниже приведена реализация исходного описания на языке Python с использованием RSA.

import os, hashlib, random, Crypto.PublicKey.RSA

class ring:
    def __init__(self, k, L=1024):
        self.k = k
        self.l = L
        self.n = len(k)
        self.q = 1 << (L - 1)

    def sign(self, m, z):
        self.permut(m)
        s = [None] * self.n
        u = random.randint(0, self.q)
        c = v = self.E(u) 
        for i in (range(z+1, self.n) + range(z)):
            s[i] = random.randint(0, self.q)
            e = self.g(s[i], self.k[i].e, self.k[i].n)
            v = self.E(v^e) 
            if (i+1) % self.n == 0:
                c = v
        s[z] = self.g(v^u, self.k[z].d, self.k[z].n)
        return [c] + s

    def verify(self, m, X):
        self.permut(m)
        def _f(i):
            return self.g(X[i+1], self.k[i].e, self.k[i].n)
        y = map(_f, range(len(X)-1))
        def _g(x, i):
            return self.E(x^y[i])
        r = reduce(_g, range(self.n), X[0])
        return r == X[0]

    def permut(self, m):
        self.p = int(hashlib.sha1('%s' % m).hexdigest(),16)

    def E(self, x): 
        msg = '%s%s' % (x, self.p)
        return int(hashlib.sha1(msg).hexdigest(), 16)

    def g(self, x, e, n):
        q, r = divmod(x, n)
        if ((q + 1) * n) <= ((1 << self.l) - 1):
            rslt = q * n + pow(r, e, n)
        else:
            rslt = x
        return rslt

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

size = 4
msg1, msg2 = 'hello', 'world!'

def _rn(_):
  return Crypto.PublicKey.RSA.generate(1024, os.urandom)

key = map(_rn, range(size))
r = ring(key)
for i in range(size):
    s1 = r.sign(msg1, i)
    s2 = r.sign(msg2, i)
    assert r.verify(msg1, s1) and r.verify(msg2, s2) and not r.verify(msg1, s2)