# Ring Signature

## 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:

\begin{aligned} R &= eG - cX && \mid -R -eG \\ -eG &= -R - cX && \mid \times (-1) \\ eG &= R + cX \end{aligned}

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:

$c = H(X_1 \mathbin\Vert ... \mathbin\Vert X_n \mathbin\Vert R_1 \mathbin\Vert ... \mathbin\Vert R_n \mathbin\Vert m)$

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

$c' = c_1 \oplus ... \oplus c_n \oplus 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$:

$c = H(X_1 \mathbin\Vert ... \mathbin\Vert X_n \mathbin\Vert R_1 \mathbin\Vert ... \mathbin\Vert R_n \mathbin\Vert 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:

\begin{aligned} c &= c' \oplus c_1 \oplus ... \oplus c_n \\ &= c_1 \oplus ... \oplus c_n \oplus c \oplus c_1 \oplus ... \oplus c_n \\ &= c \end{aligned}

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:

\begin{aligned} R &= eG - cX && \mid -R -eG \\ -eG &= -R - cX && \mid \times (-1) \\ eG &= R + cX \end{aligned}

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:

$c' = c_1 \oplus ... \oplus c_n \oplus c$

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”:

\begin{aligned} c &= c' \oplus c_1 \oplus ... \oplus c_n \\ &= c_1 \oplus ... \oplus c_n \oplus c \oplus c_1 \oplus ... \oplus c_n \\ &= c \end{aligned}

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.