Кольцевая подпись (Tkl,eyfgx hk;hnv,)

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

Математический алгоритм кольцевой подписи разработали Рональд Ривест, Ади Шамир и Яэль Тауман (англ. Yael Tauman), представив в 2001 году на международной конференции Asiacrypt^[англ.]^[1]. По утверждению авторов, они старались в названии подчеркнуть отсутствие центральной или координирующей структуры при формировании такой подписи: «…кольца представляют собой геометрические фигуры с однородной периферией и без центра».

История

Идея групповой подписи под прошениями или жалобами, подтверждающей, что все подписанты поддерживают обращение, но не позволяющей выявить её автора или инициатора, берёт начало в прошлом. Так, английский термин «round-robin» известен с XVII столетия и обозначает петицию, которую подписывали по кругу без соблюдения иерархии, чтобы избежать наказания для подписавшегося первым^[2], — своеобразный вариант круговой поруки. В 1898 году после осады города Сантьяго-де-Куба во время испано-американской войны высокопоставленные офицеры 5-го армейского корпуса подписали по кругу письмо в штаб-квартиру армии в Вашингтоне с требованием вернуть корпус в Соединённые Штаты для лечения и отдыха. Письмо попало в прессу и получило широкую известность, а также вызвало резонанс в правительстве президента Мак-Кинли^[3].

Множественная подпись стала электронным аналогом бумажной подписи по кругу. В 1991 году Дэвид Чом и Юджин ван Хейст (англ. Eugene Van Heyst) предложили схему групповой подписи^[1], где подписантом является кто-то из членов группы, которую сформировал администратор. Проверяющий может убедиться, что подписант член группы, но не может узнать, кто именно. При этом администратор имеет возможность идентифицировать подписанта^[4].

Кольцевые подписи, по существу, схожи с групповыми, но, в отличие от последних, нет возможности установления личности подписанта, нет администратора или координатора. Все члены списка, за исключением самого подписанта, могут не знать ни содержания сообщения, ни даже факта использования их открытого ключа для формирования кем-то кольцевой подписи^[1].

Общее описание механизма создания и проверки кольцевой подписи

Предполагается, что существует некий перечень, где указана однозначная связь человека с его открытым (публичным) ключом (например, сервер криптографических ключей). Причина появления открытого ключа в этом перечне не имеет значения. Например, человек мог создать ключи RSA только для покупок через Интернет и может совершенно не знать, что его открытые ключи используются кем-то для создания кольцевой подписи на сообщении, которое он никогда не видел и не хотел подписывать^[1]. Общий алгоритм кольцевой подписи допускает одновременное использование открытых ключей, сформированных разными системами (алгоритмами), в том числе имеющими разные размеры как ключей, так и подписей^[1].

При создании кольцевой подписи для сообщения m подписывающий по своему усмотрению формирует список из открытых ключей (P₁, P₂, …, P_n), в который включает и свой под номером i (его порядковый номер в списке не имеет значения). Всё это вместе с секретным ключом подписывающего S_i как параметры подаётся на вход функции наложения подписи (m, S_i, P₁, …, P_n), получая на выходе результат σ. Хотя каждому открытому ключу из списка соответствует свой уникальный закрытый ключ и используется только один из них (принадлежащий подписывающему), но по получившейся подписи невозможно узнать, какой именно из закрытых ключей использовался при её создании. Даже имея неограниченное число кольцевых подписей, выполненных одним и тем же подписантом, нет возможности его идентифицировать или хотя бы гарантированно установить, что некоторые подписи были наложены с использованием одного и того же закрытого ключа^[1].

Подлинность кольцевой подписи можно проверить, используя σ, m и только открытые ключи P₁, …, P_n^[5].

Варианты реализации

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

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

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

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

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

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

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

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

В дополнение к связываемой подписи при повторном использовании может раскрываться открытый ключ подписанта. Такой протокол позволяет реализовать системы тайного электронного голосования, которые позволяют поставить анонимно только одну подпись, но раскрывают участника, проголосовавшего дважды^[10].

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

Система CryptoNote допускает кольцевые подписи^[11]. Впервые это было использовано в июле 2012 года в криптовалюте Bytecoin^[12]^[13] (не путать с Bitcoin).

