Journal of Software Engineering

Year: 2016 | Volume: 10 | Issue: 3 | Page No.: 279-284
DOI: 10.3923/jse.2016.279.284

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.

Keywords: Identity-based encryption, HIBE, private key derivation, authorized delegation and encryption privacy

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 I_j is used to differentiate all those non-local identifiers I_i,.... I_j-1, which maps the true identity I_j to a newly constructed identity (not necessary a true identity in the hierarchy). Most importantly, those ancestor entities of ID_j 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 Entity_i with identity ID_i = (I₁,..., I_i) is an ancestor of Entity_j with identity ID_i = (I₁,..., I_j) that is ID_i is a prefix of ID_j such that ID_i [k] = ID_j [k] for all kε{1,...,i}.

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 Entity_j’s private key denoted dID_j can be hierarchically randomized to generate private keys for all of its descendants level by level. How Entity_j can derive a private key for its child entity Entity_j+1 with use of its private key dID_j, public system parameters, identity of the child and some random values is exemplified below.

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

Let Δd₀ be the result of dID_j+1 [0], Δd₀ is calculated as:

Correspondingly, other components can as well be calculated as and Let denote the private key for Entity_j (i.e., dID_j) and r₁,..., r_j+1 be j+1 random numbers from z_q, the private key forEntityt_j can be derived as (other than extracting by extract (mk, ID_j+1)):

By repeating the derivation process above, the private key of Entity_j+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 ID_k, denoted Entity_k 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., Entity_k) to be able to derive private keys for its descendants of limited depth, beginning from Entity_k’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 Entity_j and Entity_j+1 with identities and ID_j+1 = (ID_j, I_j+1), respectively are extracted by the root PKG as:

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

By repeating the process above, private keys for all descendants of Entity_j can be derived with use of the Entity_j’s private key and needed historical content. Different from private key derivation in BB₁ 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 Entity_j+1with use of Entity_j’s private key, as an important historical argument is needed for calculating as one important share of the resulted private key for Entity_j+1, as well as randomizing Entity_j’s private key to get the other share of the private key for Entity_j+1.

Then, if the root PKG does not provide l-j components when distributing a private key for Entity_j, where is still a valid private key for Entity_j from perspective of cryptographic operation without considering private key derivation, there is no means of generating valid private keys for any descendant of Entuty_j with using Entuty_j’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 Entity_j+1 with use of Entity_j 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 Entity_j 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 Entity_j+t with use of Entity_j’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:

The main idea of this solution differentiating technique is to differentiate between identifiers I₁,..., I_j of the identity ID_j when extracting a private key for Entity_j. Specifically, in addition to randomizing the master secret of the root PKG with each identifier of {I₁,...,I_j} independently and uniformly for extracting a private key for Entity_j, which is the only mechanism of private key extraction presented in Boneh and Boyen (2011) an extra share ξ resulted from the combination of Entity_j’s local identifier I_j and those random values picked correspondingly for identifiers I₁,...,I_j-1 is introduced into the Entity_j’s private key. The extra share ξ anchors the generated private key only to the identity ID_j = (I₁,..., I_j). Anchor here means that the private key generated for Entity_j 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 Entity_j to wipe off the share defined on its local identifier I_j 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 Entity_i as an ancestor of Entity_j is authorized to derive private keys for Entity_j (the specified entity). Entity_j 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 I₁→...→I_i and the other copy is the result of combination of local identifier I_j of Entity_j (not Entity_i) with those random numbers picked for identifiers I₁,..., I_i in randomizing the master secret. Then with these two copies of information Entity_j can further hierarchically randomized these two copies with identical random number series along the identity hierarchies I_i+1→...→I_j and I_j→...→I_j, respectively and at last add these two copies of information. The summation is a private key for Entity_j. It is worth noting that two copies of information during the derivation process, i.e., along the identity hierarchy I_j+1→...→I_j-1, neither can be used to derive private keys for entities other than Entity_j, nor can be added to get a private key for any ancestor of Entity_j.

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 Entity_j should derive a private key for Entity_j in order to decrypt ciphertexts intended for Entity_j. When encrypting a given message M∈G_t intended for Entity_j with identitythe encryptor picks a random value and outputs the ciphertext as:

Let Entity_j with identity ID_k = (I₁,..., I_k) be an ancestor of Entity_j, the private key for Entity_k denoted is extracted as:

Entity_k can decrypt ciphertext C denoted , intended for Entity_j, 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 Entity_j is an ancestor of Entity_j (without respect to whether Entity_j is capable of deriving private keys for Entity_j or not) and an encryptor encrypts a given messageMεG₁ on Entity_j’s identity ID_j = (I₁,..., I_j) as:

then Entity_j 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 I_j in Zq. Because α₁,... and α_l are all uniformly and independently selected from Z_q, 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 Entity_j by Entity_i as an ancestor equals the probability that a specific value modq∈Z_q is selected as qεZ_q. Similarly, if α_j is a descendant of Entity_j, 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 I₁→...→I_j and I_j→...→I_j, i.e. by randomizing the master secret of the root PKG along the former and privacy specifically pertained to local identifier I_j (dedicated privacy) along the later and at last get a private key for Entity_j. 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