  In spite of progress in securing Vehicular Communication (VC) systems, there
is no consensus on how to distribute Certificate Revocation Lists (CRLs). The
main challenges lie exactly in (i) crafting an efficient and timely
distribution of CRLs for numerous anonymous credentials, pseudonyms, (ii)
maintaining strong privacy for vehicles prior to revocation events, even with
honest-but-curious system entities, (iii) and catering to computation and
communication constraints of on-board units with intermittent connectivity to
the infrastructure. Relying on peers to distribute the CRLs is a double-edged
sword: abusive peers could "pollute" the process, thus degrading the timely
CRLs distribution. In this paper, we propose a vehicle-centric solution that
addresses all these challenges and thus closes a gap in the literature. Our
scheme radically reduces CRL distribution overhead: each vehicle receives CRLs
corresponding only to its region of operation and its actual trip duration.
Moreover, a "fingerprint" of CRL 'pieces' is attached to a subset of
(verifiable) pseudonyms for fast CRL 'piece' validation (while mitigating
resource depletion attacks abusing the CRL distribution). Our experimental
evaluation shows that our scheme is efficient, scalable, dependable, and
practical: with no more than 25 KB/s of traffic load, the latest CRL can be
delivered to 95% of the vehicles in a region (50x50 KM) within 15s, i.e., more
than 40 times faster than the state-of-the-art. Overall, our scheme is a
comprehensive solution that complements standards and can catalyze the
deployment of secure and privacy-protecting VC systems.
