The Phantom Tollbooth: Privacy-Preserving Electronic Toll Collection in the Presence of Driver Collusion

In recent years, privacy-preserving toll collection has been proposed as a way to resolve the tension between the desire for sophisticated road pricing schemes and drivers’ interest in maintaining the privacy of their driving patterns. Two recent systems in particular, VPriv (USENIX Security 2009) and PrETP (USENIX Security 2010), use modern cryptographic primitives to solve this problem. In order to keep drivers honest in paying for their usage of the roads, both systems rely on unpredictable spot checks (e.g., by hidden roadside cameras or roaming police vehicles) to catch potentially cheating drivers.

In this paper we identify large-scale driver collusion as a threat to the necessary unpredictability of these spot checks. Most directly, the VPriv and PrETP audit protocols both reveal to drivers the locations of spot-check cameras—information that colluding drivers can then use to avoid paying road fees. We describe Milo, a new privacy-preserving toll collection system based on PrETP, whose audit protocol does not have this information leak, even when drivers misbehave and collude. We then evaluate the additional cost of Milo and find that, when compared to naïve methods to protect against cheating drivers, Milo offers a significantly more cost-effective approach.