An (n-t)-out-of-n Threshold Ring Signature Scheme.

In CRYPTO2002, Bresson, Stern, and Szydlo proposed a threshold ring signature scheme. Their scheme uses the notion of fair partition and is provably secure in the random oracle model. Their scheme is efficient when the number t of signers is small compared with the number n of group members, i.e., $t={\mathcal O}(\log{n})$ (we call this scheme BSS scheme). However, it is inefficient when t is ω(logn). In this paper, we propose a new threshold ring signature scheme which is efficient when the number of signers is large compared with the number n of group members, i.e., when the number t of non-signers in the group members is small compared with n. This scheme is very efficient when $t={\mathcal O}(\log{n})$. This scheme has a kind of dual structure of BSS scheme which is inefficient when the number of signers is large compared with the number of group members. In order to construct our scheme, we modify the trap-door one-way permutations in the ring signature scheme, and use the combinatorial notion of fair partition. This scheme is provably secure in the random oracle model. [ABSTRACT FROM AUTHOR]