Криптовалюта ShadowCash использует прослеживаемую кольцевую подпись для анонимности отправителя транзакции^[14]. Однако первоначальная реализация была ошибочной, что привело к частичной деанонимизации ShadowCash с первой реализации до февраля 2016 года^[15].

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

Большинство предложенных алгоритмов имеют асимптотический размер результата $O(n)$ , то есть размер результирующей подписи прямо пропорционален количеству использованных открытых ключей. Каждый использованный открытый ключ при наложении или проверке кольцевой подписи требует фиксированного объёма вычислений, что значительно лучше аналогов, имевшихся на момент создания протокола^[1]. Например, технология CryptoNote реализует кольцевые подписи в платежах p2p, чтобы обеспечить анонимность отправителя^[10].

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

Алгоритм

Суть алгоритма кольцевой подписи, предложенной Ривестом, Шамиром и Тауман, состоит в следующем^[1] (см. рисунок схемы).

Кольцевая подпись для некоторого сообщения будет сформирована на основе списка из $r$ открытых ключей (обозначены на схеме как $pk_{1},\ldots ,pk_{r}$ ), среди которых ключ подписывающего имеет порядковый номер $s$ . Открытые ключи позволяют зашифровать произвольную информацию (информационный блок $x_{1}$ , зашифрованный ключом $pk_{1}$ , обозначен на схеме как $\mathrm {Enc} _{pk_{1}}(x_{1})$ ). «Информационные блоки» здесь и далее не являются частью или результатом обработки подписываемого сообщения и не имеют самостоятельного значения, это сгенерированные случайные данные, становящиеся компонентами подписи.

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

В качестве комбинационной функции авторы алгоритма предложили следующую последовательность действий: берётся некоторое стартовое значение (на схеме обозначено $v$ , формируется случайно), над которым и первым аргументом выполняется побитовое исключающее «или» (обозначено на схеме символом $\oplus$ ). Затем к результату применяется определённое обратимое преобразование (обозначенное на схеме как $E_{\sigma }$ ), взаимно однозначно связанное с хеш-суммой подписываемого сообщения. Полученный результат участвует в операции побитового исключающего «или» со вторым аргументом, снова применяется преобразование $E_{\sigma }$ и так далее. В качестве аргументов используются зашифрованные открытыми ключами соответствующие информационные блоки $x_{1},\ldots ,x_{r}$ .

Выбранное случайное значение $v$ является одновременно и стартовым, и целевым (конечным) значением комбинационной функции: результат всех преобразований должен «пройти по кольцу» и стать равным начальному значению. Информационные блоки $x_{1},\ldots ,x_{r}$ для каждого из ключей, кроме блока $x_{s}$ , соответствующего ключу самого подписывающего, задаются как случайные значения. Подписывающий шифрует информационные блоки соответствующими открытыми ключами. Теперь у подписывающего имеется целевое значение комбинационной функции и все аргументы, кроме одного — того, что соответствует его собственному ключу. Благодаря свойствам комбинационной функции, подписывающий может узнать недостающий аргумент и, использовав собственный закрытый ключ ( $sk_{s}$ ), «расшифровать» этот аргумент ( $\mathrm {Dec} _{sk_{s}}$ ), получив недостающий информационный блок $x_{s}$ .

Компоненты готовой кольцевой подписи^[1]:

подписываемое сообщение;
список всех использованных открытых ключей;
значения всех информационных блоков $x_{1},\ldots ,x_{r}$ ;
значение комбинационной функции $v$ .

Для проверки подписи нужно^[1]:

при помощи открытых ключей зашифровать информационные блоки;
при помощи хеш-суммы подписываемого сообщения вычислить значение комбинационной функции, использовав как аргументы $v$ (задающее стартовое значение) и зашифрованные информационные блоки (результаты предыдущего шага);
убедиться, что полученное значение совпадает с $v$ .

Пример реализации

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

import os
import hashlib
import random
import 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 = 'hello'
msg2 = '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)

Примечания

↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ ¹² Ronald L. Rivest, Adi Shamir, Yael Tauman. How to leak a secret // Advances in Cryptology — ASIACRYPT 2001 / C. Boyd (ed.). — Berlin, Heidelberg : Springer-Verlag, 2001. — P. 552—565. — (Lecture Notes in Computer Science^[англ.]. Vol. 2248).
↑ И. Ю. Павловская. Фоносемантический анализ речи. — СПб.: Изд-во Санкт-Петербургского университета, 2001. — 290 с.
↑ Historical Dictionary of the Spanish American War / Donald H. Dyal, Brian B. Carpenter and Mark A. Thomas, eds. — Westport, Conn.: Greenwood Press, 1996.
↑ B. Schneier. Applied Cryptography (англ.). — New York: John Wiley & Sons, 1996. — P. 98.
↑ Debnath A., Singaravelu P., Verma, S. Efficient spatial privacy preserving scheme for sensor network // Central European Journal of Engineering^[англ.]. — 2013. — Vol. 3, no. 1. — P. 1—10. — doi:10.2478/s13531-012-0048-7.
↑ Lingling Wang, Guoyin Zhang, Chunguang Ma. A survey of ring signature // Frontiers of Electrical and Electronic Engineering in China. — 2008. — Vol. 3, no. 1. — P. 10—19. — doi:10.1007/s11460-008-0012-8.
↑ Hu Xiong, Zhiguang Qin, Fagen Li. A Taxonomy of Ring Signature Schemes: Theory and Applications // IETE Journal of Research. — 2013. — Vol. 59, no. 4. — P. 376—382. — doi:10.4103/03772063.2013.10876518.
↑ Bresson E., Stern J., Szydlo M. Threshold ring signatures and applications to ad-hocgroups // Advances in Cryptology: CRYPTO 2002 / Moti Yung. — Berlin, Heidelberg, Ney York, Barcelona, Hong Kong, London, Milan, Paris, Tokyo : Springer, 2002. — P. 465—480. — (Lecture Notes in Computer Science^[англ.]. Vol. 2442). — doi:10.1007/3-540-45708-9_30.
↑ Liu J. K., Wong D. S. Linkable ring signatures: Security models and new schemes // Computational Science and Its Applications — ICCSA 2005. — Berlin; New York : Springer, 2005. — Vol. 2. — P. 614—623. — (Lecture Notes in Computer Science^[англ.]. Vol. 3481). — doi:10.1007/11424826_65.
↑ ¹ ² Fujisaki E., Suzuki K. Traceable Ring Signature // Public Key Cryptography — PKC 2007. — Berlin; Heidelberg; New York : Springer, 2007. — P. 181—200. — (Lecture Notes in Computer Science^[англ.]. Vol. 4450).
↑ CryptoNote Phylosophy (неопр.). CryptoNoteTech. Дата обращения: 24 ноября 2017. Архивировано 24 ноября 2017 года.
↑ CryptoNote Currencies (англ.) (2015). Дата обращения: 29 ноября 2017. Архивировано 13 июля 2017 года.
↑ CryptoNote — убийца Bitcoin? (неопр.) (23 июня 2014). Дата обращения: 29 ноября 2017. Архивировано 1 декабря 2017 года.
↑ Rynomster, Tecnovert. ShadowCash: Zeroknowledge Anonymous Distributed ECash via Traceable Ring Signatures (англ.) (pdf). www.shadow.cash (2015). Архивировано из оригинала 1 декабря 2017 года.
↑ Crypto Fun. Broken Crypto in Shadowcash (англ.) (13 февраля 2016). Дата обращения: 29 ноября 2017. Архивировано 27 сентября 2016 года.
↑ Fujisaki E. Sublinear size traceable ring signatures without random oracles // Topics in Cryptology — CT-RSA 2011. — Heidelberg; Dordrecht; London; New York : Springer, 2011. — P. 393—415. — (Lecture Notes in Computer Science^[англ.]. Vol. 6558).
↑ Au, Man Ho; Liu J. K.; Susilo W.; Yuen, Tsz Hon. Constant-Size ID-Based Linkable and Revocable-iff-Linked Ring Signature // Progress in Cryptology — INDOCRYPT 2006. — Heidelberg; Dordrecht; London; New York : Springer, 2006. — P. 364—378. — (Lecture Notes in Computer Science^[англ.]. Vol. 4329).

Литература

Чикишев Г. О. Одноразовая кольцевая подпись и её применение в электронной наличности // Прикладная дискретная математика». — 2012. — № 5. — С. 56—58. — Приложение.
Запечников С. В. и другие. Кольцевые подписи и их приложения в Энциклопедии теоретической и прикладной криптографии, МИФИ

