In Proceedings of CCS 2004, pages 168–77. ACM Press, Oct. 2004.
Group signatures have recently become important for enabling privacy-preserving attestation in projects such as Microsoft's NGSCB effort (formerly Palladium). Revocation is critical to the security of such systems. We construct a short group signature scheme that supports Verifier-Local Revocation (VLR). In this model, revocation messages are only sent to signature verifiers (as opposed to both signers and verifiers). Consequently there is no need to contact individual signers when some user is revoked. This model is appealing for systems providing attestation capabilities. Our signatures are as short as standard RSA signatures with comparable security. Security of our group signature (in the random oracle model) is based on the Strong Diffie-Hellman assumption and the Decision Linear assumption in bilinear groups. We give a precise model for VLR group signatures and discuss its implications.