An Efficient Threshold Anonymous Authentication Scheme for Privacy-Preserving Communications

Anonymous authentication enables any user to be authenticated without being identified. (t,n)-threshold ring signatures, introduced by Bresson et. al., are ring signature schemes that allow a group of t members to jointly sign a message anonymously in a ring of n members. Threshold ring signature schemes provide a nice tradeoff between anonymity and creditability since it allows multiple ring members to sign a message jointly. The complexity in both signature generation and signature verification of the threshold ring signature scheme proposed by Bresson et. al. is mathcal{O}(n^2). They also proposed an efficient threshold ring signature scheme based on an (n,t)-complete fair partition, with complexity mathcal{O}(n log n). In this paper, a new efficient (t,n)-threshold ring signature scheme is proposed. This scheme is constructed through a system of t linear equations and n variables, where t is generally a fixed number that is much smaller than n. The proposed threshold ring signature scheme can provide unconditional signer ambiguity, threshold unforgeability and provable security in the random oracle model. The complexity of signature generation and signature verification of the proposed threshold ring signature scheme are mathcal{O}(t log^2_2t) and mathcal{O}(n), respectively. Furthermore, the length of the threshold ring signature is the same as the regular ring signature introduced by Rivest et. al., which is 2n+2, while the length of the threshold ring signature scheme proposed by Bresson et. al. is 3n-t+3.