[Asiacrypt-1] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ ¹² Ronald L. Rivest, Adi Shamir, Yael Tauman. How to leak a secret // Advances in Cryptology — ASIACRYPT 2001 / C. Boyd (ed.). — Berlin, Heidelberg : Springer-Verlag, 2001. — P. 552—565. — (Lecture Notes in Computer Science^[англ.]. Vol. 2248).

[2] И. Ю. Павловская. Фоносемантический анализ речи. — СПб.: Изд-во Санкт-Петербургского университета, 2001. — 290 с.

[3] Historical Dictionary of the Spanish American War / Donald H. Dyal, Brian B. Carpenter and Mark A. Thomas, eds. — Westport, Conn.: Greenwood Press, 1996.

[eng_second-4] B. Schneier. Applied Cryptography (англ.). — New York: John Wiley & Sons, 1996. — P. 98.

[5] Debnath A., Singaravelu P., Verma, S. Efficient spatial privacy preserving scheme for sensor network // Central European Journal of Engineering^[англ.]. — 2013. — Vol. 3, no. 1. — P. 1—10. — doi:10.2478/s13531-012-0048-7.

[survey2008-6] Lingling Wang, Guoyin Zhang, Chunguang Ma. A survey of ring signature // Frontiers of Electrical and Electronic Engineering in China. — 2008. — Vol. 3, no. 1. — P. 10—19. — doi:10.1007/s11460-008-0012-8.

[taxonomy2013-7] Hu Xiong, Zhiguang Qin, Fagen Li. A Taxonomy of Ring Signature Schemes: Theory and Applications // IETE Journal of Research. — 2013. — Vol. 59, no. 4. — P. 376—382. — doi:10.4103/03772063.2013.10876518.

[8] Bresson E., Stern J., Szydlo M. Threshold ring signatures and applications to ad-hocgroups // Advances in Cryptology: CRYPTO 2002 / Moti Yung. — Berlin, Heidelberg, Ney York, Barcelona, Hong Kong, London, Milan, Paris, Tokyo : Springer, 2002. — P. 465—480. — (Lecture Notes in Computer Science^[англ.]. Vol. 2442). — doi:10.1007/3-540-45708-9_30.

[9] Liu J. K., Wong D. S. Linkable ring signatures: Security models and new schemes // Computational Science and Its Applications — ICCSA 2005. — Berlin; New York : Springer, 2005. — Vol. 2. — P. 614—623. — (Lecture Notes in Computer Science^[англ.]. Vol. 3481). — doi:10.1007/11424826_65.

[FS07-10] ¹ ² Fujisaki E., Suzuki K. Traceable Ring Signature // Public Key Cryptography — PKC 2007. — Berlin; Heidelberg; New York : Springer, 2007. — P. 181—200. — (Lecture Notes in Computer Science^[англ.]. Vol. 4450).

[11] CryptoNote Phylosophy (неопр.). CryptoNoteTech. Дата обращения: 24 ноября 2017. Архивировано 24 ноября 2017 года.

[12] CryptoNote Currencies (англ.) (2015). Дата обращения: 29 ноября 2017. Архивировано 13 июля 2017 года.

[13] CryptoNote — убийца Bitcoin? (неопр.) (23 июня 2014). Дата обращения: 29 ноября 2017. Архивировано 1 декабря 2017 года.

[14] Rynomster, Tecnovert. ShadowCash: Zeroknowledge Anonymous Distributed ECash via Traceable Ring Signatures (англ.) (pdf). www.shadow.cash (2015). Архивировано из оригинала 1 декабря 2017 года.

[15] Crypto Fun. Broken Crypto in Shadowcash (англ.) (13 февраля 2016). Дата обращения: 29 ноября 2017. Архивировано 27 сентября 2016 года.

[16] Fujisaki E. Sublinear size traceable ring signatures without random oracles // Topics in Cryptology — CT-RSA 2011. — Heidelberg; Dordrecht; London; New York : Springer, 2011. — P. 393—415. — (Lecture Notes in Computer Science^[англ.]. Vol. 6558).

[17] Au, Man Ho; Liu J. K.; Susilo W.; Yuen, Tsz Hon. Constant-Size ID-Based Linkable and Revocable-iff-Linked Ring Signature // Progress in Cryptology — INDOCRYPT 2006. — Heidelberg; Dordrecht; London; New York : Springer, 2006. — P. 364—378. — (Lecture Notes in Computer Science^[англ.]. Vol. 4329).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]