SPEcTRe

Traditional stop-and-pay toll booths inconvenience drivers and are infeasible for complicated urban areas. As a way to minimize traffic congestion and avoid the inconveniences caused by toll booths, electronic tolling has been suggested. For example, as drivers pass certain locations, a picture of their licence plate may be taken and a bill sent to their home. However, this simplistic method allows the administrator of the system to build a dossier on drivers. While this may be an attractive feature for law enforcement, a society may not wish to trust the tolling agency with such detailed information. We present SPEcTRe, a suite of protocols to maintain driver privacy while ensuring that tolls are accurately collected. Existing protocols for privacy-preserving electronic toll pricing suffer from computational challenges and require an undesirable amount of location data to be collected. We present two schemes: the spot-record scheme, which requires the same amount of location data exposure as prior privacy-preserving schemes, but runs much faster, and the no-record scheme, which collects no location information from honest users and is still able to run efficiently.