An efficient and secure alternative to OCSP for public-key certificate revocation

This paper presents an on-line method for efficient authentication and verification of certificate status within Public-Key Infrastructures (PKIs). The proposed method has been devised as an alternative to the well-known Online Certificate Status Protocol (OCSP): it exhibits the same positive features of as regards scalability, security, timeliness and expressive power while significantly reducing the directory computational load, a particularly remarkable benefit especially in high-traffic scenarios, where performance bottlenecks could be exploited to induce a denial-of-service over the directory. This key feature has been achieved by means of a purposely conceived extension of the One-Way Accumulator (OWA) cryptographic primitive, which permits to provide an explicit, concise, authenticated and not forgeable proof about the revocation status of each certificate. A thorough investigation on the performance attainable shows that the devised method allows reducing the computational load up to an order of magnitude under normal operating conditions of the PKI in which it is deployed, and, for very intensive query activity, even to fix an upper bound independent from the rate PKI users perform certificate status verification operations.