Abstract
This paper introduces a novel revocation mechanism for group signatures that achieves constant signature length and constant signer computation, independent of the number of revoked members. By extending the ACJT group signature scheme, the authors implement an explicit revocation system using a Certificate Revocation List (CRL). The approach utilizes zero-knowledge proofs of non-membership, specifically double discrete logarithm proofs, to ensure privacy and backward unlinkability. While the signer's workload is constant, the verifier's effort scales linearly with the revocation list, offering a "quasi-efficient" trade-off suitable for various cryptographic applications.
Introduction
Group signatures provide a balance between anonymity and accountability, allowing a member to sign on behalf of a group while permitting a Group Manager to reveal the signer's identity if necessary. A critical challenge in these schemes is revocation: removing a member's signing privileges without compromising the anonymity of others or increasing the overhead for active signers. Prior methods often suffered from linear growth in signature size or required fixed time-period updates. This work addresses these issues by proposing a system where the signer's burden remains fixed, and signatures do not grow as the group changes.
Methods and Technical Framework
The authors build upon the ACJT scheme, which is grounded in the Strong RSA and Decision Diffie-Hellman (DDH) assumptions. The revocation process is managed through a REVOKE algorithm where the Group Manager issues a new revocation base ($b_s$) for each update cycle.
To maintain anonymity while proving validity, a signer must demonstrate in zero-knowledge that their membership certificate is not included in the published CRL. This is achieved via a specialized Signature of Knowledge (SKLOGEQLOGLOG) for double discrete logarithms. This proof ensures that the signer's secret is distinct from all revoked secrets without revealing the secret itself. The rotation of the revocation base $b_s$ ensures backward unlinkability, meaning past signatures cannot be linked to the signer after a revocation event.
The management of these certificates and their associated metadata is crucial for the system's operation. The following table illustrates the conceptual structure of a revocation-related data store, where certificates are encrypted and associated with search tags to facilitate management while preserving privacy:
Key Insights
The term "quasi-efficient" reflects the trade-off between signature size and computational complexity. While the signature size is constant—a significant improvement over previous $O(n)$ schemes—the generation of double discrete log proofs is computationally expensive, requiring hundreds of exponentiations. The design choice to keep signer work constant while allowing verifier work to scale linearly ($O(m)$, where $m$ is the number of revoked members) is a practical compromise, as verifiers often have more resources or can perform checks asynchronously. Furthermore, the paper suggests using "fake" entries in the CRL to obfuscate the actual number of revoked members, thereby protecting group-level privacy.
Results and Security Analysis
The scheme successfully maintains the core properties of group signatures—anonymity, unlinkability, and exculpability—under standard cryptographic assumptions. Key results include:
- Constant Signature Size: Signatures do not increase in length as more members are revoked.
- Constant Signer Work: The effort required to sign a message does not depend on the size of the CRL.
- Provable Security: The scheme is shown to be secure against adaptive chosen-message attacks.
Quantitatively, a signature operation requires approximately 500 exponentiations for standard security levels. Although high, this was a landmark achievement in providing explicit, flexible revocation.
Limitations and Future Directions
The primary limitation is the high computational cost for signers and the linear verification time. As the CRL grows, the verifier's task becomes increasingly demanding. The authors acknowledge that the CRL itself still grows linearly and suggest that future work should explore dynamic accumulators to achieve sub-linear or constant-size revocation lists. Additionally, the scheme does not support retroactive revocation, where a manager might want to invalidate signatures only from a specific past interval.
Conclusion
This paper provides a robust theoretical foundation for explicit revocation in group signatures. By prioritizing constant signature size and signer workload, it offers a viable path for managing dynamic groups in privacy-preserving systems, despite the remaining challenges in computational efficiency and verification scaling.
Summary updated