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

TL;DR

This paper introduces SAKI, a novel protocol for Identity-Based Encryption (IBE) that allows users to obtain private keys anonymously and securely without requiring a pre-existing secure channel. By leveraging short blind signatures and separating the duties of identity authentication from key generation, the system protects user privacy and eliminates the "chicken-and-egg" problem of establishing secure communication with a Key Generation Center (KGC).

What Problem Does This Paper Address?

Identity-Based (ID-based) cryptosystems are attractive because they allow a user's public key to be a simple string, like an email address, eliminating the need for complex digital certificates. However, they face three major hurdles:

  1. The Secure Channel Requirement: Traditionally, when a KGC generates a private key for a user, it must send that key over a secure channel. Setting up this channel is difficult because the user doesn't have their private key yet—a classic "chicken-and-egg" problem.
  2. Lack of Anonymity: In standard systems, the KGC knows exactly which identity is requesting a key. For privacy-oriented applications (like anonymous ring signatures), this knowledge is a significant privacy leak.
  3. Monolithic Authorities: Often, the same entity is responsible for both verifying a user's physical identity and performing the cryptographic computation. This creates a single point of failure and a massive trust bottleneck.

Methods

The authors propose the SAKI (Separable and Anonymous ID-based Key Issuing) scheme. The core technical innovation is the adaptation of Short Blind Signatures based on Bilinear Pairings in Gap Diffie-Hellman (GDH) groups.

Key components include:

  • Separation of Duties: The protocol splits the process between a Local Registration Authority (LRA), which handles the "real-world" authentication of the user, and the KGC, which performs the cryptographic heavy lifting.
  • Blinding Technique: Inspired by the work of Boneh et al. and Boldyreva, the user "blinds" their identity and a one-time password before sending them to the KGC.
  • The Protocol Flow:
    1. The user authenticates offline with an LRA and receives a one-time password.
  • The user sends a "blinded" request to the KGC.
  • The KGC verifies the request against a database of pending keys (provided by the LRA) without learning the user's actual identity.
  • The KGC computes a blinded private key and sends it back over a public channel.
  • The user "unblinds" the response to retrieve their actual private key.

Datasets

Not discussed in the paper. As a theoretical cryptography paper, the authors focus on mathematical proofs and algorithmic complexity rather than empirical testing on specific datasets.

Key Insights and Ideas

  • Privacy through Blindness: By using blind signatures, the KGC can issue a valid private key without ever knowing which specific identity (e.g., which email address) it is serving.
  • Public Channel Security: Because the key is sent in a blinded form, it is effectively encrypted. Only the legitimate requester who knows the blinding factor can retrieve the final key, making a dedicated secure channel unnecessary.
  • Solving Key Escrow: The authors provide an extension to support multiple KGCs. By splitting the master key among several authorities, they ensure that no single KGC can impersonate a user or decrypt their messages, solving the "key escrow" problem inherent in many ID-based systems.

Key Results

  • Efficiency: The scheme is computationally lean. On the user side, it requires only 2 scalar multiplications, 2 modular inversions, and 2 pairing computations. The KGC side requires just 1 pairing and 1 scalar multiplication.
  • Provable Security: The authors prove that the underlying Short Blind Signature (SBS) is secure against "one-more-forgery" attacks under the chosen-target Computational Diffie-Hellman (CDH) assumption.
  • Anonymity: The protocol successfully prevents the KGC from linking a key request to a specific user identity, provided the LRA and KGC do not collude.

Limitations and Future Work

  • Password Formatting: The authors note that the KGCs "blindly sign" a password chosen by the user. To prevent certain attacks, they suggest that the password must follow specific formatting or padding (e.g., prefixing it with "PASSWORD: ").
  • LRA-KGC Collusion: While the system separates duties, if the LRA and KGC collude, the anonymity of the user could be compromised.
  • Integration with Newer Schemes: The authors mention that while newer, more efficient short signature schemes exist, integrating them into the SAKI framework remains an open problem for future research.

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},
}

Loading related content...

Figure