RING SIGNATURE KEY BLINDING
==================================
Gregory Maxwell and Andrew Poelstra
September 2014
Introduction
===============
Ring signatures offer the exciting cryptographic ability to sign a document
as a member of some set of signers, without revealing any information beyond
that. That is, a valid ring signature can be proven to be created by one key
out of some fixed set, but the specific key cannot be identified.
However, naive use of ring signatures presents a risk that parties retroactively
remove themselves from the anonymity set. They can do this by revealing their
secret key --- allowing all others to easily determine that they were (not) the
signer.
Blinding
===============
A solution to this is to "blind" the signing key by adding a random offset.
When creating a signature, all users add a curvepoint Q = qG to their public
key, and provide a zero-knowledge proof of q (a DSA signature of H(0) with Q
will suffice, for any cryptographic hash function H). If their original key
was P = pG, then the key in the ring signature is P + Q.
Because they proved knowledge of q, and a signature with P + Q proves knowledge
of p + q, such a signature proves knowledge of p. This is why we may substitute
P + Q for P without loss.
To create a signature, the signer generates q values for all signers. She proves
knowledge of each one of them, adds the corresponding Q values to the public
keys, and uses her own q (plus her private key) to create the signature. Then
she forgets all the q values.
Now, if a party whose key is in the ring later wants to prove their non-participation,
they have no recourse, because they do not know the secret q value that was added
to their key to get the key in the ring. (On the other hand, the proofs of knowledge
of q prove that their key really did appear in the ring; that is, all these purported
"Q + P" values are not simply independent random points chosen by the signer, they can
only be used by somebody with knowledge of P's private key.)
The signing party also has equal deniability to all other parties, and if she really
forgot the q value she used, she can't prove that she was the signer even if she wanted
to!