This paper introduces an efficient and spontaneous privacy-preserving
protocol for vehicular ad-hoc networks based on revocable ring signature. The
proposed protocol has three appealing characteristics: First, it offers
conditional privacy-preservation: while a receiver can verify that a message
issuer is an authorized participant in the system only a trusted authority can
reveal the true identity of a message sender. Second, it is spontaneous: safety
messages can be authenticated locally, without support from the roadside units
or contacting other vehicles. Third, it is efficient by offering fast message
authentication and verification, cost-effective identity tracking in case of a
dispute, and low storage requirements. We use extensive analysis to demonstrate
the merits of the proposed protocol and to contrast it with previously proposed
solutions.