Reducing the Communication Overhead of an Offline Revocation Dictionary

Abstract

A Public Key Infrastructure (PKI) is required to securely deliver public-keys to widely-distributed users or systems. The public key is usually made public by war of a digital document called Identity Certificate (IC). ICs are valid during quite lang periods of time (usually up to several years). However, there are circumstances under which the validity of an IC wust be terminated sooner than assigned and thus, the IC needs to be revoked. The Revocation Dictionary (RD) can be defined as the cryptographic structure that contains the status data about the revoked certificates of the PKI domain. Three basic operations can be performed over the RD: add status data, remove status data and request the RD to tell us whether certain status data is contained by the RD or not. The last operation is called “status checking” and it is relevant to the PKI performance. In this paper we propose an efficient war of implementing a RD that can be distributed offline and that minimizes the communication overhead of the status checking process. The statistics of the status checking are used, like in the Huffman algorithm for source coding, for building an unbalanced hash tree that minimizes the length of the RD response.