Some protocols avoid the need for a revocation system by using short-term certificates. (e.g. micropayments protocols when a certificate owner may cause a limited damage [13]). These certificates are issued daily and expire at the end of the day of issue. Actually, even shorter periods are desired and the main limit is due to the increase in the certification authority computation (certificates for all users have to be computed daily) and communication (certificates should be sent to their owners) short-term certificates cause.
An on-line/off-line digital signature scheme (like CRS) will reduce the computation the CA has to perform, but, it will not reduce significantly the communication costs, since the CA has to send different messages to different users, making the CA a communication bottleneck. This calls for a solution where the CA performs a simple computation (say, concerning only new users and users whose certificates are not renewed) and sends a common update message to all users. Using this message, exactly all users with non-revoked certificates should be able to prove the validity of their certificates.
We suggest a simple modification of our certificate revocation scheme that yields an efficient certificate update scheme in which the CA sends the same update message to all users. In this solution we do not assume the existence of a directory with information about all certificates, but of local directories that may hold the latest messages that were sent by the directory.
As before, the scheme is based on a tree of revoked certificates created by the certification authority, presented in Section 4.1. Since there is no way to extract certificates from a directory, every user gets an initial certificate that may be updated using the CA's messages. Specifically, the CA augments every issued certificate with the path proving its validity, this is the only part of the certificate that is updated periodically.
To update all certificates simultaneously, the CA updates its copy of the tree, and publishes the tree paths that where changed since the previous update. Every user holding a non-revoked certificate locates the lowest node, v, on a path that coincides with his path, and updates his path by copying the new node values from v up to the root. All users holding a revoked certificate can not update their path, unless a collision is found for the hash function h.
The information sent by the CA is optimal (up to a factor of 
).
For r insertions/deletions since the previous update, the CA has
to publish a message of length 
bits.
Since the CA communication is reduced, one may use this update scheme for, say, updating certificates once every hour. This may cause some users to lag in updating their certificates, and the local directories should save several latest update messages, and some aggregate updates (combining update messages of a day) enabling uses that lag several days to update their certificates.