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:
- 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.
- 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.
- 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:
- 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