Group Signatures with Verifier-Local Revocation

Authors: D. Boneh and H. Shacham

Group signatures have recently become important for enabling privacy-preserving attestation in projects such as Microsoft's {\sc ngscb} effort (formerly Palladium). Revocation is critical to the security of such systems. We construct a \emph{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.

In proceedings of the 11'th ACM conference on Computer and Communications Security (CCS), pp. 168-177, 2004

Full paper: pdf