Subscribe Now Subscribe Today
Abstract
Fulltext PDF
References
Research Article
 

On Delegating Private Key Derivation in Hierarchical Identity Based Encryption and Related Encryption Privacy



Jian-Wu Zheng, Jing Zhao and Xin-Ping Guan
 
ABSTRACT

As of Hierarchical Identity Based Encryption (HIBE) systems, there are two important tasks should be accomplished properly, the first one is to establish logically hierarchical relationship between entities in the hierarchy tree, which is essentially accomplished through private key derivation by delegating responsibilities to lower-level PKGs and the other task is to achieve encryption privacy of ciphertext targeting an intended recipient. In this study, mechanisms of private key derivation in HIBE systems are classified, which explicitly define how and to what extent an entity in the hierarchy takes its level PKGs role of generating valid private keys for its descendants in the hierarchy. Moreover, a new delegation mechanism, authorized delegation is introduced, which can prevent any entity from deriving private keys for its descendants with use of its private key and delegate the responsibility of generating private keys for a specified entity through authorization by distributing a specific secret to an entity as an ancestor of the specified entity by the root PKG (primitive authorization) or some other authorized entities (chained authorization). As for encryption privacy of ciphertext in a HIBE system, which measures the possibility that ciphertexts targeting an entity are successfully decrypted by its ancestors or descendants, the encryption privacy is studied from two distinct perspectives, i.e., private key derivation perspective and private key legitimacy perspective. Furthermore, dominated encryption privacy and dedicated encryption privacy are defined and discussed from private key legitimacy perspective.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Jian-Wu Zheng, Jing Zhao and Xin-Ping Guan, 2016. On Delegating Private Key Derivation in Hierarchical Identity Based Encryption and Related Encryption Privacy. Journal of Software Engineering, 10: 279-284.

DOI: 10.3923/jse.2016.279.284

URL: https://scialert.net/abstract/?doi=jse.2016.279.284
 
Received: March 14, 2016; Accepted: April 30, 2016; Published: June 15, 2016

INTRODUCTION

An Identity Based Encryption (IBE) system is a public key system that an entity’s public key can be any identifier of the entity (arbitrary string that is public and can identify the entity) and private key for the entity can be calculated from its identifier with use of a master key by an authority called Private Key Generator (PKG). Since the introduction of the concept of Identity Based Encryption (IBE) by Shamir (1985), there are no usable IBE constructions until the studies by Boneh and Franklin (2001), Cocks (2001) and Sakai and Kasahara (2000). The concept of Hierarchical Identity Based Encryption (HIBE) was first introduced by Horwitz and Lynn (2002). Gentry and Silverberg (2002), Canetti et al. (2003), Boneh and Boyen (2004a), Gentry (2006) and Waters (2005, 2009) constructed their schemes under the Decisional Bilinear Diffie-Hellman assumption (or variants of BDH assumption) and proved the security of their systems in standard model. Studies by Gentry (2006), Waters (2005, 2009) and Boneh et al. (2005) provided some fully secure schemes without random oracles.

Conventionally, it is taken for granted that in a HIBE system entities in the hierarchy have the power of generating valid private keys for their descendants; specifically, an entity can not only directly use its own private key and some public parameters to derive valid private keys along the hierarchy tree (usually derivation is accomplished by randomizing an ancestor’s private key), but also unrestrictedly generate valid private keys for all descendants of the entity if the entity wants to. Boneh et al. (2005) presented a HIBE scheme that is selective identity secure in standard model and fully secure in the random oracle model; notably, the scheme can achieve limited delegation and short ciphertexts regardless of the hierarchy depth.

Although, key escrow problem is inherent in IBE public cryptography, resulting from the mechanism of generating private keys for entities in the system, but it should not be exaggerated in HIBE systems, where lower level PKGs are unrestrictedly delegated to be capable of generating private keys for their descendants. Particularly, it is irrational and undesirable that a lower level PKG (as an ancestor) can generate valid private keys for a descendant with direct use of its private key and a lower level PKG can generate private keys for all of its descendants.

