Efficient user revocation for privacy-aware PKI

Wei Ren, Kui Ren, Wenjing Lou, Yanchao ZhangQSHINE 2008 · DOI

Abstract

This paper proposes Delta-RL, a hybrid revocation scheme designed for privacy-aware Public Key Infrastructure (PKI). Utilizing group signatures to maintain user anonymity, the scheme balances security requirements with system performance. By combining periodic updates with incremental "delta" revocation lists and a mathematically derived threshold for full key re-distribution, Delta-RL significantly reduces the communication and computation overhead typically associated with user revocation in anonymous networks.

Introduction

In privacy-aware PKI systems, such as those deployed in vehicular ad-hoc networks (VANETs) or mobile sensor arrays, users must prove authorization without compromising their specific identity. Group signatures facilitate this by allowing a verifier to confirm a signer belongs to a legitimate group without identifying the individual. However, revoking a user—due to subscription expiry or key compromise—presents a significant challenge. Traditional revocation lists (RLs) grow linearly, imposing a "verification tax" on every transaction. Conversely, frequent full-system re-keying creates massive communication bottlenecks. The authors address these challenges by optimizing the revocation process across communication, computation, and storage dimensions.

Methodology: The Delta-RL Scheme

The authors analyze three baseline approaches: Periodic Revocation (PR) for scheduled expirations, Timely Revocation (TR) for immediate emergency re-keying, and Revocation List Schemes (RLS) for local verification. To address the inefficiencies of these methods, they introduce Delta-RL (DRL).

Structure of the Delta-RL scheme showing time slots and incremental updates.

Delta-RL employs several key innovations:

  1. Incremental Updates: Instead of broadcasting the entire RL, the Trusted Third Party (TTP) transmits "deltas"—specific tokens to be added (revocation) or removed (revival).
  2. Hybrid Logic: The system supports dynamic group membership where users can be reinstated after temporary suspension, managing both additions and deletions from the list.
  3. Threshold-Based Reset: Using queueing theory (specifically M/M/1/N and M/D/1 models), the authors calculate a threshold ($T_{th}$). When the cost of checking an ever-growing RL exceeds the cost of a full key reset, the system triggers a re-distribution and clears the list.

Analysis and Results

The evaluation relies on extensive mathematical modeling and numerical analysis. User behavior regarding revocation and revival is modeled as Poisson processes, using parameters representative of typical secure systems.

Threshold time ($T_{th}$) as a function of the number of revoked users across various signature arrival rates.

Key findings include:

  • Efficiency of Deltas: Sending only changes is consistently more efficient than full list broadcasts, particularly in dynamic environments where users might be temporarily suspended.
  • Optimal Reset Timing: The authors derived a closed-form inequality to estimate $T_{th}$. As shown in Figure 4, the optimal time to reset the system is inversely proportional to the number of revoked users and the rate of incoming signature packets ($\lambda_s$). For instance, with high signature traffic, the system should ideally re-distribute keys every 1–2 hours to maintain peak efficiency.
  • Un-linkability: The scheme ensures that revocation tokens ($grt$) change across time slots, preventing observers from linking a revoked user's past signatures to their current identity.

Conclusion

Delta-RL provides a mathematically grounded approach to managing user revocation in anonymous PKI systems. By identifying the "tipping point" where list-based verification becomes inefficient compared to re-keying, the system maintains high performance without sacrificing privacy. Future work may address more complex network topologies and the application of these principles to post-quantum group signature schemes.

Summary updated

BibTeX
@inproceedings{ren2008efficient,
  author = {Wei Ren and Kui Ren and Wenjing Lou and Yanchao Zhang},
  title = {{Efficient user revocation for privacy-aware PKI}},
  booktitle = {QSHINE},
  year = {2008},
  doi = {10.4108/icst.qshine2008.3824},
}
Figure