In this paper, we propose a lightweight mechanism for revoking security certificates appropriate for the limited bandwidth and hardware cost constraints of a VANET. A Certificate Authority (CA) issues certificates to trusted nodes, i.e., vehicles. If the CA looses trust in a node (e.g., due to evidence of malfunction or malicious behavior), the CA must promptly revoke the certificates of the distrusted node. To distribute revocation information quickly even during incremental deployment, we propose CAs use Certificate Revocation Lists (CRLs). The CRL should be composed in a secure manner, and it should be exchanged in a way such that the CRL is both quickly and widely distributed. Laberteaux et al.  proposed a mechanism for the quick distribution of CRL updates that also covers a wide area by using car-to-car (C2C) communication. However, this revocation process, which involves both the CA and VANET nodes, must conform to the aforementioned bandwidth and hardware restrictions. In this paper, we present mechanisms that achieve the goals of reduced CRL size, a computationally efficient mechanism for determining if a certificate is on the CRL, and a lightweight mechanism for exchanging CRL updates. Additionally, we present a formal proof of the security of our mechanism for reducing the size of CRLs.