In order to preventing entities from deriving private keys for their descendants with direct use of their private keys, while providing a means for entities to be capable of deriving private keys for some of their descendants. A new technique for composing private keys for entities in HIBE hierarchy is proposed, that it was called differenting technique. When generating a private key for an identity, the local identifier Ij is used to differentiate all those non-local identifiers Ii,.... Ij-1, which maps the true identity Ij to a newly constructed identity (not necessary a true identity in the hierarchy). Most importantly, those ancestor entities of IDj are not prefixes of the newly constructed identity, thus preventing the direct private key derivation and guaranteeing the related encryption privacy. Moreover, privilege of generating private keys for an entity can be delegated by the root PKG to any ancestor of the entity through authorization by distributing an authorized credential to the ancestor with respect to the differentiating technique. That it was called authorized delegation.

MATERIALS AND METHODS

Different from the one-PKG characterized IBE, Hierarchical Identity Based Encryption (HIBE) accommodates level-oriented PKG configuration. Namely, the top level PKG is the root PKG (at level zero), who maintains a hierarchy tree of which non-leaf nodes are viewed as level PKGs. The HIBE allows the root PKG to balance the workload by delegating identity authentication, private key generation and private key distribution to lower level PKGs. Usually, delegation of private key generation for entities in the hierarchy is main job of responsibility delegation (from root PKG to lower level PKGs). The mechanisms of delegating private key generation can be classified into three classes, i.e., unlimited delegation, limited delegation and a new delegation firstly propsed in this study, authorized delegation with reference to criteria listed below. For ease of presentation, it is assumed that Entityi with identity IDi = (I1,..., Ii) is an ancestor of Entityj with identity IDi = (I1,..., Ij) that is IDi is a prefix of IDj such that IDi [k] = IDj [k] for all kε{1,...,i}.

Only an entity’s private key or some specially crafted content other than private key should be utilize to generate private keys for the entity’s descendants, besides some public parameters, such as system parameters, identities (public keys) of the descendants whose private keys are derived and so on
Whether the private key generation can be hierarchically derived along the identity hierarchy tree; specifically, whether private key for Entityj+1 can be derived given a private key for Entityj is generated
Whether Entityj should first generate private keys for all entities, which are descendants of Entityi and ancestors of Entityj prior to deriving a private key for Entityj

Unlimited delegation: Unlimited delegation indicates that an entity dominates all of its descendants. Unlimited delegation means that an entity in the hierarchy can directly and unrestrictedly derive private keys for its descendants. Directly here means an entity can derive private keys for its descendant’s with only use of its private key, or the private key for the entity is the only needed secret for generating the descendant’s private keys. Unrestrictedly means that the private key derivation can be accomplished hierarchically by an entity for all of its descendants.

As of private key derivation in Boneh and Boyen (2004b, 2011) an Entityj’s private key denoted dIDj can be hierarchically randomized to generate private keys for all of its descendants level by level. How Entityj can derive a private key for its child entity Entityj+1 with use of its private key dIDj, public system parameters, identity of the child and some random values is exemplified below.

Both private keys for Entityj and Entityj+1 with identities of depth j≤l-1 and , denoted and , respectively can be extracted as:


Let Δd0 be the result of dIDj+1 [0], Δd0 is calculated as:

Correspondingly, other components can as well be calculated as and Let denote the private key for Entityj (i.e., dIDj) and r1,..., rj+1 be j+1 random numbers from zq, the private key forEntitytj can be derived as (other than extracting by extract (mk, IDj+1)):

By repeating the derivation process above, the private key of Entityj+1 can be derived by any of its ancestors along the hierarchy. Consequently not only ciphertexts intended for an entity can be decrypted by any of its ancestors, but also the ancestor, being with knowledge of a private key of the descendant can do anything that the entity can do.

Limited delegation: Unlike unlimited delegation, limited delegation restricts the depth within which the descendant’s private keys can be derived. Limited delegation means that an entity at depth k with public identity IDk, denoted Entityk is given a restricted private key witht t instead of l-k (t<l-k, where l is the maximum hierarchy depth) extra secrets that only authorizes the ancestor (i.e., Entityk) to be able to derive private keys for its descendants of limited depth, beginning from Entityk’s child to its descendant at depth k+t (the deepest depth). If all l-k extra secrets are provided, then the entity at depth k can generate private keys for all of its descendant. Particularly, the HIBE system fails to only generate valid private keys for a descendant at a specified depth ξ for k+2≤ξ≤l without deriving private keys for descendants at depth k+1,..., ξ.

The HIBE system presented by Boneh et al. (2005) considers "Limited delegation" and related encryption privacy of preventing an ancestor from successfully decrypting ciphertexts targeting its descendants. Private keys for Entityj and Entityj+1 with identities and IDj+1 = (IDj, Ij+1), respectively are extracted by the root PKG as:

