Paper 2006/066

Simple and Flexible Private Revocation Checking

John Solis and Gene Tsudik


Digital certificates signed by trusted certification authorities (CAs) are used for multiple purposes, most commonly for secure binding of public keys to names and other attributes of their owners. Although a certificate usually includes an expiration time, it is not uncommon that a certificate needs to be revoked prematurely. For this reason, whenever a client (user or program) needs to assert the validity of another party’s certificate, it performs revocation checking. There are many revocation techniques varying in both the operational model and underlying data structures. One common feature is that a client typically contacts an on-line third party (trusted, untrusted or semi-trusted), identifies the certificate of interest and obtains some form of a proof of either revocation or validity (non-revocation) for the certificate in question. While useful, revocation checking can leak potentially sensitive information. In particular, third parties of dubious trustworthiness discover two things: (1) the identity of the party posing the query, as well as (2) the target of the query. The former can be easily remedied with techniques such as onion routing or anonymous web browsing. Whereas, hiding the target of the query is not as obvious. Arguably, a more important loss of privacy results from the third party’s ability to tie the source of the revocation check with the query’s target. (Since, most likely, the two are about to communicate.) This paper is concerned with the problem of privacy in revocation checking and its contribution is two-fold: it identifies and explores the loss of privacy inherent in current revocation checking, and, it constructs a simple, efficient and flexible privacy-preserving component for one well-known revocation method.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
privacy-preserving protocolsrevocationimplementation
Contact author(s)
gts @ ics uci edu
2006-06-21: revised
2006-02-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {John Solis and Gene Tsudik},
      title = {Simple and Flexible Private Revocation Checking},
      howpublished = {Cryptology ePrint Archive, Paper 2006/066},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.