  Standardization and harmonization efforts have reached a consensus towards
using a special-purpose Vehicular Public-Key Infrastructure (VPKI) in upcoming
Vehicular Communication (VC) systems. However, there are still several
technical challenges with no conclusive answers; one such an important yet open
challenge is the acquisition of shortterm credentials, pseudonym: how should
each vehicle interact with the VPKI, e.g., how frequently and for how long?
Should each vehicle itself determine the pseudonym lifetime? Answering these
questions is far from trivial. Each choice can affect both the user privacy and
the system performance and possibly, as a result, its security. In this paper,
we make a novel systematic effort to address this multifaceted question. We
craft three generally applicable policies and experimentally evaluate the VPKI
system performance, leveraging two large-scale mobility datasets. We consider
the most promising, in terms of efficiency, pseudonym acquisition policies; we
find that within this class of policies, the most promising policy in terms of
privacy protection can be supported with moderate overhead. Moreover, in all
cases, this work is the first to provide tangible evidence that the
state-of-the-art VPKI can serve sizable areas or domain with modest computing
resources.