where, r(IDj) and r(IDj+1) are two random numbers picked from Zq by the root PKG. For clarity of representation, dIDj is denoted as By picking a random number r from Zq, a private key for Entityj+1 is derived with use of dIDj as:

By repeating the process above, private keys for all descendants of Entityj can be derived with use of the Entityj’s private key and needed historical content. Different from private key derivation in BB1 system, where private keys for a child can be derived by only randomizing its parent’s private keys, this HIBE system however, does need some extra historical content in deriving a private key for a child, in addition to randomizing the parent’s private key. For example, in deriving a private key for Entityj+1with use of Entityj’s private key, as an important historical argument is needed for calculating as one important share of the resulted private key for Entityj+1, as well as randomizing Entityj’s private key to get the other share of the private key for Entityj+1.

Then, if the root PKG does not provide l-j components when distributing a private key for Entityj, where is still a valid private key for Entityj from perspective of cryptographic operation without considering private key derivation, there is no means of generating valid private keys for any descendant of Entutyj with using Entutyj’s private key because of lack of the needed historical argument

Actually, only the component instead of all those l-j components is not provided, it is impossible to derive a private key for Entityj+1 with use of Entityj private key and thus disabling the hierarchical private key derivation along the hierarchy tree. That is, by providing a restricted private key with onlyt components for k = 1,...,t to Entityj can be capable of only generating private keys for its descendants of bounded depth t, i.e. from descendant at depth j+1 to descendant at depth j+1 along hierarchy tree.

Authorized delegation: Limited delegation does prevent private keys for those descendants at depth beyond the limited depth from being derived. Nevertheless, there is no means to only derive a private key for Entityj+t with use of Entityj’s private key without revealing private keys for those entities, which are at level between j+1 and j+t-1. This undesirable breach in privacy is resulted from the need of use of a parent’s private key when deriving a child’s private key.

Authorized delegation means that private keys for an entity cannot be derived directly from its ancestor’s private keys. However, by distributing a secret specifically crafted for an entity to its ancestor by the root PKG, the ancestor is thus authorized to generate private keys for the specific descendant, while failing to generate private keys for any entity other than the specified descendant.

In the sequel a new technique: Differentiating technique is proposed, which can be applied to construct a HIBE system with authorized delegation of generating private keys for entities (always descendants of the generator). Particularly, what should be accomplished for achieving authorized delegation is as follows:

Planning private key composition, such as including share of randomizing the master secret and some components that make direct and unrestricted delegation of generating private keys for descendants impossible. Contrasted to private key derivation in (Gentry and Silverberg, 2002; Boneh and Boyen, 2004a, 2011), where both Sj and dIDj can be hierarchically randomized to generate private keys for IDj+1 = (Idj, Ij+1) IDj+2,... and so on
Providing means for an entity, such as through authorization to be capable of generating private keys for a specified descendant entity. Authorization here can be achieved through secret distribution by equipping the generator with specially crafted content for deriving private keys for the specified entity, somewhat analogous to HIBE system presented by Boneh et al. (2005), where by equipping Entityj with needed secrets for deriving a private key for Entityj’s descendant at depth j+1

The main idea of this solution differentiating technique is to differentiate between identifiers I1,..., Ij of the identity IDj when extracting a private key for Entityj. Specifically, in addition to randomizing the master secret of the root PKG with each identifier of {I1,...,Ij} independently and uniformly for extracting a private key for Entityj, which is the only mechanism of private key extraction presented in Boneh and Boyen (2011) an extra share ξ resulted from the combination of Entityj’s local identifier Ij and those random values picked correspondingly for identifiers I1,...,Ij-1 is introduced into the Entityj’s private key. The extra share ξ anchors the generated private key only to the identity IDj = (I1,..., Ij). Anchor here means that the private key generated for Entityj can neither be used to derive private keys for its descendants, nor to decrypt ciphertexts intended for its ancestors or descendants. Namely, it is infeasible for an entity to derive private keys for its descendants with its private key, because there is no means for the Entityj to wipe off the share defined on its local identifier Ij from its private key and to introduce needed share related to the local identifier of each of its descendants for private key derivation in order to generate the corresponding descendant’s private key.

