Digital signatures are one of the fundamental security primitives in Vehicular Ad-Hoc Networks (VANETs) because they provide authenticity and non-repudiation in broadcast communication. However, the current broadcast authentication standard in VANETs is vulnerable to signature flooding: excessive signature verification requests that exhaust the computational resources of victims. In this paper, we propose two efficient broadcast authentication schemes, Fast Authentication (FastAuth) and Selective Authentication (SelAuth), as two countermeasures to signature flooding. FastAuth secures periodic single-hop beacon messages. By exploiting the sender's ability to predict its own future beacons, FastAuth enables 50 times faster verification than previous mechanisms using the Elliptic Curve Digital Signature Algorithm. SelAuth secures multi-hop applications in which a bogus signature may spread out quickly and impact a significant number of vehicles. SelAuth pro- vides fast isolation of malicious senders, even under a dynamic topology, while consuming only 15%--30% of the computational resources compared to other schemes. We provide both analytical and experimental evaluations based on real traffic traces and NS-2 simulations. With the near-term deployment plans of VANET on all vehicles, our approaches can make VANETs practical.

This paper proposes novel certificate assignment strategies for use in vehicular networks in order to significantly reduce the complexity of managing the public key infrastructure (PKI) framework. The strategy involves segmenting a country into a number of geographic regions, and the assignment of region-specific certificates to an OBU resident on a vehicle. A vehicle is also assigned multiple certificates corresponding to several regions in its vicinity as advance preparation for migration into nearby regions. Segmentation based on geographic regions is shown to significantly reduce the size of certificate revocation lists (CRLs). Next, a scalable design for the back-end certifying authority (CA) with region-based certificates is presented. The paper concludes with a simple analysis of the performance of the proposed strategies.