Privacy-Preserving Billing for e-Ticketing Systems in Public Transportation

Florian Kerschbaum, Hoon Wei Lim, Ivan GudymenkoIACR ePrint 2013 · DOI

TL;DR

This paper tackles the privacy invasion inherent in public transportation e-ticketing systems by proposing a novel, privacy-preserving billing mechanism. It demonstrates how existing systems like Singapore's EZ-Link leak sensitive travel data and introduces a solution using homomorphic encryption to process travel records securely, enabling monthly billing and data mining without compromising user privacy.

What Problem Does This Paper Address?

Public transportation systems worldwide are increasingly adopting electronic ticketing for convenience. While these systems offer benefits like ease of use and flexible tariffs, they also create a significant privacy risk. Each electronic ticket acts as a unique identifier, allowing transportation companies to collect and link detailed travel records for every commuter. This creates a comprehensive profile of an individual's movements, which can be a substantial invasion of privacy. The paper highlights this issue by analyzing Singapore's EZ-Link system, showing how easily travel data can be accessed. Furthermore, existing privacy-preserving solutions often only support upfront payments and do not allow for the valuable data mining that transportation companies need for service improvement. This paper aims to bridge this gap by offering a solution that preserves privacy while still enabling monthly billing and data mining.

Methods

The core of the proposed solution lies in partially homomorphic encryption, specifically using Paillier's encryption scheme. This allows computations to be performed on encrypted data without decrypting it. The system employs a zero-knowledge proof (ZKP) for card authentication, ensuring that the card's identity remains anonymous to the system.

Key methodological contributions include:

  • Privacy-Preserving Bill Processing: Travel records (location and time) are encrypted using Paillier's scheme. The transportation company can then process these encrypted records to compute monthly bills. This is achieved through a series of operations on encrypted bits, including logical AND and negation, which are enabled by the homomorphic properties of Paillier encryption.
  • Anonymous Card Authentication: A ZKP protocol, adapted from Schnorr's scheme but using Paillier encryption instead of discrete logarithms, is used to authenticate cards without revealing their actual identity.
  • Privacy-Preserving Data Mining: The homomorphic encryption allows for data mining on encrypted travel records. The paper demonstrates how to compute a histogram of frequently used routes, enabling network optimization and other analyses without compromising user privacy.
  • Distributed Negation Service: To manage the computational overhead of negation operations, a distributed service involving multiple authorities is proposed.

Datasets

Not discussed in the paper. The paper focuses on analyzing an existing system (Singapore's EZ-Link) and proposing a theoretical and implemented solution, rather than training or evaluating on specific datasets.

Key Insights and Ideas

  • EZ-Link's Vulnerability: The paper's analysis of the EZ-Link system reveals a surprisingly straightforward method for adversaries to obtain detailed travel records using readily available tools, underscoring the urgent need for better privacy protections in real-world systems.
  • Homomorphic Encryption as a Privacy Enabler: The core insight is that homomorphic encryption, while computationally more expensive, is a powerful tool for enabling both privacy-preserving billing and data mining simultaneously, a feat not achieved by previous approaches.
  • Monthly Billing is Achievable with Privacy: Unlike many prior privacy-focused solutions that rely on upfront payments (akin to electronic cash), this work demonstrates that monthly billing, a more convenient and flexible model for both users and providers, can be implemented securely.
  • Trade-off Between Privacy and Performance: The paper explicitly acknowledges that achieving strong privacy comes at a computational cost, particularly for the back-end processing. However, it argues that this cost is "expensive, but achievable," especially when computations can be performed offline.

Key Results

  • Demonstrated Privacy Leakage: The paper successfully demonstrated how to extract travel records from the EZ-Link system using traffic analyzers and a contactless card reader.
  • Feasibility of Privacy-Preserving Solution: A proof-of-concept implementation of the authentication protocol showed comparable front-end computational overhead to EZ-Link. The back-end processing of encrypted data was found to be costly but feasible due to off-line processing and parallelization.
  • Theoretical Guarantees: The paper provides theoretical security proofs (Theorems 1-3) demonstrating that the transportation company cannot distinguish between user identifiers or locations from encrypted travel records, and that the card authentication protocol is sound and zero-knowledge.

Limitations and Future Work

  • Computational Cost: The primary limitation acknowledged is the significant computational overhead associated with homomorphic encryption, particularly for the back-end operations. While parallelization and off-line processing mitigate this, it remains a challenge.
  • Trusted Authorities: The proposed solution relies on trusted authorities for key management and potentially for decryption of aggregated data. The authors identify the elimination or reduction of the need for these trusted authorities as a key open problem.
  • Efficiency Improvements: The paper suggests that further optimization of the protocol and advancements in high-performance parallel computing are needed to make the solution more practical and efficient.
  • Differential Privacy: While the proposed solution protects privacy against direct observation of travel records, the authors note that data mining outputs could still potentially lead to inferences. They suggest incorporating differential privacy mechanisms to address this.

Summary updated

BibTeX
@article{kerschbaum2013privacy,
  author = {Florian Kerschbaum and Hoon Wei Lim and Ivan Gudymenko},
  title = {{Privacy-Preserving Billing for e-Ticketing Systems in Public Transportation}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2013},
  doi = {10.1145/2517840.2517848},
}
Figure