Moreover, this HIBE system does provide a mechanism for authorized private key derivation, i.e., deriving a valid private key for and only for a specified descendant. Assume that Entityi as an ancestor of Entityj is authorized to derive private keys for Entityj (the specified entity). Entityj can be authorized by distributing to it two copies of information, the first information is the result of randomizing the master secret along the identity hierarchy I1→...→Ii and the other copy is the result of combination of local identifier Ij of Entityj (not Entityi) with those random numbers picked for identifiers I1,..., Ii in randomizing the master secret. Then with these two copies of information Entityj can further hierarchically randomized these two copies with identical random number series along the identity hierarchies Ii+1→...→Ij and Ij→...→Ij, respectively and at last add these two copies of information. The summation is a private key for Entityj. It is worth noting that two copies of information during the derivation process, i.e., along the identity hierarchy Ij+1→...→Ij-1, neither can be used to derive private keys for entities other than Entityj, nor can be added to get a private key for any ancestor of Entityj.

RESULTS AND DISCUSSION

Unlike public key cryptography implemented in Public Key Infrastructure (PKI), where an entity’s public and private key pair can be selected by either the trusted authority or the entity itself, private keys for an entity in HIBE system can only be generated by the root PKG or some domain (lower-level) PKGs. That is key escrow problem is inherent in (H) IBE public cryptography and ciphertexts for an entity can be decrypted by those entities that are capable of generating valid private keys for the entity. As a result, there is no encryption privacy of ciphertexts targeting entities for which private keys can be derived by their ancestor entities from the ancestor’s point of view.

With the technique detailed in section above, unlimited delegation is disabled with the differentiating technique and any entity needs to be authorized by the root PKG for being able to generate private keys for any of its descendants. Moreover, other than from private key derivation perspective, it is necessary to consider encryption privacy from private key legitimacy perspective, i.e., whether an entity’s private key is legitimate for ciphertexts encrypted on identity of the entity’s descendants.

Dominated encryption privacy: Means that ciphertexts targeting an entity can be decrypted by all or some of its ancestors without burden of generating a private key for the entity but with direct use of these ancestor’s private keys. As for HIBE scheme in Gentry and Silverberg (2002) and BB1 scheme in Boneh and Boyen (2004b, 2011) it is not necessary that any ancestor of Entityj should derive a private key for Entityj in order to decrypt ciphertexts intended for Entityj. When encrypting a given message M∈Gt intended for Entityj with identitythe encryptor picks a random value and outputs the ciphertext as:

Let Entityj with identity IDk = (I1,..., Ik) be an ancestor of Entityj, the private key for Entityk denoted is extracted as:

Entityk can decrypt ciphertext C denoted , intended for Entityj, as:

That is any ancestor of an entity can decrypt ciphertexts encrypted on the public key (i.e. identity) of the entity with only use of its own private key without need of deriving a valid private key for the entity.

Dedicated encryption privacy: Means that all entities other than the intended recipient of a ciphertext cannot decrypt the ciphertext, thus achieving encryption privacy of ciphertext dedicated only to the intended recipient. As for encryption privacy of HIBE system presented by Boneh et al. (2005), assume that Entityj is an ancestor of Entityj (without respect to whether Entityj is capable of deriving private keys for Entityj or not) and an encryptor encrypts a given messageMεG1 on Entityj’s identity IDj = (I1,..., Ij) as:

then Entityj can decrypt the ciphertext with its private key as:

For a successful decryption, it is required that is congruent to zero with modulus prime q, where αk for k = 1,...,l are logarithms of is calculated as:

where, is multiplicative inverse of Ij in Zq. Because α1,... and αl are all uniformly and independently selected from Zq, then the probability of event that αj is of value is 1/q, which means the probability of success of decrypting a ciphertext intended for Entityj by Entityi as an ancestor equals the probability that a specific value modq∈Zq is selected as qεZq. Similarly, if αj is a descendant of Entityj, it is required that is congruent to zero with modulus prime q for a successful description.

CONCLUSION

