A certificate revocation scheme for a large-scale highly replicated distributed system

A common way to protect objects in distributed systems is to issue authorization certificates to users, which they present to gain access. In some situations a way is needed to revoke existing certificates. Current methods, such as having a master revocation list, have been designed to work efficiently with identity certificates, and to not take into account the delegation of certificate-issuing rights required when implementing complex administrative hierarchies for large distributed applications. In this paper we present a novel mechanism for revoking authorization certificates based on clustering users and servers, and present arguments showing that it is more efficient than other methods. We also discuss a way for probabilistically auditing the use of the revocation mechanism proposed to reduce the chances of any component behaving maliciously.