In urban vehicular networks, where privacy, especially the location privacy of anonymous vehicles is highly concerned,anonymous verification of vehicles is indispensable. Consequently, an attacker who succeeds in forging multiple hostile identifies caneasily launch a Sybil attack, gaining a disproportionately large influence. In this paper, we propose a novel Sybil attack detectionmechanism, Footprint, using the trajectories of vehicles for identification while still preserving their location privacy. More specifically,when a vehicle approaches a road-side unit (RSU), it actively demands an authorized message from the RSU as the proof of theappearance time at this RSU. We design alocation-hiddenauthorized message generation scheme for two objectives: first, RSUsignatures on messages aresigner ambiguousso that the RSU location information is concealed from the resulted authorizedmessage; second, two authorized messages signed by the same RSU within the same given period of time (temporarily linkable) arerecognizable so that they can be used for identification. With the temporal limitation on the linkability of two authorized messages,authorized messages used for long-term identification are prohibited. With this scheme, vehicles can generate a location-hiddentrajectory for location-privacy-preserved identification by collecting a consecutive series of authorized messages. Utilizing socialrelationship among trajectories according to the similarity definition of two trajectories, Footprint can recognize and therefore dismiss“communities” of Sybil trajectories. Rigorous security analysis and extensive trace-driven simulations demonstrate the efficacy of Footprint.

PDF