We present PrETP, a privacy-preserving road charging system in which clients are charged depending on parameters such as the distance driven, the kind of road used, or the time of usage. As opposed to current implementations, which rely on clients sending fine-grained location data to the service provider threatening users' privacy, PrETP allows clients to prove that they use genuine data and perform correct operations while disclosing the minimum amount of location data.

PrETP is based on a de-centralized architecture in which each vehicle carries an on-board unit (OBU) that computes locally the final fee to pay. Further, OBUs use advanced cryptographic techniques to prove its honest behaviour towards the service provider. Hence, the toll service provider is ensured that the toll collection corresponds to the actual road usage.

We provide a prototype implementation of PrETP on an embedded platform, and demonstrate that the cryptographic overhead is efficient enough to be practically deployed in commercial in-car devices. Further, the fact that on-board units carry out all operations without interaction with the driver makes our system ideal in terms of usability.

Our system is suitable to be integrated into the European Electronic Toll Service (EETS), approved by the European Comission in October 2009.