It is well recognized that security plays a vital for the trustworthy operation of Vehicular Ad-hoc NETworks (VANETs). One of the critical sanctuary issues is the revocation of misbehaving vehicles, which is essential for the prevention of malicious vehicles from other vehicles. Vehicular Ad-hoc NETworks (VANETs) adopt the Public Key Infrastructure (PKI) and Certificate Revocation Lists (CRLs) for their security. In this paper, an Expedite Message Authentication Protocol (EMAP) for VANETs, this replaces the time-consuming CRL checking process by an efficient revocation checking process. The revocation check process in EMAP uses a keyed hash message authentication code shared only between non revoked On-Board Units (OBUs).