Stronger Notions and a More Efficient Construction of Threshold Ring Signatures, by Alexander Munch-Hansen and Claudio Orlandi and Sophia Yakoubov

A ring signature (introduced by Rivest et al., Asiacrypt 2001) allows a signer
to sign a message without revealing their identity by anonymizing themselves
within a group of users (chosen by the signer in an ad-hoc fashion at signing
time). The signature proves that one member of the group is the signer, but
does not reveal which one. We consider threshold ring signatures (introduced
by Bresson et al., Crypto 2002), where any $t$ signers can sign a message
together while anonymizing themselves within a larger (size-$n$) group. The
signature proves that $t$ members of the group signed, without revealing
anything else about their identities.

Our contributions in this paper are two-fold. First, we strengthen existing
definitions of threshold ring signatures in a natural way; we demand that a
signer cannot be de-anonymized even by their fellow signers. This is crucial,
since in applications where a signer’s anonymity is important, we do not want
that anonymity to be compromised by a single insider.

Second, we give the first rigorous construction of a threshold ring signature
with size independent of $n$, the number of users in the larger group. Instead,
our signatures have size linear in $t$, the number of signers. This is also a
very important contribution; signers should not have to choose between
achieving their desired degree of anonymity (possibly very large $n$) and their
need for communication efficiency.