The proposed scheme is closer in spirit to CRL and CRT than to CRS, since it maintains a list of only the revoked certificates. It reduces the CA's communication and actually makes it feasible to update the directory periodically many times a day, achieving a very fine update granularity. The revoked certificates list is maintained in an authenticated search data structure. The benefits of this construction are:
The underlying idea is to imitate a search in a data structure constructing a proof for the result during the search. For that, we combine a hash tree scheme (as in [17]) with a sort tree, such that tree leaves correspond to revoked certificates, sorted according to their serial numbers. Both proving that a certificate is revoked and that a certificate is not revoked reduce to proving the existence of certain leaves in the tree:
We maintain a 2-3 tree with leaves corresponding to the revoked certificates' serial numbers in increasing order. (In a 2-3 tree every interior node has two or three children and the paths from root to leaves have the same length. Testing membership, inserting and deleting a single element are done in logarithmic time, where the inserting and deleting of an element affect only the nodes on the insertion/deletion path. For a detailed presentation of 2-3 trees see [1, pp. 169-180,].) The property of 2-3 trees that we use is that membership queries, insertions and deletions involve only changes to nodes on a search path. I.e. every change is local and the number of affected paths is small.
The tree may be created either by inserting the serial numbers of the revoked certificates one by one into an initially empty 2-3 tree, or, by sorting the list of serial numbers and building a degree 2 tree with leaves corresponding to the serial numbers in the sorted list (because the communication complexity is minimal when the tree is of degree 2).
Every tree node is assigned a value according to the following procedure:
to the values of its children.
The tree update procedure is as follows:
The certification authority vouches for the authenticity of the data structure by signing a message containing the tree root value and the tree height. A proof that there exists a leaf in the tree with a certain value consists of all node values on a path (of length equal to the tree height) from the root to a leaf, plus the values of these nodes children. The proof is verified by checking the values of the tree nodes values on the given path and its length. Finding a fallacious proof for the existence of a leaf in the tree amounts to breaking the collision intractability of h.
Remark:
Possible choices for h include the more efficient
MD4 [22], MD5 [23] or SHA [21] (collisions for
MD4 and for the compress function of MD5 were found by Dobbertin
[9,10]) and functions based on a
computational hardness assumption such as the hardness of
discrete log [8,7,4]
and subset-sum [14,12] (these are much less efficient).
Remark: Note that an explicit serial number is not needed. Instead, any string that is easily computed from the certificate (e.g. hash of the certificate) may be used.
Remark: It is possible to use a family of universal one-way hash functions,
U, instead of collision intractable hash functions by letting
every internal node, v, hold also an index of a function 
.
The function h is randomly chosen whenever v lies in a deletion or
insertion path. The value of a node is computed by applying h to the
values of its children concatenated with their hash function indices.
A motivation for using universal one-way hash functions instead of collision
intractable hash functions is the successful attacks on MD4 and MD5
[9,10]. Since universal one-way hash functions are not susceptible to
birthday attacks, their application may result in a
smaller increase in communication and storage costs with respect to collision
intractable functions. Bellare and Rogaway [6] discuss methods for
creating practical universal one-way hash functions.
Remark: The scheme may be used also for on-line revocation checking of
certificates (where the latency between certificate revocation and CRL update
is reduced). As the result of a query, the on-line service is supposed to
return the current certificate status.
In general, on-line revocation checking requires the certificate validator
to be trusted (where in off-line checking, the directory could be a
non-trusted party). In practice, it is enough that the certificate validator
honestly informs a user about the last time it
was updated by the CA (and may be dishonest with respect to other information).
then it is not needed for the CA to update it only on predetermined times, and
the CA may update the directory whenever the status of a certificate is
changed.
Even if such an assumption is not plausible, the CA may use the
authenticated search data structure to reduce the number of signatures
it has to compute, since a signature has to be computed only when a certificate
status is changed and not for every query.
For a simpler implementation of the authenticated data structure, random treaps [2] may be used instead of 2-3 trees. Treaps are binary trees whose nodes are associated with (key, priority) pairs. The tree is a binary search tree with respect to node keys (i.e. for every node the keys in its left (resp. right) subtrees are small (resp. greater) than its key), and a heap with respect to node priorities (i.e. for every node its priority is higher than its descendents' priorities). Every finite set of (key, priority) pairs has a unique representation as a treap. In random treaps, priorities are drawn at random from a large enough ordered set (thus, they are assumed to be distinct).
Seidel and Aragon [2] present simple algorithms for membership queries, insert and delete operations with expected time complexity logarithmic in the size of the set S stored in the treap. Random treaps may be easily converted into authenticated search data structures similarly to 2-3 trees. The communication costs of these schemes is similar since the expected depth of a random treap is similar to its 2-3 tree counterpart.
We now give details for the operations of the three parties in the system.
such that the value of 
(resp. 
) is smaller
(resp. larger)
than the queried serial number.
The user first verifies the CA's signature on the certificate and checks the certificate expiration date. Then, the user issues a query by sending the directory the certificate serial number s. Upon receiving the directory's answer to a query, the user verifies the CA's signature on the root value, tree height and time stamp.
The user checks that 
.
In the above scheme,
the communication costs of verifying that a certificate was not revoked may
be twice the communication costs of verifying that a certificate is in the
list. To overcome this, the tree may be built such that every node corresponds
to two consecutive serial numbers -- thus having to send only one path
in either case. Since the number of bits needed for holding the value of
a tree node, i.e. the hash function security parameter (
in the
notation below)
is more than twice the bits needed for holding a certificate
serial number, this does not influence the tree size.