Your old road is rapidly agin’ — Ring Signatures and Anonymisation in an era of privacy

Your old road is rapidly agin’ — Ring Signatures and Anonymisation in an era of privacy

Your old road is rapidly agin’
Please get out of the new one if you can’t lend your hand
For the times they are a-changin’

Introduction

And so there has been a leak of information at the White House.

Donald Trump calls in his Cyber Security leads (Bob, Alice, Eve and Trent), and tells them, “I know one of you leaked the information, but I can’t tell which of you”.

So how can Donald tell that one of his chiefs 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.

Creating the signature

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 (m), 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 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 (xi) for each of the other participants, but takes his own secret key (Si) for his value.

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 (Ek), 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 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.

A demo of this is given here.

So what?

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.

The method proposed by Rivest et al uses RSA 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 information systems we have created are not fit for purpose in the era of GDPR and data privacy, and where we often record sensitive information around transactions. Our future needs to be build with privacy at its core, and ring signatures are one way of achieving this. With blockchain we are now only seven years into its creation, and every single day it gets better in the way we are creating our new world, and the step towards anonymisation of transactions is the next natural step.

So, Bob Dylan could have written this for our emerging blockchain world:

Come mothers and fathers
Throughout the land
And don’t criticize
What you can’t understand
Your sons and your daughters
Are beyond your command
Your old road is rapidly agin’
Please get out of the new one if you can’t lend your hand
For the times they are a-changin’