Ring Signature

Table of contents

What it is

In a Ring Signature protocol a signer can produce a valid signature while hiding it among “fake” signatures generated by other group participants.

Doing so allows for a certain level of anonymity given that the verifier can’t determine which group member generated the valid signature.

How it works

The Ring Signature scheme we’ll explore here is based on Schnorr Signatures combined with the OR-Proof Technique.

Familiarity with the Schnorr Signature protocol is required to follow along.

In our example we’ll use an Elliptic Curve $E$ that has a generator $G$ and is of order $q$. All calculations are done $\bmod\ q$ if not stated otherwise.

There will be a set of $n$ users, one of which will generate a valid signature that is subsequently verified by the verifier.

At first, we need to decide which user will generate the signature.

The group of users who collaborate but don’t produce a valid signature will all generate their secret $x$ and it’s corresponding public value $X = xG$ as usual.

Next, rather than proceeding with the regular Schnorr Signature protocol in which a random nonce $r$ is sampled, the set of users deviate from the protocol and choose a value for $c$ as well as a random value for $e$.

Doing so allows each individual to compute $R = eG - cX$ which, when checked by the verifier later on via $eG \overset{?}{=} R + cX$ will be valid because:

With that done, the “real” signer will now generate their secret $x$ randomly and compute the public value $X = xG$. Next, the nonce $r$ will be sampled randomly and the value $R$ wil be computed as $R = rG$.

The signer gathers all the $X$ and $R$ values to compute $c$ as the hash of the concatenation of those values with the message $m$ that will be signed:

To compute their own $c'$ value, all $c$ values of the other participants are XORed with a final XOR of the value $c$:

The signer’s $e$ value is now calculated as $e = r + c'x$.

Finally, all $R$, $c$ (including $c'$) and $e$ values of all participants are sent to the verifier.

The verifier computes $c$ as the hash of the concatenation of the $X$ and $R$ values alongside the message $m$:

Next up, all individual $c$ values (including $c'$) are XORed with each other to check if the result is equal to $c$.

Due to XOR’s properties, a value XORed with itself cancels out. Given that $c' = c_1 \oplus ... \oplus c_n \oplus c$ which is XORed with $c_1 \oplus ... \oplus c_n$ we’ll end up with a remaining $c$ which validates the equality check:

As a final step, the verifier checks for every protocol participant if $eG \overset{?}{=} R + cX$ with their respective $e$, $R$ and $X$ value.

Why it works

Given that the participants determine the value of $c$ and $e$, they can produce a value for $R$ so that the check $eG \overset{?}{=} R + cX$ done by the verifier results in a truthy value because:

A value XORed with itself results in the zero value when values are represented as binary. This property of “cancelling out” is leveraged when the signer creates the value for $c'$ by XORing all the participants values in addition to the value $c$ that was generated via the hash:

The verifier XORs all $c$ values (including $c'$) to check if it’s equal to $c$, which it will be due to the aforementioned property that a value XORed with itself “cancels out”:

With all the different values for $c$, $e$ and $R$ from all participants of the protocol, it’s impossible to distinguish any specific value from the others which therefore allows the signer to remain anonymous among the group of participants.

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.

• Wikipedia - Ring Signature
• Nguyen Thoi Minh Quan - Intuitive Advanced Cryptography