A ring signature is a digital signature that is created by a member of a group that each have their own keys. With this it will not be possible to determine the person in the group who has created the signature. They were initially created by Ron Rivest, Adi Shamir, and Yael Tauman in 2001.
Ring Signatures |
Details
And so there has been a leak of information at the White House. Donald Trump calls in his Cyber Security leads, and tells them, "I know one of you leaked the information, but I can't tell which one". How can Donald tell that one of his chief leaked the information, but not know which one? Well this can be achieved with a ring signature, and which provides anonymity, unforgivably and collusion resistance.
A ring signature is a digital signature that is created by a member of a group which each have their own keys. It is then not be possible to determine the person in the group who has created the signature. The method was initially created by Ron Rivest, Adi Shamir, and Yael Tauman in 2001, and who proposed the White house leak dilemma.
In a ring signature we define a group of entities who each have public/private key pairs of (P1, S1), (P2, S2), …, (Pn, Sn). If we want entity \(i\) to sign a message (\(message\)), they use their own secret key (\(s_i\)) but the public keys of the others in the group (\(m,s_i,P_1 … P_n\)). It should then be possible to check the validity of the group by knowing the public key of the group, but not possible to determine a valid signature if there is no knowledge of the private keys within the group.
So let's say that Trent, Bob, Eve and Alice are in a group, and they each have their own public key and secret key. Bob now wants to sign a message from the group. He initially generates a random value \(v\), and then generates random values (\(s_i\)) for each of the other participants, but takes his own secret key (\(s_i\) and uses it to determine a different secret key, and which reverse of the encryption function. He next takes the message and takes a hash of it, and thus creates a key (\(k\)). This key will be used with symmetric encryption to encrypt each of the elements of the ring (\(E_k\), and each element of the ring uses an EX-OR function from the previous element (Figure 1). Each of the random values for the other participants are then encrypted with the public key of the given participant. Bob then computes the value of \(y_s\) in order to create the ring (the result of the ring must equal v). He will then inverse this value to produce the equivalent private key (xs). Bob now releases the overall signature, and the random x values, along with the computed secret key. To check the signature, the receive just computes the ring, and checks that the result matches the sent signature.
The basic method are:
1. Generate encryption with \(k=\text{Hash}(message)\).
2. Generate a random value (\(u\)).
3. Encrypt \(u\) to give \(v=E_k(u)\).
4. For each person (apart from the sender):
- 4.1 Calculate \(e=s_i^{P_i} \pmod{N_i}\) and where \(s_i\) is the random number generated for the secret key of the \(i\)th party, and \(P_i\) is the public key of the party.
- 4.2 Calculate \(v= v \oplus e\)
5. For the signed party (\(z\)), calculate \( s_z={(v \oplus u)}^d \pmod {N_z}\) and where \(d\) is the secret key of the signing party.
We will end up with the signature (\(v=E_k(u)\)), and which completes the ring.
Presentation
The following is an outline presentation [slides]:
Coding
The code is direct from [link] and includes an RSA-derived method:
import os, hashlib, random, Crypto.PublicKey.RSA import sys from functools import reduce class ring: def __init__(self, k, L=1024): self.k = k self.l = L self.n = len(list(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 (list(range(z+1, self.n)) + list(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 = list(map(_f, list(range(len(X)-1)))) def _g(x, i): return self.E(x^y[i]) r = reduce(_g, list(range(self.n)), X[0]) return r == X[0] def permut(self, m): self.p = int(hashlib.sha1(m.encode()).hexdigest(),16) # sha1(s.encode(encoding)).hexdigest() def E(self, x): msg = '%s%s' % (x, self.p) return int(hashlib.sha1(msg.encode()).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 size = 4 msg1="Hello" def _rn(_): return Crypto.PublicKey.RSA.generate(1024, os.urandom) print(("Message is:",msg1)) key = list(map(_rn, list(range(size)))) r = ring(key) for i in range(size): s1 = r.sign(msg1, i) # s2 = r.sign(msg2, i) if (i==1): print(("Signature is", s1)) print(("Signature verified:",r.verify(msg1, s1))) # assert r.verify(msg1, s1) and r.verify(msg2, s2) and not r.verify(msg1, s2)