Conditional Privacy-preserving Authentication and Message Dissemination Scheme using Timestamp based Pseudonyms for VANETs

Many of the privacy-preserving authentication and message dissemination approaches presented in the literature for Vehicular Ad Hoc Networks (VANETs) use pseudonyms. Under these schemes, each vehicle is assigned a set of pseudonyms by a central authority and the vehicles use these pseudonyms in all communications to preserve their privacy. Vehicles change their pseudonym (choosing from the pool of pseudonyms assigned) to prevent from being tracked. For authenticating a message sent by a vehicle using its pseudonym, certificate of the pseudonym signed by the central authority is used. When a vehicle is found to be malicious, the certificates issued for all the pseudonyms assigned to that vehicle have to be revoked. The list of certificates revoked need to be communicated to all entities that will correspond with the vehicle and they will store them in their certificate revocation list (CRL). Since the pool of pseudonyms allocated to each vehicle is large (assuming a vehicle changes pseudonym every 5 minutes, it will need more than 100,000 pseudonyms in a year) number of pseudonyms, the CRL can grow very large as the number of vehicles revoked increases which will result in high storage overhead (for storing CRL) and authentication overhead (because each time a message is received, the receiver has to check its CRL to see if that pseudonym). In this paper, we address this issue and present a timestamp based pseudonym allocation scheme.