Skip to content

Ring Signature

Table of contents

Open 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 EE that has a generator GG and is of order qq.

There will be a set of nn 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 xx and it’s corresponding public value X=xGX = xG as usual.

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

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

R=eGcXReGeG=RcX×(1)eG=R+cX\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 xx randomly and compute the public value X=xGX = xG. Next, the nonce rr will be sampled randomly and the value RR wil be computed as R=rGR = rG.

The signer gathers all the XX and RR values to compute cc as the hash of the concatenation of those values with the message mm that will be signed:

c=H(X1...XnR1...Rnm)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 cc' value, all cc values of the other participants are XORed with a final XOR of the value cc:

c=c1...cnc.c' = c_1 \oplus ... \oplus c_n \oplus c.

The signer’s ee value is now calculated as e=r+cxmodqe = r + c'x \mod q.

Finally, all RR, cc (including cc') and ee values of all participants are sent to the verifier.

The verifier computes cc as the hash of the concatenation of the XX and RR values alongside the message mm:

c=H(X1...XnR1...Rnm)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 cc values (including cc') are XORed with each other to check if the result is equal to cc.

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

c=cc1...cn=c1...cncc1...cn=c\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=?R+cXeG \overset{?}{=} R + cX with their respective ee, RR and XX value.

Ring Signature

Why it works

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

R=eGcXReGeG=RcX×(1)eG=R+cX\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 cc' by XORing all the participants values in addition to the value cc that was generated via the hash:

c=c1...cncc' = c_1 \oplus ... \oplus c_n \oplus c

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

c=cc1...cn=c1...cncc1...cn=c\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 cc, ee and RR 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.

Additional Resources