  In this paper we propose a novel abstraction that we have named
Range-Revocable Pseudonyms (RRPs). RRPs are a new class of pseudonyms whose
validity can be revoked for any time-range within its original validity period.
The key feature of RRPs is that the information provided to revoke a pseudonym
for a given timerange cannot be linked with the information provided when using
the pseudonym outside the revoked range. We provide an algorithm to implement
RRPs using efficient cryptographic primitives where the space complexity of the
pseudonym is constant, regardless of the granularity of the revocation range,
and the space complexity of the revocation information only grows
logarithmically with the granularity; this makes the use of RRPs far more
efficient than the use of many short-lived pseudonyms. We have used RRPs to
design EDGAR, an access control system for VANET scenarios that offers backward
unlinkability. The experimental evaluation of EDGAR shows that, when using
RRPs, the revocation can be performed efficiently (even when using time slots
as small as 1 second) and that users can authenticate with low latency
($0.5-3.5$ ms).

Cryptography and Security