IBRS: An Efficient Identity-based Batch Verification Scheme for VANETs Based on Ring Signature

Feng Liu, Qi Wang

TL;DR

This paper introduces IBRS, a novel identity-based ring signature scheme for Vehicular Ad-hoc Networks (VANETs) that balances privacy, security, and auditability. By utilizing Road-Side Units (RSUs) to distribute verified lists of ring members and employing batch verification, the scheme prevents malicious nodes from disrupting communications while significantly reducing computational and communication overhead.

What Problem Does This Paper Address?

In Vehicular Ad-hoc Networks (VANETs), cars constantly broadcast traffic and safety information. This creates a complex security trilemma:

  1. Authentication: Vehicles must know a message is legitimate.
  2. Privacy: Drivers shouldn't be tracked by eavesdroppers.
  3. Auditability: If a vehicle broadcasts malicious or fake data (e.g., causing a crash), law enforcement must be able to trace the message back to the real driver.

Traditional Public Key Infrastructure (PKI) and simple pseudonym schemes struggle here; they either require massive overhead to constantly change certificates or fail to provide true anonymity. Ring signatures—where a sender hides their identity within a "ring" of other users' public keys—offer a great solution for privacy. However, existing ring signature schemes in VANETs have a fatal flaw: if a vehicle randomly collects public keys from nearby cars to form a ring, a malicious car can inject an invalid public key. This "poisons" the ring, causing the final signature to fail verification for everyone else. Furthermore, existing schemes struggle to provide an efficient way for authorities to trace bad actors.

Methods

The authors propose a hybrid Identity-Based Cryptography (IBC) and ring signature scheme with a few key architectural shifts:

  • RSU-Managed Ring Lists: Instead of vehicles building their own rings by sniffing local traffic, they request a "ring list" from a local RSU. The RSU checks a revocation list and securely delivers a list of valid pseudonyms to the vehicle. This eliminates the "poisoned ring" problem.
  • Identity-Based Ring Signatures: The scheme uses an IBC ring signature approach where a vehicle's public key is derived directly from its pseudonym, eliminating the need to attach bulky certificates to every message.
  • Batch Verification: Because vehicles in dense traffic receive hundreds of messages per second, verifying them one by one is computationally impossible for standard On-Board Units (OBUs). The authors implement a batch verification mode that allows an OBU to verify multiple signatures simultaneously using bilinear pairings.
  • Built-in Traceability: The scheme introduces a Law Enforcement Authority (LEA) entity. The LEA holds a private tracing key that, when combined with the Transportation Regulation Center's (TRC) data, can extract the true identity of a signer from the ring signature.

Datasets

Not discussed in the paper. (The authors evaluated their scheme using real-world cryptographic benchmarks on hardware rather than using a specific vehicular dataset).

Key Insights and Ideas

  • Gatekeeping the Ring is Crucial: Allowing decentralized, ad-hoc ring formation in VANETs is too vulnerable to disruption. Centralizing the distribution of ring members at the RSU level ensures cryptographic integrity without sacrificing the decentralized nature of V2V message verification.
  • Curve Selection Drives Efficiency: The authors deliberately chose an asymmetric bilinear pairing (Type 3 on the MNT159 curve) over symmetric curves (like SS512). This allows for a much shorter mathematical representation of group elements, which drastically cuts down the communication payload size.
  • Batching Changes the Math: While generating a ring signature is somewhat computationally heavy, the real bottleneck in VANETs is the receiver verifying hundreds of incoming messages. By enabling batch verification, the computational cost scales sub-linearly, making ring signatures practically viable for real-time automotive hardware.

Key Results

The authors implemented the cryptographic operations using the CHARM framework on a Raspberry Pi 3b+ (1.4 GHz ARM, 1GB RAM) to simulate a low-cost vehicle OBU.

  • Communication Overhead: IBRS is highly efficient. A single pseudonym requires only 30 bytes, and a single signature requires 90 bytes. For comparison, a competing scheme by Zeng et al. requires 90 bytes for a pseudonym and 936 bytes for a signature.
  • Computation Speed: For a ring size of 2 (which the authors argue is sufficient for basic VANET privacy), signing takes ~127ms and a single verification takes ~255ms.
  • Batch Scaling: When batch verification is applied, the time required to verify multiple messages drops dramatically compared to sequential verification, proving the scheme can handle high-density traffic scenarios.

Limitations and Future Work

  • Invalid Signature Isolation: A known limitation of batch verification is that if even one signature in the batch is invalid, the entire batch fails the check. Due to space constraints, the authors did not include the algorithm for isolating and dropping the specific invalid signature from a failed batch. They note this as a primary direction for future work.
  • Hardware Assumptions: The scheme assumes the presence of Hardware Security Modules (HSMs) in the vehicles. The authors suggest future work should explore implementing these HSMs using real-world Trusted Execution Environments (TEEs), such as ARM's TrustZone.

Summary updated

Abstract

Vehicular ad-hoc networks (VANETs) are one of the most important components in an Intelligent Transportation System (ITS), which aims to provide information communication between vehicles. Safety-critical vehicular communication requires security, privacy, auditability and efficiency. To satisfy these requirements simultaneously, several conditional privacy-preserving authentication schemes are proposed by employing ring signatures. However, these methods have been paid too little attention to the issues like how to choose the valid ring members or how to set up a ring. In this paper, we introduce an efficient conditional privacy-preserving scheme which provides an appropriate approach establishing the list of ring members. Moreover, our proposed scheme also supports batch verification to significantly reduce the computational cost. According to the analysis of security, our scheme is sufficiently resistant against several common attacks in VANETs. The performance results show that the proposed scheme is efficient and practical with both low computation and communication cost.
BibTeX
@inproceedings{liu2019ibrs,
  author = {Feng Liu and Qi Wang},
  title = {{IBRS: An Efficient Identity-based Batch Verification Scheme for VANETs Based on Ring Signature}},
  booktitle = {VNC},
  year = {2019},
  url = {https://openreview.net/forum?id=th_bJwCHWo},
}

Loading related content...

Figure