  Any on-demand pseudonym acquisition strategy is problematic should the
connectivity to the credential management infrastructure be intermittent. If a
vehicle runs out of pseudonyms with no connectivity to refill its pseudonym
pool, one solution is the on-the-fly generation of pseudonyms, e.g., leveraging
anonymous authentication. However, such a vehicle would stand out in the crowd:
one can simply distinguish pseudonyms, thus signed messages, based on the
pseudonym issuer signature, link them and track the vehicle. To address this
challenge, we propose a randomized hybrid scheme, RHyTHM, to enable vehicles to
remain operational when disconnected without compromising privacy: vehicles
with valid pseudonyms help others to enhance their privacy by randomly joining
them in using on-the-fly self-certified pseudonyms along with aligned
lifetimes. This way, the privacy of disconnected users is enhanced with a
reasonable computational overhead.
