Windowed Key Revocation in Public Key Infrastructures

A fundamental problem inhibiting the wide acceptance of a Public Key Infrastructure (PKI) in the Internet is the lack of a mechanism that provides scalable certificate revoca-tion. In this paper, we propose a novel mechanism called Windowed Revocation. In windowed revocation, certifi-cate revocation is announced for short periods in periodic Certificate Revocation Lists (CRLs). Due to the assur-ances provided by the protocol over which certificates are retrieved, we bound the amount of time that any certificate is cached by users. Thus, we can limit the announcement of revocation only to the time in which the certificate may be cached; not until its expiration. Because the time in which certificate are announced is short, CRLs are sim-ilarly small. By limiting the size of CRLs, we are able to integrate other mechanisms that increase the scalability of the PKI. One such mechanism is the use of “pushed” CRLs using multicast. We include a proof of the correct-ness of our approach.