Go And Do Ring Signatures: Preserving Privacy

A demo of the methods involved in this article is here.
Photo by Helloquence on Unsplash

Go And Do Ring Signatures: Preserving Privacy

A demo of the methods involved in this article is here.

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 leads has 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 in their paper they proposed the White house leak dilemma.

Creating the ring

In a ring signature we define a group of entities who each have their own public/private key pairs of (P1, S1), (P2, S2), …, (Pn, Sn). If we want an entity i to sign a message (message), they use their own secret key (si), but the public keys of the others in the group (m,si,P1…Pn). 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 and secret keys. Bob now wants to sign a message from the group. He initially generates a random value v, and then generates random values (xi) for each of the other participants, but takes his own secret key (si) and uses it to determine a different secret key, and which reverse of the encryption function. He now 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 (Ek), and then each element of the ring uses an EX-OR function from the previous element (Figure 1).

He now 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 (Ek), and then 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 ys 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=Hash(message).

2. Generate a random value (u).

3. Encrypt u to give v=Ek(u).

4. For each person (apart from the sender):

  • 4.1 Calculate e=si^{Pi} (mod Ni) and where si is the random number generated for the secret key of the ith party, and Pi is the public key of the party.
  • 4.2 Calculate v=v⊕e

5. For the signed party (z), calculate sz=(v⊕u)^d (mod Nz) and where d is the secret key of the signing party.

We will end up with the signature (v=Ek(u)), and which completes the ring.

I have created a demonstration of the original method here, and here is an outline presentation of the method [slides].

A demo of the methods involved in this article is here. The basic method involves creating Bob creating fake private keys for the other people in the ring:

The following defines some code [taken from here][demo]:

A sample run is [demo]:

Message: Hello
Public keys: [81753b549e40804617759c9cba6878b494b8cf1d82651c504040d52acc2eb694 c45ae8f669e313183cbc7bbd6369e9423aa12c20d30da38deba7fe8da14c408a 94d45114ef11eeba37c1c9e37bd375f8f3af7b690cd7de54b9ab20e876c7e288 5dd0b5464b971d3776941a9f0df9330f1bb54423e3d12fb41b6175bc1549ba10 789c14943c31a0d56c65c75b0e0fdcc5dc7242b3a750802f1cbbcd711a3a9bce]
Private key of signer: 9c7ecf02d2f0b18c470e2f0e6a0cc7b3f966b87757bab56ca3fbfdd7116ac10e
Public key of signer: 01cad592c6ca5a9b397dbc15662a297a274df1f79da5dd336b9dea46a83f7399
Signature:
00000000  4c e1 3a b6 31 2d cb 79  69 91 1a 05 2a f8 46 0b  |L.:.1-.yi...*.F.|
00000010  a5 b2 ea cb 5e 21 ff 23  d4 6b 03 f5 07 e4 58 0d  |....^!.#.k....X.|
00000020  82 a1 49 c5 e8 f0 0a 3d  00 ec 64 e0 1a 1a 36 91  |..I....=..d...6.|
00000030  3d 5e 53 9e 81 66 b4 ba  54 cb bd c9 00 73 b3 04  |=^S..f..T....s..|
00000040  1d a0 d8 5f a3 33 78 08  cf c5 57 3f 69 f4 49 48  |..._.3x...W?i.IH|
00000050  47 aa d3 7e ae f3 d2 66  9e b0 37 80 c7 34 f5 0a  |G..~...f..7..4..|
00000060  76 11 9b 2a 79 1d e0 5e  2d 21 c1 26 ec cc 18 a1  |v..*y..^-!.&....|
00000070  c0 27 f1 96 0a eb 40 d2  a3 c1 11 5e 6f 08 da 02  |.'....@....^o...|
00000080  bd 86 53 73 2c 94 b6 04  9a 05 0a 86 1f 2c d1 1e  |..Ss,........,..|
00000090  ca f4 d8 60 b3 4e 36 ed  74 fd d4 32 23 06 b1 0a  |...`.N6.t..2#...|
000000a0  11 b5 0b 4c f2 e0 f4 45  d9 e9 a9 3c 26 c2 78 c5  |...L...E...-&.x.| 
000000b0  12 ee d7 5b 2a 65 65 c9 bf b1 31 2a eb 34 b8 04   |...[*ee...1*.4..|
Signature has been verified

Rings Signatures in Monero

The major problem with the Bitcoin network, is that the amount of a transaction and the sender and receive of the funds are not private, and someone who knows someones address can trace their transactions. This is the case because the blockchain needs to check that the sender has enough funds to pay the recipient.Thus many cryptocurrencies are looking for ways of anonymising the transaction. Ethereum, for example, uses zk-Snarks to hide identities.

One method of preserving identity was proposed by Rivest et al and uses RSA encryption. Unfortunately it is not efficient for modern systems, thus Greg Maxwell’s defined an elliptic curve methods as a new way of creating the ring signature: the Borromean ring signature [paper].

The cryptocurrency Monero then adopted the method for anonymising transactions, but have since migrated to a new method: Multi-layered Linkable Spontaneous Anonymous Group signature. This method hides the transaction amount and the identity of the payer and recipient [paper]. It is now known as RingCT (Ring Confidential Transactions), and was rolled-out in January 2017 and mandatory for all transactions from September 2017.

Conclusions

The major problem with the Bitcoin network is that the amount of a transaction and the sender and receiver of the funds are not private, and someone who knows someone’s address can trace their transactions. This is the case because the blockchain needs to check that the sender has enough funds to pay the recipient. Thus many cryptocurrencies are looking for ways of anonymising the transaction.