In this blog post I explain -of- anonymous threshold ring signatures, “Ring Multisignatures”. This technique is a straight-forward generalization of a method for n-of-n Schnorr multisignature described to me last summer by Monero Developer TacoTime.
Suppose that a group of users wants to create a multisignature address requiring of the group to sign in order to spend any funds received, and in such a way that any observer will be unable to determine for certain whether funds have been sent from this address or not, but in such a way that spending funds twice is impossible.
3.1. Setup Phase
First create a shared key for each sized subset of the users. For a running example suppose and , I will say that are users, and denote their shared keys . Now the destination multisignature address will be the sum of all of these shared keys. So in our example, . Note that at least two users of are required to know the private keys belonging to each of the summands, so this results in a -of- multisignature address.
3.2. Ring Signing
How does one create a ring signature with this type of addresses? Suppose that of the signers (say and in the above example) wish to sign a transaction. The shared key in this case is the sum of all subset-shared keys, and thus, since , each summand in the shared key:
has a private key known by at least one of the signers.
Let and denote cryptographic hash functions returning a scalar and curve point respectively. If signer knows the private key to summand , in the above shared key, then to start the signature, they generate a random scalar and share to the other signers (keeping secret). As in a usual ring signature, the signers decide on other unspent public keys from the block-chain to be partners in the ring with. Furthermore, signer will compute and the key image of the signature will be .
Now, supposing the signers decide on putting their multisignature key at secret index , they start the ring signature by computing:
(in the MLSAG setting of RingCT these computation are carried out in each row of the signature) with and
The ring signature proceeds as in the usual MLSAG fashion (c.f. RingCT ), for each index the signers choose a random scalar and compute
stopping after has been computed.
Finally, using the relation:
each signer computes (without revealing )
where is the order of the underlying field. The final is then the sum of the ,
If there are other inputs, the MLSAG apparatus allows for these other inputs in other rows of the MLSAG with no changes from RingCT , and verification of the above signature, which consists of the key-image , the scalars , and the -th index hash proceeds exactly as in RingCT , since the pubkey is indistinguishable, to an observer, from any other pubkey.
Note that the Schnorr multisignature described by TacoTime is a special case of the above, with a ring of size (having no additional public keys), and in that case, if , the shared keys belonged to one user only, or in the case that , the shared keys belong to users. Thus the above, is really a straight-forward generalization. Furthermore, since is chosen randomly, the probablility that will be the same in two different signatures is negligible. Thus we avoid the repeated nonce attack which must be specially taken care of in other threshold signature schemes.
Claim 1 In the above scheme describing Ring Multisignature, at least of signers are needed for a given transaction, and conversely, of signers can sign a given transaction.
Proof: This is fairly simple: suppose that there are signers in the given transaction. If the claim holds for , then it clearly holds for smaller , so without loss of generality, assume . We may clearly assume that is at least two. Note that given a set of integers, there is clearly a subset of size elements not containing any given elements (namely the complement of those elements). Thus it follows that at least signers are needed, since each summand in the pubkey is a shared key among signers.
Conversely, if there are at least distinct signers, then any subset of the signers size distinct must clearly intersect with the signers, so all of the summands have a secret key known to the signers.