Group signatures (GSs) is an elegant approach for providing privacy-preserving authentication. Unfortunately, modern GS schemes have limited practical value for use in large networks due to the high computational complexity of their revocation check procedures. We propose a novel GS scheme called the Group Signatures with Probabilistic Revocation (GSPR), which significantly improves scalability with regard to revocation. GSPR employs the novel notion of probabilistic revocation, which enables the verifier to check the revocation status of the private key of a given signature very efficiently. However, GSPR’s revocation check procedure produces probabilistic results, which may include false positive results but no false negative results. GSPR includes a procedure that can be used to iteratively decrease the probability of false positives. GSPR makes an advantageous tradeoff between computational complexity and communication overhead, resulting in a GS scheme that offers a number of practical advantages over the prior art. We provide a proof of security for GSPR in the random oracle model using the decisional linear assumption and the bilinear strong Diffie-Hellman assumption.