1 Introduction

The wide use of public key cryptography requires the ability to verify the authenticity of public keys. This is achieved through the use of certificates (that serve as a mean for transferring trust) in a Public Key Infrastructure (PKI). A certificate is a message signed by a publicly trusted authority (the certification authority, whose public key authenticity may be provided by other means) which includes a public key and additional data, such as expiration date, serial number and information regarding the key and the subject entity.

When a certificate is issued, its validity is limited by an expiration date. However, there are circumstances (such as when a private key is revealed, or when a key holder changes affiliation or position) where a certificate must be revoked prior to its expiration date. Thus, the existence of a certificate is a necessary but not sufficient evidence for its validity, and a mechanism for determining whether a certificate was revoked is needed.

A typical application is a credit card system where the credit company may revoke a credit card, temporarily or permanently, prior to its expiration, e.g. when a card is reported stolen or according to its user's bank account balance.

This work focuses on the problem of creating and maintaining efficient authenticated data structures holding information about the validity of certificates. I.e. how to store, update and retrieve authenticated information concerning certificates.

There are three main types of parties involved with certificates:

1. Certification authority (CA): A trusted party, already having a certified public key, responsible for establishing and vouching for the authenticity of public keys, including the binding of public keys to users through certificates and certificate revocation.

   A CA does not provide on-line certificate information services to users. Instead, It updates a directory on a periodic basis.

   A CA issues certificates for users by signing a message containing the certificate serial number, relevant data and an expiration date. The certificate is sent to a directory and/or given to the user himself. The CA may revoke a certificate prior to its expiration date.

2. Directory: One or more non-trusted parties that get updated certificate revocation information from the CA and serve as a certificate database accessible by the users.

3. User: A non-trusted party that receives its certificate from the CA, and issues queries for certificate information. A user may either query the validity of other users' certificates (we denote users that query other users' certificates as merchants) or, get a proof of the validity of his certificate in order to present it with his certificate (for the latter, the proof must be transferable).

The rest of this paper is organized as follows: In Section 2 we briefly review the solutions we are aware of (CRL, CRS and CRT), memory checkers and incremental cryptographic schemes. In Section 3 we give some basic definitions and the theoretical background and restate the problem in terms of finding efficient authenticated directories and, in particular, authenticated search data structures. The proposed scheme is described in detail in Section 4 and compared with the other schemes in Section 5. Finally, in Section 6, we consider a model in which a directory is not used for extracting certificates, and certificates are updated periodically. We show how a simple modification of our revocation scheme works in this model.