The mechanism of delegating private key generation is crucial in establishing logically hierarchical relationship between entities along hierarchy tree in HIBE systems, which should reflect the true institutional structures in real world. The delegation mechanisms are classified into three classes, with reference to how an entity’s private key can be generated by lower-level PKGs other than the root PKG. Moreover, differentiating technique for achieving authorized delegation is proposed, which hierarchically derive secrets along identity hierarchies I1→...→Ij and Ij→...→Ij, i.e. by randomizing the master secret of the root PKG along the former and privacy specifically pertained to local identifier Ij (dedicated privacy) along the later and at last get a private key for Entityj. Contrasted to direct and unrestricted private key derivation in unlimited delegation HIBE systems and restricted private key derivation of limited depth in limited delegation HIBE systems, authorized delegation can explicitly authorize some entity to generate valid private keys for some specified entity of which ancestor’s private keys are not needed or generated at all.

At last, two types of encryption privacy, i.e., dominated encryption privacy and dedicated encryption privacy are discussed and compared from private key legitimacy perspective. It is unquestionably necessary to achieve dedicated encryption privacy when constructing a HIBE system.

REFERENCES
Boneh, D. and M.K. Franklin, 2001. Identity-based Encryption from the Weil Pairing. In: Advances in Cryptology, Kilian, J. (Ed.). Springer, Berlin, Heidelberg, ISBN: 978-3-540-42456-7, pp: 213-229.

Boneh, D. and X. Boyen, 2004. Efficient Selective-ID Secure Identity-Based Encryption without Random Oracles. In: Advances in Cryptology, Cachin, C. and J.L. Camenisch (Eds.). Springer, Berlin, Heidelberg, ISBN: 978-3-540-21935-4, pp: 223-238.

Boneh, D. and X. Boyen, 2004. Secure Identity based Encryption without Random Oracles. In: Advances in Cryptology, Franklin, M. (Ed.). Springer, Berlin, Heidelberg, ISBN: 978-3-540-22668-0, pp: 443-459.

Boneh, D. and X. Boyen, 2011. Efficient selective identity-based encryption without random oracles. J. Cryptol., 24: 659-693.
CrossRef  |  Direct Link  |  

Boneh, D., X. Boyen and E.J. Goh, 2005. Hierarchical Identity based Encryption with Constant Size Ciphertext. In: Advances in Cryptology, Cramer, R. (Ed.). Springer, Berlin, Heidelberg, ISBN: 978-3-540-25910-7, pp: 440-456.

Canetti, R., S. Halevi and J. Katz, 2003. A Forward-Secure Public-Key Encryption Scheme. In: Advances in Cryptology, Biham, E. (Ed.). Springer, Berlin, Heidelberg, ISBN: 978-3-540-14039-9, pp: 255-271.

Cocks, C., 2001. An Identity based Encryption Scheme based on Quadratic Residues. In: Cryptography and Coding, Honary, B. (Ed.). Springer, Berlin, Heidelberg, ISBN: 978-3-540-43026-1, pp: 360-363.

Gentry, C. and A. Silverberg, 2002. Hierarchical ID-based Cryptography. In: Advances in Cryptology, Yuliang, Z. (Ed.). Springer, Berlin, Heidelberg, ISBN: 978-3-540-00171-3, pp: 548-566.

Gentry, C., 2006. Practical Identity-based Encryption without Random Oracles. In: Advances in Cryptology, Vaudenay, S. (Ed.). Springer, Berlin, Heidelberg, ISBN: 978-3-540-34546-6, pp: 445-464.

Horwitz, J. and B. Lynn, 2002. Toward Hierarchical Identity-based Encryption. In: Advances in Cryptology, Knudsen, L. (Ed.). Springer, Berlin, Heidelberg, ISBN: 978-3-540-43553-2, pp: 466-481.

Sakai, R. and M. Kasahara, 2000. Cryptosystems based on pairings. Proceedings of the Symposium on Cryptography and Information Security, January 26-28, 2000, Okinawa, Japan -.

Shamir, A., 1985. Identity-Based Cryptosystems and Signature Schemes. In: Advances in Cryptology, Blakley, G. and D. Chaum (Eds.). Springer, Berlin, Heidelberg, ISBN: 978-3-540-15658-1, pp: 47-53.

Waters, B., 2005. Efficient Identity-based Encryption without Random Oracles. In: Advances in Cryptology, Cramer, R. (Ed.). Springer, Berlin, Heidelberg, ISBN: 978-3-540-25910-7, pp: 114-127.

Waters, B., 2009. Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions. In: Advances in Cryptology, Halevi, S. (Ed.). Springer, Berlin, Heidelberg, ISBN: 978-3-642-03355-1, pp: 619-636.

©  2019 Science Alert. All Rights Reserved
Fulltext PDF References Abstract