In cryptography, a ring signature is a type of digital signature that can be performed by any member of a set of users that each have keys. Therefore, a message signed with a ring signature is endorsed by someone in a particular set of people. One of the security properties of a ring signature is that it should be computationally infeasible to determine which of the set's 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 set of users can be used as a signing set without additional setup.
Ring signatures were invented by Ron Rivest, Adi Shamir, and Yael Tauman Kalai, and introduced at ASIACRYPT in 2001.[1] The name, ring signature, comes from the ring-like structure of the signature algorithm.
Suppose that a set of entities each have public/private key pairs, (P1, S1), (P2, S2), ..., (Pn, Sn). Party i can compute a ring signature σ on a message m, on input (m, Si, P1, ..., Pn). Anyone can check the validity of a ring signature given σ, m, and the public keys involved, P1, ..., Pn. 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 set without knowing any of the private keys for that set.[2]
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. Here the sender and the recipient of a message form a group for the ring signature, then the signature is valid to the recipient, but 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:
Most of the proposed algorithms have asymptotic output size
O(n)
n
O(n)
More efficient algorithms have appeared recently. There are schemes with the sublinear size of the signature,[6] as well as with constant size.[7]
The original paper describes an RSA based ring signature scheme, as well as one based on Rabin signatures. They define a keyed "combining function"
Ck,v(y1,y2,...,yn)
k
v
y1,...yn
yi
gi(xi)
gi
The function
Ck,v(y1,y2,...,yn)
Ek
Ck,v(y1,y2,...,yn)=Ek(yn ⊕ Ek(yn-1 ⊕ Ek(... ⊕ Ek(y1 ⊕ v)...)))
It outputs a single value
z
v
v=Ck,v(y1,y2,...,yn)
yi
xi
| -1 | |
| g | |
| i |
| -1 | |
| g | |
| i(y |
i)=xi
Generating a ring signature involves six steps. The plaintext is signified by
m
P1,P2,...,Pn
k=l{H}(m)
l{H}
k
Ek
v
xi
xs
yi=gi(xi)
ys
xs
xs=g
| -1 | |
| s |
(ys)
(2n+1)
(P1,P2,...,Pn;v;x1,x2,...,xn)
Signature verification involves three steps.
xi
yi=gi(xi)
k=l{H}(m)
Ck,v(y1,y2,...,yn)=v
Here is a Python implementation of the original paper using RSA. Requires 3rd-party module PyCryptodome.
import functools
class Ring: """RSA implementation."""
def __init__(self, k, L: int = 1024) -> None: self.k = k self.l = L self.n = len(k) self.q = 1 << (L - 1)
def sign_message(self, m: str, z: int): self._permut(m) s = [None] * self.n u = random.randint(0, self.q) c = v = self._E(u)
first_range = list(range(z + 1, self.n)) second_range = list(range(z)) whole_range = first_range + second_range
for i in whole_range: 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
s[z] = self._g(v ^ u, self.k[z].d, self.k[z].n) return [c] + s
def verify_message(self, m: str, X) -> bool: 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)) y = list(y)
def _g(x, i): return self._E(x ^ y[i])
r = functools.reduce(_g, range(self.n), X[0]) return r
def _permut(self, m): msg = m.encode("utf-8") self.p = int(hashlib.sha1(msg).hexdigest, 16)
def _E(self, x): msg = f"".encode("utf-8") 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): result = q * n + pow(r, e, n) else: result = x return result
To sign and verify 2 messages in a ring of 4 users:
def _rn(_): return Crypto.PublicKey.RSA.generate(1024, os.urandom)
key = map(_rn, range(size))key = list(key)
r = Ring(key)
for i in range(size): signature_1 = r.sign_message(msg1, i) signature_2 = r.sign_message(msg2, i) assert r.verify_message(msg1, signature_1) and r.verify_message(msg2, signature_2) and not r.verify_message(msg1, signature_2)
Monero and several other cryptocurrencies use this technology.