Ring signature

In cryptography, a ring signature is a type of digital signature that can be performed by any member of a group of users that each have keys. Therefore, a message signed with a ring signature is endorsed by someone in a particular group of people. One of the security properties of a ring signature is that it should be computationally infeasible to determine which of the group members' keys was used to produce the signature. Ring signatures are similar to group signatures but differ in two key ways: first, there is no way to revoke the anonymity of an individual signature, and second, any group of users can be used as a group without additional setup. Ring signatures were invented by Ron Rivest, Adi Shamir, and Yael Tauman, and introduced at ASIACRYPT in 2001. The name "ring signature" comes from the ring-like structure of the signature algorithm.

Definition

Suppose that a group of entities each have public/private key pairs, (PK₁, SK₁), (PK₂, SK₂), ... ,(PK_n, SK_n). Party i can compute a ring signature σ on a message m, on input (m, SK_i, PK₁, ... , PK_n). Anyone can check the validity of a ring signature given σ, m, and the public keys involved, PK₁, ... , PK_n. If a ring signature is properly computed, it should pass the check. On the other hand, it should be hard for anyone to create a valid ring signature on any message for any group without knowing any of the secret keys for that group.

Applications and modifications

In the original paper, Rivest, Shamir, and Tauman described ring signatures as a way to leak a secret. For instance, a ring signature could be used to provide an anonymous signature from "a high-ranking White House official", without revealing which official signed the message. Ring signatures are right for this application because the anonymity of a ring signature cannot be revoked, and because the group for a ring signature can be improvised.

Another application, also described in the original paper, is for deniable signatures. A ring signature where the group is the sender and the recipient of a message will only seem to be a signature of the sender to the recipient: anyone else will be unsure whether the recipient or the sender was the actual signer. Thus, such a signature is convincing, but cannot be transferred beyond its intended recipient.

There were various works, introducing new features and based on different assumptions:

• Threshold ring signatures. Unlike standart "t-out-of-n" threshold signature, where t of n users should collaborate to decrypt a message, this variant of a ring signature requires t users to cooperate in the signing protocol. Namely, parties (l₁,l₂, ... , l_t) can compute a (t,n)-ring signature σ on a message m, on input (m, SK_l1,SK_l2, ... , SK_lt, PK₁, ... , PK_n).
• Linkable ring signatures. The property of linkability allows to determine whether any two signatures have been produced by the same member (under the same private key). The identity of the signer is nevertheless preserved. One of the possible applications can be an offline e-cash system.
• Traceable ring signature. In addition to the previous scheme the public key of the signer is revealed (if he issued more than one signatures under the same private key). An e-voting system can be implemented using this protocol.

Efficiency

Most of the proposed algorithms have asymptotic output size $O(n)$, i.e. the size of the resulting signature increases linearly with the size of input (amount of public keys). That means that such schemes are impracticable for real use cases with sufficiently large $n$ (for example, an e-voting with millions of participants). But for some application with relatively small median input size such estimate may be acceptable. CryptoNote implements $O(n)$ ring signature scheme by Fujisaki and Suzuki in p2p payments to archieve sender's untraceability.

More efficient algorithms have appeared recently. There are schemes with the sublinear size of the signature, as well as with constant size.

Implementation

Here is a Python implementation of the original paper using 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

To sign and verify 2 messages in a ring of 4 users:

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)

Crypto-currencies

The CryptoNote technology uses ring signatures. It was first implemented by Bytecoin (BCN) in July 2012.