Separable and Anonymous Identity-Based Key Issuing

Ai Fen Sui, Sherman S. M. Chow, Lucas Chi Kwong Hui, Siu-Ming Yiu, Kam-Pui Chow, Wai Wan Tsang, C. F. Chong, Kevin K. H. Pun, H. W. Chan

Introduction

Identity-Based Encryption (IBE) represents a significant shift in public-key cryptography by allowing a user’s public key to be derived from a simple, unique string—such as an email address or a phone number. This eliminates the need for the complex digital certificates and Public Key Infrastructure (PKI) required by traditional systems. However, despite their theoretical appeal, practical IBE deployments have been hindered by three critical issues: the requirement for a secure channel to deliver private keys, the lack of user anonymity during key issuance, and the concentration of power within a single Key Generation Center (KGC).

This paper introduces SAKI (Separable and Anonymous ID-based Key Issuing), a novel protocol designed to address these bottlenecks. By leveraging short blind signatures and a decentralized architecture, SAKI enables users to obtain their private keys securely over public channels while maintaining their anonymity from the central authority.

The Problem: The "Chicken-and-Egg" of Key Issuance

Standard IBE systems face a fundamental paradox. When a KGC generates a private key for a user, it must transmit that key securely. However, the user typically requires a private key to establish a secure, encrypted channel in the first place. This "chicken-and-egg" problem often forces organizations to rely on out-of-band delivery or pre-existing secure infrastructures, which limits scalability.

Furthermore, in traditional IBE, the KGC is a monolithic entity that knows exactly which identity is requesting which key. For privacy-sensitive applications, such as anonymous voting or ring signatures, this knowledge constitutes a significant privacy leak. Finally, the KGC often acts as both the identity verifier and the cryptographic generator, creating a single point of failure and a massive trust bottleneck.

The SAKI Protocol Architecture

The core innovation of SAKI is the separation of duties and the application of Short Blind Signatures based on Bilinear Pairings in Gap Diffie-Hellman (GDH) groups. The protocol splits the key issuance process between two distinct entities:

  1. Local Registration Authority (LRA): Responsible for the physical or "real-world" authentication of the user. The LRA verifies the user's identity and provides them with a one-time password (OTP).
  2. Key Generation Center (KGC): Responsible for the cryptographic computation of the private key. Crucially, the KGC does not interact with the user's real-world identity directly.

The Protocol Flow

The SAKI workflow follows a multi-step process designed to preserve privacy:

  • Authentication: The user authenticates offline with the LRA and receives an OTP.
  • Blinding: The user "blinds" their identity and the OTP using a random factor. This ensures that the KGC cannot see the underlying data.
  • Request: The user sends this blinded request to the KGC over a public channel.
  • Issuance: The KGC verifies the request against a database of pending keys provided by the LRA. It then computes a blinded private key and returns it to the user.
  • Unblinding: The user applies their secret blinding factor to the KGC's response to retrieve their actual private key.

Key Insights and Security Analysis

Privacy through Blindness

By utilizing blind signatures, SAKI ensures that the KGC can issue a valid private key without ever learning the specific identity (e.g., the email address) it is serving. This decoupling of identity from key generation is essential for maintaining user anonymity.

Security over Public Channels

Because the key is transmitted in a blinded form, it is effectively encrypted during transit. Only the legitimate requester, who possesses the unique blinding factor, can successfully unblind the response to retrieve the final private key. This removes the necessity for a pre-established secure channel.

Solving the Key Escrow Problem

The authors also propose an extension to support multiple KGCs. By distributing the master key among several authorities, the system ensures that no single KGC can impersonate a user or decrypt their messages, effectively mitigating the "key escrow" problem inherent in many centralized IBE schemes.

Performance and Results

SAKI is designed to be computationally efficient, making it suitable for resource-constrained environments. The performance metrics are as follows:

  • User Side: Requires 2 scalar multiplications, 2 modular inversions, and 2 pairing computations.
  • KGC Side: Requires 1 pairing and 1 scalar multiplication.

The protocol is provably secure against "one-more-forgery" attacks under the chosen-target Computational Diffie-Hellman (CDH) assumption. This ensures that even if an adversary observes multiple key issuances, they cannot generate a new valid key for an unauthorized identity.

Limitations and Future Directions

While SAKI offers a robust solution for anonymous key issuing, it is not without limitations. The authors note that the protocol relies on the assumption that the LRA and KGC do not collude; if they were to share data, the user's anonymity could be compromised. Additionally, the security of the blind signature requires specific formatting or padding of the user's password to prevent certain algebraic attacks.

Future research may involve integrating SAKI with more recent, even more efficient short signature schemes to further reduce the computational overhead for mobile and IoT devices.

Summary updated

BibTeX
@inproceedings{sui2005separable,
  author = {Ai Fen Sui and Sherman S. M. Chow and Lucas Chi Kwong Hui and Siu-Ming Yiu and Kam-Pui Chow and Wai Wan Tsang and C. F. Chong and Kevin K. H. Pun and H. W. Chan},
  title = {{Separable and Anonymous Identity-Based Key Issuing}},
  booktitle = {ICPADS},
  year = {2005},
  doi = {10.1109/icpads.2005.263},
}
Figure