Wagner and Eckhoff survey simulation-based assessments of privacy in vehicular networks . They find that 70% of the papers covered assume an attacker with global coverage, which we argue is unrealistic. The survey criticizes unrealistic mobility models such as the random waypoint model and the widespread use of simplistic traffic scenarios such as Manhattan grids for urban scenarios or straight lines for highways.
There are several approaches for modeling location privacy and we provide an overview in Section 2.2.2. Shokri et al. propose a generic framework for modeling location privacy . Our approach could be expressed in terms of their framework but is more specific, as we focus on IVC specific pseudonym changes and an adversary with limited coverage.
There is a large body of research on pseudonym schemes in vehicular networks, of which Petit et al. provide an excellent survey . Yet, little guidance exists on performance of different pseudonym schemes, their suitability for practical deployment, and when and how often pseudonyms should be changed.
The most common approach is for each vehicle to periodically change its pseudonym every x seconds (we call this the periodic change strategy). Gerlach and Guttler describe that pseudonym changes are more effective in certain contexts than in others . Building on this notion, Liao and Li propose that several vehicles cooperate and try to change their pseudonym at the same time  (we call this the synchronous pseudonym change strategy). Eckhoff et ad. introduce time-slotted pseudonym changes where pseudonyms are valid for fixed time intervals and all vehicles change their pseudonyms simultaneously .
In the context of location-based services, Beresford and Stajano describe that an observer can resolve pseudonym changes that happen in his reception area if the subject is sending messages with a high frequency . For vehicular communication, Wiedersheim et al. obtain similar results, showing that nodes that emit messages with a high frequency can be tracked by an observer with global coverage even if messages contain no identifiers at all .
To provide a context where pseudonymous identifiers can be changed privately, Beresford and Stajano suggest the placement of mix-zones in which users do not send any messages . There are several suggestions to apply this concept to VANETs in order to avoid tracking by a global attacker: Huang et al. propose silent periods after pseudonym changes, during which vehicles do not send any messages , and this suggestion is used in several other pseudonym schemes, e.g., CARAVAN , AMOEBA , SLOW , and more recently VLPZ . Freudiger et al. propose to establish cryptographic mix-zones at predefined locations in which all communication is encrypted to avoid eavesdropping by outsiders, using symmetric keys that are distributed by road-side units and forwarded among vehicles . They also provide recommendations about the optimal placement of mix-zones . Unfortunately, all of these approaches can affect V2X-based safety functions when sending of CAM messages is suppressed by silent periods or when messages may be inaccessible to some participants due to encryption. Lefevre et al. find that longer silent periods greatly reduce the effectiveness of V2X-based collision avoidance systems , which challenges the protocols’ suitability for practical deployment.
There are several suggestions for using privacy-friendly cryptographic primitives such as group signatures and anonymous credentials for authentication of V2X messages. These suggestions have drawbacks with regard to short-term linkability of messages and performance, which we discuss in more detail in
Beresford and Stajano also present an analytic model for the location privacy provided by mix-zones. They describe an attacker that tries to resolve pseudonym changes by calculating the maximum weight matching in a bipartite assignment graph . Buttyan et al. use a simulation-based approach to assess the location privacy provided by pseudonym changes in vehicular networks. Their attacker only tracks a single, randomly chosen vehicle whereas in our work the attacker tries to track all vehicles. Their tracking success is rather high, but the applicability of their results is limited by the simplified traffic scenario and the use of simplistic, random traffic flows . Troncoso et al. examine reuse of pseudonyms in a Manhattan grid simulation scenario . They conclude that the attacker can learn all pseudonyms that belong to one vehicle using a clustering approach and that pseudonym reuse should be avoided. Tomandl et al. perform a simulation-based evaluation of the privacy achieved by silent periods and mix-zones in VANETs and find that their attacker can resolve pseudonym changes with a high success rate . While they use realistic maps for their simulations, silent periods and explicit placement of mix-zones are hardly realistic for real-world VANET deployments. Pan and Li create an analytic model to evaluate cooperative pseudonym changes . They also perform a simulation-based evaluation but use only small, simplistic traffic scenarios. Petit et al. provide a rare evaluation of pseudonym changes based on real-life mobility data . Using an attacker with limited coverage they achieve a relatively high tracking success, but their scenario of tracking a single vehicle within a university campus is rather limited. Ma et al. demonstrate threats to location privacy in VANETs posed by accumulated observations over a period of several weeks or months but focus on a theoretical analysis and do not conduct detailed traffic simulations .
There are several works evaluating the location privacy provided by pseudonym changes using simulations. Additionally, most proposals for new strategies or pseudonym systems are accompanied by a simulation-based evaluation. Yet, most simulations use simplistic maps and randomly generated traffic. To our knowledge there is no comprehensive evaluation in a large-scale simulation with realistic traffic patterns, which motivates us to fill this gap.