5 Evaluation

The CA-to-directory communication costs of our scheme are optimal (proportional to the number of changes in the revocation list), enabling high update rates. The proof supplied by the directory is of length logarithmic in the number of revoked certificates. This allows the user to hold a short transferable proof of the validity of his certificate and present it with his certificate (This proof may be efficiently updated, we will make use of this feature in the certificate update scheme of Section 6).

In the following, we compare the communication costs of CRL, CRS and our system (the communication costs of CRT are similar to ours). Basing on this analysis, we show that the proposed system is more robust to changes in parameters, and allows higher update rates than the other.

Other advantages of the proposed scheme are:

• The CA has to keep a smaller secret than in CRS.
• Since CA-to-directory communication is low, the CA may communicate with the directory using a slow communication line secured against breaking into the CA's computer (the system security is based on the ability to protect the CA's secrets).
• Since we base our scheme on a 2-3 tree, there is never a need to re-compute the entire tree to update it. This allows higher update rates than CRT.
• Another consequence of the low CA-to-directory communication is that a CA may update many directories, avoiding bottlenecks in the communication network.

5.1 Communication costs

The parameters we consider are:

• n - Estimated total number of certificates (n=3,000,000).
• k - Estimated average number of certificates handled by a CA (k=30,000).
• p - Estimated fraction of certificates that will be revoked prior to their expiration (). (We assume that certificates are issued for one year, thus, the number of certificates revoked daily is .)
• q - Estimated number of certificate status queries issued per day (q=3,000,000).
• T - Number of updates per day (T=1).
• - Number of bits needed to hold a certificate serial number ().
• - Number of bits needed to hold the certificate revocation status numbers and ().
• - Length of signature ().
• - Security parameter for the hash function ().

Values for are taken from Micali [18], and are specific to our scheme.

CRL costs

• The CRL daily update cost is since each CA sends the whole CRL to the directory in each update. An alternative update procedure where the CA sends to the directory only a difference list (which serial numbers to add/remove from the previous CRL) costs .
• The CRL daily query cost is since for every query the directory sends the whole CRL to the querying user.

CRS costs:

• The CRS daily update cost is since for every certificate the CA sends bits of certificate revocation status.
• The CRS daily query cost is .

The proposed scheme:

• To update the directory, the CA sends difference lists of total daily length of .
• To answer a user's query, the directory sends up to numbers, each bits long, totaling bits.

The following table shows the estimated daily communication costs (in bits) according to the three schemes.

As shown in the table, the proposed scheme costs are lower than CRL costs both in CA-to-directory and in directory-to-users communication. The CA-to-directory costs are much lower than the corresponding CRS costs but, the directory-to-user (and thus the over all) communication costs are increased. Note that in practice, due to communication overheads, the difference between CRS and the proposed method in Directory-to-users communication may be insignificant.

5.2 Robustness to changes

Our scheme is more robust to changes in parameters than CRL and CRS. Since these are bound to change in time or due to the specific needs of different implementations, it is important to have a system that is robust to such changes.

Changes will occur mainly in the total number of certificates (n) and the update rate (T). In the proposed method, changes in n are moderated by a factor of p. Changes in T are moderated by the fact that the update communication costs are not proportional to nT but to T. Figure 1 shows how the CA-to-directory update communication costs of the three methods depend on the update rate (all other parameters are held constant). The update communication costs limit CRS to about one update a day (Another factor that limits the update rate is the amount of computation needed by a user in order to verify that a certificate was not revoked). The proposed method is much more robust, even allowing once per hour updates.

 
Figure 1: Daily CA-to-directory update costs vs. update rate.