Public-key cryptography is widely used as the underlying mechanism for securing many protocols and applications in the Internet. 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 way of a digital document called a certificate. Certificates are valid during a certain period of time, however, there are circumstances under which the validity of a certificate must be terminated sooner than assigned and thus, the certificate needs to be revoked. The revocation of certificates implies one of the major costs of the whole PKI. The goal of this paper is to present an efficient offline revocation system based on the Merkle Hash Tree (MHT) named Enhanced-MHT (E-MHT). The authors propose several mechanisms that allow the E-MHT to provide a response size that is close to (or even better than) online systems. These mechanisms include the optimization of the MHT aths for non-revoked certificates, the division of the status data among multiple MHTs and a low cost mechanism for re-utilization of MHT digests and E-MHT responses. Furthermore, an ASN.1 protocol for the E-MHT is introduced and discussed. Finally, a performance evaluation of the E-MHT using this protocol is presented.