Tsukada Lab. Computer Network Group

Let the Truth Tell: Zero-Knowledge Proof Mechanisms to Realize Fact-Based Cooperative ITS

Ye Tao

Ph.D. Thesis, The University of Tokyo (Esaki Lab), Mar 31, 2024

Summary in three lines

  • The thesis studies how vehicles can verify shared observations and claims in a decentralized cooperative ITS.
  • Zero-knowledge proofs enable cross-checking traffic observations while protecting information about the sender.
  • A separate protocol lets vehicles distinguish local pseudonym owners to resist Sybil attacks while preserving unlinkability.

Figures from the paper

Figure 3.1: Architecture of the Flowsim simulator
Figure 3.1. Architecture of the Flowsim simulatorSource: Figure 3.1 from Ph.D. thesis, The University of Tokyo, 2024 (author's version)Flowsim runs each vehicle in a sandbox and calls separate simulators for position, networking (ETSI GeoNetworking single-hop broadcast), camera perception and the match between number plates and V2X identities. It can co-simulate with SUMO and external network or perception simulators.
Figure 4.1: Procedure of a zero-knowledge proof of traffic
Figure 4.1. Procedure of a zero-knowledge proof of trafficSource: Figure 4.1 from Ph.D. thesis, The University of Tokyo, 2024 (author's version)Independent observations from different vehicles can corroborate a collective perception report without disclosing the sensitive observation itself.
Figure 5.2: Overview of the zk-PoDI protocol
Figure 5.2. Overview of the zk-PoDI protocolSource: Figure 5.2 from Ph.D. thesis, The University of Tokyo, 2024 (author's version)An authority gives each vehicle a secret solution and one equation per pseudonym. A vehicle combines its solution with its own equation and another vehicle's equation to produce a zk-SNARK proof, from which a verifier can confirm that the two pseudonyms belong to different vehicles without linking them.

Abstract

The Cooperative Intelligent Transportation System (C-ITS) represents a communication-based technological framework designed to facilitate the ex- change of information among vehicles. This exchange encompasses details pertaining to their presence, observations, and intentions, thereby contribut- ing to the realization of shared objectives, primarily safety and efficiency. Functioning as a distributed and ad-hoc system, C-ITS relies on both direct vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) communication protocols. Given its dynamic topology and intermittent global connectivity, C-ITS is susceptible to various cybersecurity threats. Threats such as data ma- nipulation, the creation of ghost vehicles, and the abuse of pseudonymous identities pose significant challenges. These threats can potentially lead to erroneous decision-making by the affected entities. Misbehavior detection (MBD) is an endeavor to detect and mitigate cyber-attacks in C-ITS. MBD is categorized into two types: data-centric approaches leverage plausibility and consistency to identify potential cyber threats; node-based approaches rely on the past behavior and reputation of a vehicle to assess its likelihood of engaging in dishonest activities. However, both approaches exhibit limitations. Data-centric approaches are constrained to detecting predefined misbehaviors and are susceptible to false positives and negatives. On the other hand, node-centric approaches suffer from high latency in establishing and updating trust assessments, including blocking ongoing attacks. In contrast, emerging technologies such as blockchain and cryptocurren- cies establish consensus through verifiable facts and employ game theory to discourage dishonest behavior. These fact-based approaches differ markedly from traditional C-ITS methods, which often assume a prevailing honesty among individuals. Demonstrating efficacy across various industries, includ- ing healthcare, education, logistics, and government, fact-based approaches exhibit notable potential for enhancing C-ITS. Several works proposed in this dissertation leverage these fact-based methodologies. In chapter 3, we introduced Flowsim, a novel simulator tailored for eval- uating Connected and Autonomous Vehicles (CAV) behavior and data flow in large-scale scenarios. The primary objective of Flowsim is to expedite the development and assessment of cybersecurity measures and protocols for CAVs, ensuring their safe and secure deployment. Beyond its focus on CAV evaluation, Flowsim demonstrates versatility in various use cases, including protocol evaluation, cybersecurity assessment, traffic optimization, and pol- icy development. The simulator’s extensible and playable open environment encourages the exploration of innovative algorithms and strategies for CAVs, fostering collaboration and innovation in research communities. Flowsim shows its significance in addressing the limitations of existing simulators for CAV behavior evaluation, specifically for its modularity, extensibility, and performance. In chapter 4, we introduced a novel deterministic cross-verification method named zero-knowledge Proof of Traffic (zk-PoT) within the context of cooper- ative perception. The zk-PoT protocol utilizes zero-knowledge proofs (ZKPs) to enable vehicles to independently prove their observations’ existence, allow- ing remote parties to cross-verify these observations without relying on the ground truth. The zero-knowledge property ensures that no additional in- formation is disclosed during this process, thereby safeguarding the location privacy of observed vehicles. Integration into existing cooperative perception standards, such as ISO and ETSI, requires minimal architectural changes and ensures backward compatibility. The study concludes with quantitative simu- lation analyses based on Flowsim in the scenario of a full-scaled Luxemburg city, demonstrating zk-PoT’s high success rate, low decision latency, and moderate resource assumption. Threat analyses indicate resilience against common attacks, making it a valuable standalone method or complementary to existing standards and trust management models. In chapter 5, we addressed the challenge of a type of Sybil attacks in C-ITS, caused by simultaneous usage of pseudonyms. We introduced a novel cryptographic protocol called zero-knowledge Proof of Distinct Identity (zk- PoDI). Based on the ”locality assumption,” wherein a vehicle need only prove its distinction from nearby vehicles rather than every vehicle globally, our proposed protocol zk-PoDI ensures that only a vehicle itself can prove it is not the owner of a given pseudonym locally, preventing Sybil attacks while pre- serving pseudonym unlinkability. The protocol’s practicality is highlighted by its zero latency, moderate computation overhead, and negligible commu- nication costs. zk-PoDI operates independently, without reliance on specific pseudonym system designs or additional knowledge. This feature together with the other practicality makes zk-PoDI ready to be integrated into C-ITS systems with any possible pseudonym designs. Looking ahead, the exploration of fact-based approaches in C-ITS is poised to continue. Empowered by innovations like zero-knowledge proofs and other cutting-edge techniques, we can anticipate the resolution of nu- merous challenges, the validation of truth, and the safeguarding of privacy within this domain.

How to cite

Y. Tao, “Let the Truth Tell: Zero-Knowledge Proof Mechanisms to Realize Fact-Based Cooperative ITS,” in Ph.D. Thesis, The University of Tokyo (Esaki Lab), 2024.

BibTeX

@phdthesis{Tao2024,
  title         = {Let the Truth Tell: Zero-Knowledge Proof Mechanisms to Realize Fact-Based Cooperative ITS},
  author        = {Ye Tao},
  year          = {2024},
  date          = {2024-03-31},
  school        = {Ph.D. Thesis, The University of Tokyo (Esaki Lab)},
  abstract      = {The Cooperative Intelligent Transportation System (C-ITS) represents a communication-based technological framework designed to facilitate the ex- change of information among vehicles. This exchange encompasses details pertaining to their presence, observations, and intentions, thereby contribut- ing to the realization of shared objectives, primarily safety and efficiency. Functioning as a distributed and ad-hoc system, C-ITS relies on both direct vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) communication protocols. Given its dynamic topology and intermittent global connectivity, C-ITS is susceptible to various cybersecurity threats. Threats such as data ma- nipulation, the creation of ghost vehicles, and the abuse of pseudonymous identities pose significant challenges. These threats can potentially lead to erroneous decision-making by the affected entities. Misbehavior detection (MBD) is an endeavor to detect and mitigate cyber-attacks in C-ITS. MBD is categorized into two types: data-centric approaches leverage plausibility and consistency to identify potential cyber threats; node-based approaches rely on the past behavior and reputation of a vehicle to assess its likelihood of engaging in dishonest activities. However, both approaches exhibit limitations. Data-centric approaches are constrained to detecting predefined misbehaviors and are susceptible to false positives and negatives. On the other hand, node-centric approaches suffer from high latency in establishing and updating trust assessments, including blocking ongoing attacks. In contrast, emerging technologies such as blockchain and cryptocurren- cies establish consensus through verifiable facts and employ game theory to discourage dishonest behavior. These fact-based approaches differ markedly from traditional C-ITS methods, which often assume a prevailing honesty among individuals. Demonstrating efficacy across various industries, includ- ing healthcare, education, logistics, and government, fact-based approaches exhibit notable potential for enhancing C-ITS. Several works proposed in this dissertation leverage these fact-based methodologies. In chapter 3, we introduced Flowsim, a novel simulator tailored for eval- uating Connected and Autonomous Vehicles (CAV) behavior and data flow in large-scale scenarios. The primary objective of Flowsim is to expedite the development and assessment of cybersecurity measures and protocols for CAVs, ensuring their safe and secure deployment. Beyond its focus on CAV evaluation, Flowsim demonstrates versatility in various use cases, including protocol evaluation, cybersecurity assessment, traffic optimization, and pol- icy development. The simulator’s extensible and playable open environment encourages the exploration of innovative algorithms and strategies for CAVs, fostering collaboration and innovation in research communities. Flowsim shows its significance in addressing the limitations of existing simulators for CAV behavior evaluation, specifically for its modularity, extensibility, and performance. In chapter 4, we introduced a novel deterministic cross-verification method named zero-knowledge Proof of Traffic (zk-PoT) within the context of cooper- ative perception. The zk-PoT protocol utilizes zero-knowledge proofs (ZKPs) to enable vehicles to independently prove their observations’ existence, allow- ing remote parties to cross-verify these observations without relying on the ground truth. The zero-knowledge property ensures that no additional in- formation is disclosed during this process, thereby safeguarding the location privacy of observed vehicles. Integration into existing cooperative perception standards, such as ISO and ETSI, requires minimal architectural changes and ensures backward compatibility. The study concludes with quantitative simu- lation analyses based on Flowsim in the scenario of a full-scaled Luxemburg city, demonstrating zk-PoT’s high success rate, low decision latency, and moderate resource assumption. Threat analyses indicate resilience against common attacks, making it a valuable standalone method or complementary to existing standards and trust management models. In chapter 5, we addressed the challenge of a type of Sybil attacks in C-ITS, caused by simultaneous usage of pseudonyms. We introduced a novel cryptographic protocol called zero-knowledge Proof of Distinct Identity (zk- PoDI). Based on the ”locality assumption,” wherein a vehicle need only prove its distinction from nearby vehicles rather than every vehicle globally, our proposed protocol zk-PoDI ensures that only a vehicle itself can prove it is not the owner of a given pseudonym locally, preventing Sybil attacks while pre- serving pseudonym unlinkability. The protocol’s practicality is highlighted by its zero latency, moderate computation overhead, and negligible commu- nication costs. zk-PoDI operates independently, without reliance on specific pseudonym system designs or additional knowledge. This feature together with the other practicality makes zk-PoDI ready to be integrated into C-ITS systems with any possible pseudonym designs. Looking ahead, the exploration of fact-based approaches in C-ITS is poised to continue. Empowered by innovations like zero-knowledge proofs and other cutting-edge techniques, we can anticipate the resolution of nu- merous challenges, the validation of truth, and the safeguarding of privacy within this domain.},
  keywords      = {ITS, Thesis},
  pubstate      = {published},
  tppubtype     = {phdthesis}
}