AccuRevoke: Enhancing Certificate Revocation with Distributed Cryptographic Accumulators

Certificate revocation is essential for maintaining the security of the Public Key Infrastructure (PKI), ensuring that compromised or untrustworthy certificates are invalidated promptly. Traditional revocation mechanisms like Certificate Revocation Lists (CRLs) and the Online Certificate Status Protocol (OCSP) face significant challenges, including scalability issues, high bandwidth consumption, privacy concerns, and reliance on centralized infrastructure that can become points of failure. In this paper, we introduce AccuRevoke, a novel revocation scheme that leverages cryptographic accumulators and edge computing to address these challenges effectively. Accu Revoke enables clients to verify the revocation status of certificates efficiently without the need to contact Certificate Authorities (CAs) directly for each validation. By utilizing distributed accumulators and threshold cryptography, Accu Revoke ensures authenticity and integrity of revocation information, even when responses are generated by third-party Edge Compute Providers (ECPs). Our scheme significantly reduces bandwidth consumption by providing compact revocation proofs-approximately 21 bytes for membership proofs and 61 bytes for non-membership proofs-which are substantially smaller than traditional OCSP responses. To further optimize performance, especially in generating non-membership witnesses, we employ GPU acceleration, achieving considerable improvements in processing times. We compare AccuRevoke with existing revocation mechanisms, demonstrating advantages in bandwidth efficiency, reliability, auditability, and potential enhancements in privacy. Our evaluation shows that Accu Revoke offers a scalable and practical solution for revocation checking, improving the security and performance of TLSIPKI deployments. We plan to open-source our design and implementation to facilitate adoption and encourage further research in this area.