Abstract: Hu, Huang and Fan proposed a fully secure hierarchical identity-based encryption (IEICE Trans. Fundamentals, Vol.E92-A, No.6, pp.1494-1499, 2009) that achieves constant size of ciphertext and tight security reduction. Unfortunately, Park and Lee (IEICE Trans. Fundamentals, Vol.E93-A, No.6, pp.1269-1272, 2010) found that the security proof of Hu et al.'s scheme is incorrect; that is, the security of Hu et al.'s scheme cannot be reduced to their claimed q-ABDHE assumption. However, it is unclear whether Hu et al.'s scheme is still secure. In this letter, we provide an attack to show that the scheme is not secure against the chosen-plaintext attack.
Introduction
Identity-Based Encryption (IBE) represents a significant shift in public-key cryptography by allowing a user's unique identity—such as an email address—to serve as their public key. This eliminates the administrative burden of managing digital certificates. Hierarchical IBE (HIBE) further refines this by allowing a root Private Key Generator (PKG) to delegate key-issuing authority to lower-level nodes in an organizational hierarchy.
In 2009, Hu, Huang, and Fan proposed a HIBE scheme that gained attention for its efficiency, specifically offering "constant-size" ciphertexts regardless of the hierarchy's depth. However, the cryptographic community's confidence in the scheme was shaken in 2010 when Park and Lee demonstrated that the original security proof was logically flawed. This left an open question: was the scheme fundamentally broken, or was the proof simply inadequate? This paper provides the definitive answer by presenting a concrete mathematical attack.
The Problem: Proof vs. Security
In modern cryptography, a "gap" in a security proof is a serious concern. While it doesn't always mean a scheme is exploitable, it often points to structural weaknesses. The Hu et al. scheme claimed security based on the q-ABDHE (q-Augmented Bilinear Diffie-Hellman Exponent) assumption. Once Park and Lee proved the reduction to this assumption was invalid, the scheme's security status became "unproven." This research moves beyond theoretical proof-checking to demonstrate a practical vulnerability to Chosen-Plaintext Attacks (CPA).
Methodology: The Key Extraction Attack
The authors utilize a "key extraction attack," which targets the algebraic relationship between identities and their corresponding private keys. The attack does not require breaking the underlying hard mathematical problems (like bilinear pairings) but rather exploits the linear way the scheme handles identity strings.
The Attack Mechanism
The attack follows a structured algebraic reconstruction process:
- Target Identification: The adversary selects a target identity ($ID^*$) they wish to compromise.
- Strategic Identity Selection: The adversary identifies three related identities ($ID_0, ID_1, ID_2$) at the same level of the hierarchy.
- Linear Relationship: These identities are chosen specifically to satisfy a linear equation: $ID_2 = ID_0 + ID_1 - ID^*$.
- Key Acquisition: The adversary queries the system for the private keys of the three "dummy" identities ($ID_0, ID_1, ID_2$).
- Algebraic Reconstruction: By performing a series of multiplications and divisions on the components of these three known keys, the adversary can cancel out the "blinding" factors used by the PKG. This allows them to isolate and reconstruct the valid private key for the target $ID^*$.
Key Insights
The Vulnerability of Linearity
The core failure of the Hu et al. scheme is the linear nature of its private key generation. In a secure HIBE, the mapping between an identity and a key should be sufficiently non-linear or randomized so that knowing multiple keys provides no information about others. In this scheme, the identity-dependent part of the key is essentially an additive component. This allows an attacker to use the homomorphic properties of the underlying mathematical groups to "solve" for an unknown key using known ones.
Zero-Query Phase 1
Notably, the attack is highly efficient. The adversary does not need to make any queries during the initial phase of the security game. They can wait to see a challenge ciphertext and then strategically choose which identities to query to facilitate the break.
Results and Impact
The analysis concludes with two primary findings:
- Total Break of Security: The authors demonstrate that an adversary can derive a valid private key for any target identity with 100% probability.
- CPA Insecurity: The scheme is formally classified as not IND-CPA secure. In cryptographic terms, failing a Chosen-Plaintext Attack is a critical failure; if a scheme cannot protect against an attacker who chooses the messages to be encrypted, it is considered fundamentally broken for practical use.
Conclusion
This work settles the uncertainty surrounding the Hu et al. HIBE scheme. It serves as a cautionary example of how structural linearity in key generation can lead to total system collapse, even if the underlying mathematical problems remain hard. While the scheme's constant-size ciphertext was an attractive feature, its lack of security makes it unsuitable for deployment. Future HIBE designs must prioritize non-linear identity-to-key mappings to avoid similar algebraic reconstruction attacks.
Summary updated