Image for post
Image for post

Ring Signatures And Anonymisation

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.

Image for post
Image for post

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 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.

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 is the 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).

Image for post
Image for post

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:

Image for post
Image for post

The verification of the ring is then:

Image for post
Image for post
Image for post
Image for post

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 method 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.

Coinmonks

Coinmonks is a non-profit Crypto educational publication.

By Coinmonks

A newsletter that brings you week's best crypto and blockchain stories and trending news directly in your inbox, by CoinCodeCap.com Take a look

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Coinmonks

Coinmonks

Coinmonks is a non-profit Crypto educational publication. Follow us on Twitter @coinmonks Our other project — https://coincodecap.com

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Coinmonks

Coinmonks

Coinmonks is a non-profit Crypto educational publication. Follow us on Twitter @coinmonks Our other project — https://coincodecap.com

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store