In this section we review the solutions we are aware of, namely Certificate Revocation List (CRL [20]), Certificate Revocation System (CRS [18]) and Certificate Revocation Trees (CRT [16]). We continue by reviewing memory checkers, and incremental cryptographic schemes, relating these problems to certificate revocation, these two sections are included as theoretical background, and are not necessary for understanding the rest of the paper.
A CRL is a signed list issued by the CA identifying all revoked certificates by their serial numbers. The list is concatenated with a time stamp (as an indication of its freshness) and signed by the CA that originally issued the certificates. The CRLs are sent to the directory on a periodic basis, even if there are no changes, to prevent the malicious replay of old CRLs instead of new CRLs.
As an answer to a query, the directory supplies the most updated CRL (the complete CRL is sent to the merchant).
A reasonable validity expiration period should be chosen for certificates. If the expiration period is short, resources are wasted reissuing certificates. If the expiration period is long, the CRL may get long, causing high communication costs and difficulties in CRL management. Kaufman et al. [15, Section 7.7.3,] suggested reissuing all certificates whenever the CRL grows beyond some limit. In their proposal, certificates are marked by a serial number instead of an expiration date. (Serial numbers are incremented for each issued certificate. Serial numbers are not reused even when all certificates are reissued.) The CRL contains a field indicating the first valid certificate. When all certificates are reissued, the CRL first valid certificate field is updated to contain the serial number of the first reissued certificate.
Micali [18] suggested the Certificate Revocation system (CRS) in order to improve the CRL communication costs. The underlying idea is to sign a message for every certificate stating whether it was revoked or not, and to use an off-line/on-line signature scheme [11] to reduce the cost of periodically updating these signatures.
To create a certificate, the CA associates with each certificate two numbers
(
and N) that are signed along with the `traditional' certificate
data.
For each certificate, the CA chooses (pseudo)randomly two numbers
and computes (using a one-way function f) 
and 
.
(Actually, a stronger assumption on f is required, e.g. that f is
one-way on its iterates, i.e. that given
it is infeasible to find 
such that 
.
This is automatically guaranteed if f is a one-way permutation.)
The directory is updated daily by the CA sending it a number C for each certificate as follows:
,
where i is a daily incremented counter, i=0 on the date of issue.
.
Another advantage of CRS is that each user may hold a succinct transferable proof of the validity of his certificate. Directory accesses are saved when users hold such proofs and presents them along with their certificates.
The complexity of verifying that a certificate was not revoked is also
proportional to the update rate. For example, for an update once an hour,
a user may have to apply the function, f, 
times in order to verify that a certificate was not revoked, making it
the dominant factor in verification.
The complexity of the Micali's method of verifying a certificate may
be improved as follows.
Let h be a collision intractable hash function.
To issue a certificate, the CA creates a binary hash tree as follows:
The tree leaves are assigned (pseudo)random values. Each internal node
v is assigned the value 
where 
are the values
assigned to v's children.
The CA signs the root value and gives it as a part of the
certificate, the other tree values (and specifically the (pseudo)random values
assigned to its leaves are not revealed).
To refresh a certificate the ith time, the CA reveals values of the nodes on
the path from the root to leaf 2i and their children (Thus, the verifier can
check that the nodes are assigned a correct. Note that it is not necessary to
explicitly give the values of the nodes on the path since these values may be
easily computed given the other values).
The path serves as a proof for the certificate validity.
Amortizing the number of tree nodes the CA has to send the directory, we get
that four nodes are sent to update a user's certificate. We make further use
of the hash tree scheme in the following sections.
Kocher [16] suggested the use of Certificate Revocation Trees (CRT)
in order to enable the verifier of a certificate to get a short proof that
the certificate was not revoked.
A CRT is a hash tree with leaves corresponding to a set of statements about
certificate serial number X issued by a CA, 
.
The set of statements is produced from the set of revoked certificates of every
CA. It provides the information whether a certificate X is revoked or not
(or whether its status is unknown to the CRT issuer).
There are two types of statements: specifying ranges of unknown CAs, and,
specifying certificates range of which only the lower certificate is revoked.
For instance, if 
revoked two certificates, 
, than one of the
statements is:
if 
and 
then
X is revoked iff X=v
To produce the CRT, the CRT issuer builds a binary hash tree [17] with leaves corresponding to the above statements.
A proof for a certificate status is a path in the hash tree, from the root to the appropriate leaf (statement) specifying for each node on the path the values of its children.
Blum et al. [3] extended the notion of program checking to programs which store and retrieve data from unreliable memory. In their model, a data structure resides in a large memory controlled by an adversary. A program interacts with the data structure via a checker. The checker may use only a small reliable memory and is responsible for detecting errors in the data structure behavior while performing the requested operations. An error occurs when a value returned by the data structure does not agree with the corresponding value entered into the data structure. Blum et al. showed how to construct an online checker for RAMs using a variant of Merkle's hash-tree authentication scheme for digital signatures [17]. They used universal one way hash functions [19].
(Informally, U is a family of universal one way hash functions
if 
, for f chosen at random from U, it is infeasible to find
y such that 
.)
Certificate revocation may be regarded as a variant of memory checking. As in memory checking, an unreliable memory is used for storing and retrieving data. The difference is that in memory checking the same program writes into and reads from memory via the checker, whereas in certificate revocation there exist two distinct non-communicating programs. One program (the CA) writes into an unreliable memory (the directory), the other (a user) reads from the unreliable memory. The fact that the two programs are disconnected raises the need for a mechanism to prevent an adversary from replaying old data.
Returning to memory checking, our solution may be regarded as a checker for dictionaries.
The high CA-to-directory communication in CRS is due to the fact that the CA has to update values not only for certificates whose status was changed since the last update, but for all certificates. Since the fraction of certificates that change status in every update is expected to be small, it would be preferable to use a scheme with communication (and computational work) depending mostly on the number of certificates that change status. Such issues are addressed by incremental cryptography.
Incremental cryptography was introduced by Bellare, Goldreich and Goldwasser [4,5]. The goal of incremental schemes is to quickly update the value of a cryptographic primitive (e.g. hash function, MAC etc.) when the underlying data is modified. Informally, for a given set of modification operators (e.g. insert, delete, replace), in an ideal incremental scheme, the computational work needed for updating a value depends only on the number of data modifications.
An ideal incremental authentication scheme based on a 2-3 search tree was suggested in [5]. The scheme is a modification of a standard tree authentication scheme [17] in order to allow efficient insert/delete block operations along with replace block operations. This scheme cannot be used directly for our problem, we modify it for our purposes in Section 4.