Performance evaluation of public-key certificate revocation system with balanced hash tree

A new method for updating certificate revocation trees (CRT) is proposed. Efficient revocation of public-key certificates is a current issue in public-key infrastructure because a traditional certificate revocation list uses a large amount of bandwidth. A certificate revocation tree is a hash tree of revoiced certificates and reduces a bandwidth consumption up to O(log(n)). In this paper, an implementation of certificate revocation tree with S-expression is presented and the performance of the system is evaluated in terms of communication and computational costs. To update a CRT, we have two algorithms; (1) random insertion-a new certificate to be revoiced is just inserted into the existing tree and (2) balancing updating-balances CRT every time a new certificate is added.