SRPV: A Scalable Revocation Scheme for Pseudonyms-Based Vehicular Ad Hoc Networks

The cryptographic credentials of misbehaving vehicles should be revoked in a timely manner to prevent jeopardizing the network. However, the revocation is a challenging problem in VANETs because of its stringent privacy requirements and the large network scalability. Each vehicle receives a large number of unlinkable certified pseudonyms to protect privacy. Large storage and computation are required to store the revocation list and verify the authenticity of messages, respectively. In this paper, we propose a scalable revocation scheme that reduces the revocation list storage overhead and the revocation checking delay in pseudonym-based VANETs. The revocation of vehicle's credentials is achieved by adding a single trapdoor in a revocation list. The vehicles use the published trapdoors for revocation check by computing simple operations instead of sequentially searching a large set of pseudonyms. Chameleon hashing is used to generate the pseudonyms and revoke them if needed. Using computationally efficient multi-signature, vehicles can cooperatively vote to revoke the credentials of a misbehaved vehicle. The objective of using multi-signature is to increase the creditability of revocation requests. Our experiments and extensive evaluations show that our scheme can revoke a large number of pseudonyms with minimum storage and computation overhead.