ID-based encryption for complex hierarchies with applications to forward security and broadcast encryption.
A forward-secure encryption scheme protects secret keys from exposure by evolving the keys with time. Forward security has several unique requirements in hierarchical identity-based encryption (HIBE) scheme: (1) users join dynamically; (2) encryption is joining-time-oblivious; (3) users evolve secret keys autonomously. We present a scalable forward-secure HIBE (fs-HIBE) scheme satisfying the above properties. We also show how our fs-HIBE scheme can be used to construct a forward-secure public-key broadcast encryption scheme, which protects the secrecy of prior transmissions in the broadcast encryption setting. We further generalize fs-HIBE into a collusion-resistant multiple hierarchical ID-based encryption scheme, which can be used for secure communications with entities having multiple roles in role-based access control. The security of our schemes is based on the bilinear Diffie-Hellman assumption in the random oracle model.
Introduction
The idea of an identity-based encryption (IBE) scheme is that an arbitrary string can serve as
a public key. The main advantage of this approach is to largely reduce the need for public key
certificates and certificate authorities, because a public key is associated with identity information
such as a user's email address. A first scheme for identity-based encryption (BF-IBE) was based
on the bilinear Di#e-Hellman assumption in the random oracle model by Boneh and Franklin [11].
In IBE schemes private key generator (PKG) is responsible for generating private keys for all users,
and therefore is a performance bottleneck for organizations with large number of users. Hierarchical
identity-based encryption (HIBE) schemes [9, 22, 26] were proposed to alleviate the workload of a
root PKG by delegating private key generation and identity authentication to lower-level PKGs.
In a HIBE scheme, a root PKG needs only to generate private keys for domain-level PKGs, who in
turn generate private keys for users in their domains in the next level. The organization of PKGs
and users forms a hierarchy that is rooted by the root PKG. To encrypt a message, Alice needs to
obtain the public parameters of Bob's root PKG, and the ID for Bob and for those domain-level
PKGs that are on the path from the root to Bob; there are no lower-level parameters. Gentry and
Silverberg [22] extended BF-IBE scheme and presented a fully scalable hierarchical identity-based
encryption (GS-HIBE) scheme. Later, a HIBE construction with a weaker notion of security was
given by Boneh and Boyen [9]. Most recently, new IBE and HIBE constructions that can be proved
to have the full security without the random oracle model [8, 36] were given.
# Department of Computer Science, Brown University, Providence, RI 02912, {dyao, anna}@cs.brown.edu.
Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, New York,
NY 10012, {fazio, dodis}@cs.nyu.edu
Due to the inherent key-escrow property 1 , the standard notion of HIBE security crucially depends
on secret keys remaining secret. Key exposure is a realistic threat over the lifetime of such
a scheme. To mitigate the damage caused by the exposure of secret key information in HIBE, one
way is to construct a forward-secure hierarchical identity-based encryption (fs-HIBE) scheme that
allows each user in the hierarchy to refresh his or her private keys periodically while keeping the
public key the same. A forward-secure public-key encryption scheme has recently been presented by
Canetti, Halevi and Katz [13]. But surprisingly, a practical fs-HIBE scheme has several unique requirements
that cannot be achieved by trivial combinations of the existing fs-PKE schemes [13, 27]
and HIBE scheme [9, 22].
Apart from being interesting on its own, fs-HIBE is a useful tool that lends itself to several
applications. One such application is the implementation of forward secrecy for public-key broadcast
encryption. While forward secrecy is an important requirement in any context, it is especially
needed for broadcast encryption [7, 18, 20, 29, 37]. This is because by design an adversary can
freely listen to any broadcast and store it. Then, should the adversary ever succeed in recovering
any user's secret key, she will manage to decrypt all past broadcasts that such user was authorized
to receive unless we have forward secrecy.
Below, we discuss the notion of forward security for HIBE in more detail, and then explain why
it cannot be trivially achieved by existing techniques such as a combination of fs-PKE [13] and
schemes.
1.1 Forward Security
The central idea of forward secrecy is that the compromise of long-term keys does not compromise
past session keys and therefore past communications. This notion was first proposed by G-unther
[21] and later by Di#e et al. [14] in key exchange protocols. The notion of non-interactive forward
security was proposed by Anderson [3] in 1997 and later formalized by Bellare and Miner [4], who
also gave a forward-secure signature scheme followed by a line of improvement [1, 30]. In this model,
secret keys are updated at regular intervals throughout the lifetime of the system; furthermore,
exposure of a secret key corresponding to a given interval does not enable an adversary to break
the system (in the appropriate sense) for any prior time period. The model inherently cannot
prevent the adversary from breaking the security of the system for any subsequent time period.
Bellare and Yee [6] provided a comprehensive treatment of forward security in the context of private
based cryptographic primitives.
The first forward-secure public-key encryption (fs-PKE) scheme was given by Canetti, Halevi,
and Katz [13] based on the Gentry-Silverberg HIBE [22] scheme. The fs-PKE scheme constructs
a binary tree, in which a tree node corresponds to a time period and has a secret key. Children
of a node w are labeled w0 and w1, respectively. Given the secrets corresponding to a prefix of
a node representing time t, one can compute the secrets of time t. In order to make future keys
computable from the current key, the secrets associated with a prefix of a future time are stored in
the current key. After the key for the next time period is generated, the current decryption key is
erased. The state-of-the-art fs-PKE scheme [13] is based on the decisional bilinear Di#e-Hellman
assumption [11] in the standard model. Canetti, Halevi and Katz also gave a more e#cient scheme
in the random oracle model [13].
knows the private keys of its child nodes.
1.2 Requirements of an fs-HIBE Scheme
Intuitively, forward security in a HIBE scheme implies that compromise of the current secret key of
a user only leads to the compromise of the user and his descendants' subsequent communications.
We will give a formal definition of security in Section 2.3. Our design of a forward-secure HIBE
scheme also takes system properties such as scalability and e#ciency into consideration. This is
essential in the management of large scale distributed systems. Below, we define the requirements
for a scalable forward-secure HIBE scheme.
. New users should be able to join the hierarchy and receive secret keys from their parent nodes
at any time.
. Encryption is joining-time-oblivious, which means that the encryption does not require knowledge
of when a user or any of his ancestors joined the hierarchy. The sender can encrypt the
message as long as he knows the current time and the ID-tuple of the receiver, along with the
public parameters of the system.
. The scheme should be forward-secure.
. Refreshing secret keys can be carried out autonomously, that is, users can refresh their secret
on their own to avoid any communication overhead with any PKG.
Surprisingly, the design of an fs-HIBE scheme that fulfils the above system requirements turns
out to be non-trivial, despite the fact that both HIBE [22] scheme and fs-PKE [13] scheme are
known. Intuitive combinations of the two schemes fail to achieve all the desired system features.
Next, we explain why this is the case.
1.3 Some Forward-Secure HIBE Attempts
In this section, we make three simple forward-secure HIBE constructions based on HIBE scheme
[22] and fs-PKE scheme [13], and explain why these naive schemes do not satisfy the requirements
of a practical fs-HIBE scheme.
1.3.1 Scheme I
Consider a scheme based on the HIBE [22] scheme. The user with a given ID tuple
maintains two sub-hierarchies (subtrees): the time subtree that evolves over time for forward
security (as in fs-PKE [13]), and the ID subtree to which other nodes are added as children join the
hierarchy. To encrypt a message for this user at time t, use the HIBE with identity (ID 1 , . , ID h , t).
The user can decrypt this message using HIBE decryption, using the fact that he knows the key
from the time subtree. The user's children are added to the hierarchy into the ID subtree.
The problem with this scheme is combining dynamic joins with forward security. Suppose a
user never erases the secret key corresponding to the root of his ID subtree. Then should this key
ever be exposed, the forward secrecy of his children is compromised. On the other hand, if this
secret key is ever erased, then no nodes can be added as children of (ID 1 , . , ID h ) in the hierarchy,
and so this scheme will not support dynamic joins.
The lesson we learn from this failed scheme is that all keys must be evolved together.
1.3.2 Scheme II
Let us try to repair Scheme I by making sure that the key from which children's keys are derived
is also evolving over time. In Scheme II, the public key of a user consists of alternating ID-tuples
and time strings, which is referred to as an ID-time-tuple. The private key of a user serves three
purposes: decryption, generating private keys for new children, and deriving future private keys
of the user. The public key of a newly joined child is the parent's ID-time-tuple appended with
the child's ID. That key is in turn used for generating keys for lower-level nodes further down the
hierarchy. For example, if Alice joins Bob, the root, at time (January, Week 1 ) and Eve joins Alice
at time (January, Week 2 ), Eve's public key is (Bob, January, Week 1, Alice, January, Week 2,
Eve). Encrypting a message to Eve requires the sender to know when Eve and all her ancestors
joined the system. Therefore Scheme II is not joining-time-oblivious.
The lesson we learn from the failed Scheme II is that the keys must evolve in a way that is
transparent to the encryption algorithm.
1.3.3 Scheme III
In our final unsuccessful attempt, Scheme III, a user adds a child to the hierarchy by giving him or
her secret keys that depend both on the current time and on the child's position in the hierarchy.
This is achieved by requiring that messages may only be decrypted by those who know two keys: one
corresponding to the current time and the other corresponding to their positions in the hierarchy.
Each user autonomously evolves his time key, and gives his newly joined children his time key in
addition to their ID keys.
It is easy to see that this scheme is not forward-secure. An adversary who joins the hierarchy at
the beginning of time can corrupt a user at any future time and obtain his or her ID key. Moreover,
this adversary can derive any past time key (because he joined at the beginning of time). Thus,
this adversary may decrypt any past message addressed to the exposed user.
For the same reason, the multiple hierarchical identity-based encryption (MHIBE) scheme generalized
from Scheme III is not collusion-resistant, where the ciphertext for a user with multiple
identities can be decrypted if some other individuals collude. MHIBE scheme is useful for secure
communications with entities having multiple identities, and is described in Section 1.4.3 and 5.
1.3.4 Comparisons
All the above trivial approaches fail. Therefore, constructing a forward-secure hierarchical ID-based
encryption scheme that is both secure and scalable is not so straightforward. Our implementation,
which is described in next Section, is still based on GS-HIBE [22] scheme and fs-PKE [13] scheme.
Yet, it overcomes the problems existing in naive combinations of the two schemes, and satisfies
the requirements of supporting dynamic joins, joining-time-obliviousness, forward security, and
autonomous key updates.
1.4 Our Contributions
We make several contributions in this paper. First, we present a scalable and joining-time-oblivious
forward-secure hierarchical identity-based encryption scheme that allows keys to be updated au-
tonomously. Second, we show how our fs-HIBE scheme can be used to obtain a forward-secure
public-key broadcast encryption (fs-BE) scheme. Third, we generalize our fs-HIBE scheme and
discuss its application in secure communications with entities having multiple roles in role-based
access control (RBAC) [33].

Figure

1: A schematic drawing of keys for ID-
tuple (Hospital, ER,Doctor, Bob) at time period
in a forward-secure HIBE
scheme. The ID-tuple (Hospital, ER,Doctor, Bob)
of Bob is on x-axis. The tuple representing time
period (2004, January, Week 1) is on y-axis. The
origin represents the root identity (Hospital) and
the highest-level time period (2004). The dark
node represents Bob's key at Week 1. The grey
nodes correspond to keys of Bob's ancestors at
Week 1. Each white node represents an intermediate
key. Secret keys at both the grey and
white nodes can be used to compute private keys
for Bob.
JanuaryBob
Hospital Doctor
ER
1.4.1 Forward-Secure HIBE Scheme
Our fs-HIBE protocol is based on the HIBE scheme by Gentry and Silverberg [22] and forward-
secure public-key encryption (fs-PKE) [13] scheme due to Canetti, Halevi and Katz. It satisfies the
requirements of dynamic joins, joining-time-obliviousness, forward security, and autonomous key
updates.
A HIBE scheme involves only one hierarchy, whereas an fs-HIBE scheme has two hierarchies:
ID and time. Each (ID-tuple, time) pair can be thought of as a point on the two-dimensional grid
as follows. On the x-axis, we start with the identity of the root Public Key Generator in the ID
hierarchy (e.g. Hospital), then in position (1,0) we have the identity of the first-level PKG (e.g.
ER). In position (2,0) there is the identity of the second level PKG (e.g. Doctor), and in position
there may be another PKG or an individual user (e.g. Bob). Thus the x-axis represents
an ID-tuple, for example (Hospital, ER, Doctor, Bob). Similarly, the y-axis represents the time.
Divide a duration of time into multiple time periods and arrange them as leaf nodes of a tree.
Internal nodes of the tree represent the time spans associated with their child nodes. Then, the
origin of the grid corresponds to the root of the time hierarchy (e.g. 2004). In position (0, 1) we
have the first level of the time hierarchy (e.g. January), and in position (0, 2) there is the next
level of time hierarchy (e.g. Week 1). Thus a time period can be expressed as a tuple on the y-axis,
for example (2004, January, Week 1). Figure 1 gives a schematic drawing of the correspondence
between the tuples and keys in fs-HIBE.
In an fs-HIBE scheme, the secret key of an (ID-tuple, time) pair is associated with some path
on the grid. For each grid point on that path, there is a corresponding element in this secret key.
Such a path (secret key) is not joining-time-oblivious: it depends on when the user, as well as the
nodes higher up, join the system. However, when encrypting, the sender does not have to know the
path. What is non-trivial here is that, the path (secret key) and ciphertext of our fs-HIBE scheme
are designed in such a way that we do not need to come up with a separate ciphertext for each
possible path in order to achieve joining-time-obliviousness.
Our fs-HIBE scheme has collusion resistance and chosen ciphertext security in the random oracle
model [5] assuming the di#culty of the bilinear Di#e-Hellman problem [11, 13, 22], provided that
the depths of the ID hierarchy and time hierarchy are bounded by constants. The formal definitions
and proofs of the scheme are given in the paper. The complexities of various parameters in our
fs-HIBE scheme are summarized in Table 1 and are discussed in Section 6.
1.4.2 Forward-Secure Broadcast Encryption Scheme
We show how our fs-HIBE scheme can be used to construct a scalable forward-secure public-key
broadcast encryption (fs-BE) scheme, which protects the secrecy of prior transmissions. A broadcast
encryption (BE) [15, 16, 23, 24, 28, 31, 32, 35] scheme allows content providers to securely distribute
digital contents to a dynamically changing user population. Each active user is issued a distinct
secret key when he joins the system, by a trusted center. In comparison with the symmetric-key
setting, a public-key BE scheme of [15] has a single public key associated with the system, which
allows the distribution of the broadcast workload to untrusted third parties.
In a scalable forward-secure public-key broadcast encryption (fs-BE) scheme, users should be
able to update their secret keys autonomously, and the trusted center should allow users to dynamically
join the broadcast system at any time while achieving forward security. In addition, each
content provider does not need to know when each user joins the system in order to broadcast
the encrypted contents. The encryption algorithm of an fs-BE scheme should only depend on the
current time and the set of authorized users, and thus be joining-time-oblivious. Applying our
fs-HIBE to the public-key BE scheme [15] yields such an fs-BE scheme.
1.4.3 Multiple Hierarchical ID-Based Encryption
We further generalize our forward-secure hierarchical ID-based encryption scheme into a collusion-
resistant multiple hierarchical identity-based encryption (MHIBE) scheme, and describe its application
in secure communications with individuals who have multiple roles in role-based access
control (RBAC) [33]. In large-scale organizations, a user may own multiple identities, each of which
is represented by an ID-tuple. In MHIBE, a message can be encrypted under multiple ID-tuples
(identities) and can be decrypted only by those who have all the required identities. The collusion-
resistant property cannot be achieved using separate HIBE schemes. We note that the fs-HIBE
scheme is a special case of our MHIBE scheme, in that in fs-HIBE scheme, time can be viewed
as another identity of a user. Therefore the identities in MHIBE scheme capture a broad sense of
meaning.
Outline of the Paper
The rest of the paper is organized as follows. In Section 2 we give definitions for fs-HIBE scheme
and its security. In Section 3, we first recall the bilinear Di#e-Hellman assumption [11], and then
give the construction of an fs-HIBE scheme and analyze the security. In Section 4, we show how an
fs-HIBE scheme can be used to add forward secrecy to a public-key broadcast encryption scheme.
In Section 5, we describe the multiple hierarchical ID-based encryption scheme. The complexity
analysis is given in Section 6. Section 7 is the conclusion.
This section defines the notion of forward secrecy for HIBE scheme and the related security.
In an fs-HIBE scheme, secret keys associated with an ID-tuple are evolved with time. At any
time period i an entity joins the system (hierarchy), its parent node computes its decryption key
corresponding to time period i and other values necessary for the entity to compute its own future
secret keys. Once the newly joined entity receives this secret information, at the end of each period
it updates its secret key and erases the old key. During time period i, a message is encrypted under
an ID-tuple and the time i. Decryption requires the secret key of the ID-tuple at time i.
2.1 Notations
Time Period: As usual in forward-secure public-key encryption [13] scheme, we assume for simplicity
that the total number of time periods N is a power of 2; that is
ID-tuple: An entity has a position in the hierarchy, defined by its tuple of IDs: (ID 1 , . , ID h ).
The entity's ancestors in the hierarchy are the users / PKGs whose ID-tuples are {(ID 1 , . , ID
is the ID for the root PKG.
Keys: There are two types of keys: sk w,(ID 1 ,.,ID h ) and SK i,(ID 1 ,.,ID h ) . The node key sk w,(ID 1 ,.,ID h )
is the key associated with some prefix w of the bit representation of a time period i and a
tuple denotes the key associated with time i and an ID-tuple
It consists of sk keys as follows: SK i,(ID 1 ,.,ID h
w0 is a prefix of i}. When this causes no confusion, we denote the keys as sk w,h and SK i,h , respectively

2.2 fs-HIBE: Syntax
Forward-secure Hierarchical ID-Based Encryption (fs-HIBE) scheme: an fs-HIBE scheme
is specified by five algorithms: Root Setup, Lower-level Setup, Update, Encrypt, and
Decrypt:
Root Setup: The root PKG takes a security parameter k and the total number of time periods N ,
and returns params (system parameters) and the initial root key SK 0,1 . The system parameters
include a description of the message space M and the ciphertext space C. The system parameters
will be publicly available, while only the root PKG knows the initial root key.
Lower-level Setup: This algorithm is run by the parent of a newly joined child at time i to
compute the child's private key. During a time period i, a lower-level entity (user or lower-level
joins in the system at level h. Its parent at level h - 1 computes the entity's key SK i,h
associated with time period i. The inputs are the parent's private key SK i,h-1 , time i, and the
ID-tuple of the child. (Note that the functionality of our Lower-level Setup includes the
functionality of both the Lower-level Setup and the Extraction algorithm in the HIBE [22]
scheme. This simplifies the protocol without any loss of generality.)
Update: During the time period i, an entity (PKG or individual) with ID-tuple (ID 1 , . , ID h )
uses SK i,h to compute his key SK (i+1),h for the next time period
Encrypt: A sender inputs params, the index i of the current time period, M # M and the
ID-tuple of the intended message recipient, and computes a ciphertext C # C.
Decrypt: During the time period i, a user with the ID-tuple (ID 1 , . , ID h ) inputs params,
its secret key SK i,h associated with time period i and the ID-tuple, and returns the
message M # M.
Encryption and decryption must satisfy the standard consistency constraint, namely when SK i,h is
the secret key generated by algorithm Lower-level Setup for ID-tuple (ID 1 , . , ID h ) and time
period i, then: #M # M,
2.3 fs-HIBE: Security
We allow an attacker to make lower-level setup queries. Also, we allow the adversary to choose the
time period and the identity on which it wishes to be challenged. Notice that an adversary may
choose the time period and the identity of its targets adaptively or nonadaptively. An adversary
that chooses its targets adaptively first makes lower-level setup queries and decryption queries, and
then chooses its targets based on the results of these queries. A nonadaptive adversary, on the
other hand, chooses its targets independently from the results of the queries he makes. Security
against an adaptive-chosen-target adversary, which is captured below, is the stronger notion of
security than the non-adaptive one. It is also stronger than the selective-node security defined in
the fs-PKE scheme by Canetti et al. [13].
Chosen-ciphertext Security (CCA2): We say an fs-HIBE scheme is semantically secure against
adaptive chosen ciphertext, time period, and identity attack, if no polynomial time bounded adversary
A has a non-negligible advantage against the challenger in the following game.
Setup: The challenger takes a security parameter k, and runs the Root Setup algorithm. It
gives the adversary the resulting system parameters params. It keeps the root secrets to itself.
Phase 1: The adversary issues queries q 1 , . , q m , where q i is one of the
1. Lower-level setup query (t i , ID-tuple i the challenger runs the lower-level setup algorithm
to generate the private key SK (t i , ID-tuple i ) corresponding to
to the adversary.
2. Decryption query the challenger runs the lower-level setup algorithm
to generate the private key SK (t i ,ID-tuple i ) corresponding to the pair (t i , ID-tuple i ), runs the
Decryption algorithm to decrypt C i using SK (t i ,ID-tuple i ) , and sends the resulting plaintext to
the adversary.
These queries may be asked adaptively. Also, the queried ID-tuple i may correspond to a position
at any level in the ID hierarchy, and the adversary is allowed to query for a future time and then
for a past time.
Challenge: Once the adversary decides that Phase 1 is over, it outputs two equal length plaintexts
and an ID-tuple # on which it wishes to be challenged. The constraint
is that no lower-level setup query has been issued for ID-tuple # or any of its ancestors for any time
The challenger picks a random bit b # {0, 1}, and sets C
It sends C # as a challenge to the adversary.
Phase 2: The adversary issues more queries q m+1 , . , q n , where q i is one of 3 :
1. Lower-level setup query (t i , ID-tuple i ), where the time period t i and ID-tuple i are under the
same restriction as in Challenge: the challenger responds as in Phase 1.
2. Decryption query the challenger responds as in Phase 1.
Guess: The adversary outputs a guess b # {0, 1}. The adversary wins the game if We
define its advantage in attacking the scheme to be |
3 A Forward-secure HIBE Scheme
Here, we present a forward-secure hierarchical identity-based encryption scheme. Following the
presentation standard in the IBE literature [11, 22], we first present an fs-HIBE with one-way
security. One-way security is the weakest notion of security. It means that it is hard to recover a
2 In the random oracle model, the adversary may also issue public key queries. Public key query (t i , ID-tuple i
challenger runs a hash algorithm on (t i , ID-tuple i ) to obtain the public key H(t i # ID-tuple i ) corresponding to
3 In the random oracle model, the adversary may also issue public key query. Public key query (t i , ID-tuple i the
challenger responds as in Phase 1.
plaintext with a passive attack. A standard technique, due to Fujisaki and Okamoto [19], converts
one-way security to CCA2 security in the random oracle model. For completeness, we give our
definition of one-way security in the Appendix B, and the Fujisaki-Okamoto conversion of the one-way
secure fs-HIBE in the Appendix C. Our scheme, which is based on the HIBE scheme of Gentry
and Silverberg [22] and the fs-PKE scheme of Canetti, Halevi and Katz [13, 27], overcomes the
scalability and security problems that exist when naively combining the two schemes as described
in Section 1.3. Next, we first give the number theoretic assumptions needed in our scheme, and
then describe the algorithms in our construction. Proofs of security of our fs-HIBE scheme are
shown in the Appendix D.
3.1 Assumptions
The security of our fs-HIBE scheme is based on the di#culty of the bilinear Di#e-Hellman (BDH)
problem [11]. Let G 1 and G 2 be two cyclic groups of some large prime order q. We write G 1
additively and G 2 multiplicatively. Our schemes make use of a bilinear pairing.
Admissible pairings: Following Boneh and Franklin [11], we call -
e an admissible pairing if
is a map with the following properties:
1. Bilinear: -
e(P, Q) ab for all P, Q # G 1 and all a, b # Z.
2. Non-degenerate: The map does not send all pairs in G 1 -G 1 to the identity in G 2 .
3. Computable: There is an e#cient algorithm to compute - e(P, Q) for any P, Q # G 1 .
We refer the readers to papers by Boneh and Franklin [11] and Boneh and Silverberg [12] for
examples and discussions of groups that admit such pairings.
Bilinear Di#e-Hellman (BDH) Parameter Generator: As in IBE [11] scheme, a randomized
algorithm IG is a BDH parameter generator if IG takes a security parameter k > 0, runs in time
polynomial in k, and outputs the description of two groups G 1 and G 2 of the same prime order q
and the description of an admissible paring
BDH Problem: As in IBE [11] scheme, given a randomly chosen P # G 1 , as well as aP, bP, and
cP (for unknown randomly chosen a, b, c # Z q ), compute - e(P, P ) abc .
For the BDH problem to be hard, G 1 and G 2 must be chosen so that there is no known algorithm
for e#ciently solving the Di#e-Hellman problem in either G 1 or G 2 . Note that if the BDH problem
is hard for a paring - e, then it follows that - e is non-degenerate.
BDH Assumption: As in IBE [11] scheme, we say a BDH parameter generator IG satisfies the
BDH assumption if the following is negligible in k for all PPT algorithm A:
e, P, aP, bP, cP
3.2 fs-HIBE: Implementation
For simplicity of description, our fs-HIBE construction makes use of a version of fs-PKE scheme
due to Katz [27]. In Katz's scheme, time periods are associated with the leaf nodes of a binary tree
(Rather than with all tree nodes as in the scheme by Canetti et al. [13]. Our fs-HIBE scheme can
also be realized based on the fs-PKE scheme by Canetti et al., which will give faster key update
time. The complexity discussion of our scheme is in Section 6).
We construct a full binary tree of height l, as in Katz's scheme [27]. The root of this tree is
labeled #; all other nodes are recursively labeled as follows: if the label of a node is w, then its left
child is labeled w0, and its right child is labeled w1. This way, for each time period i # {0, N - 1},
there is a leaf labeled with the binary representation of i. Following the fs-PKE scheme [13], we
denote the k-bit prefix of a word d. The
word w is of length d, i.e.
At the beginning of time, public parameters are generated. At time t, the entity at level h with
ID-tuple (ID 1 , . , ID h ) holds a secret key SK t,(ID 1 ,.,ID h ) . Recall that we denote key SK t,(ID 1 ,.,ID h )
as SK t,h when this causes no confusion. SK t,h consists of (sk t,h , {sk w,h }), where w are all the labels
of the right sibling, if one exists, of each ancestor of the node labeled t in the complete binary tree.
sk w,h are also called node keys. At the beginning of time, as public parameters are generated, the
values sk 0,1 and sk 1,1 are created by the root PKG, whose ID is ID 1 . Each sk w,h , where w is any
string, can be used to compute an sk w,u , where u > h, for tuple (ID 1 , . , ID u ) who is a descendant
of (ID 1 , . , ID h ). The algorithm to use is Lower-Level Setup.
Each sk w,h , where w is any string, is also used to compute the value sk (w#b),h , where
or 1. They are the child nodes of w on the binary tree. The algorithm for doing so is Compute
Next, which is defined as follows. In Compute Next, an entity (a PKG or a user) with ID-tuple
uses the value sk w,h associated with a node w to compute values sk (w0),h and sk (w1),h
for the two child nodes of w. Compute Next is a helper function and is called by the algorithm
Root Setup and Update.
We must delete all information from which sk t # can be inferred. The algorithm for
computing the keys for the next time period and erasing old keys is Update.
The public parameters, time t, and ID-tuple (ID 1 , . , ID h ) are all that a sender needs in order
to send an encrypted message to ID-tuple (ID 1 , . , ID h ) at time t using algorithm Encrypt.
The value sk t,h is all that the user with tuple (ID 1 , . , ID h ) needs in order to decrypt at time
t. The algorithm for doing so is Decrypt.
Let us look at the contents of each sk w,h more closely. It has two components Sw,h and Qw,h .
Sw,h is a point in G 1 , and Qw,h contains a set of Q-values, which will be explained later. If w
represents a leaf on the binary tree, Sw,h and the Q-values in Qw,h together are used for decryption
for ID-tuple (ID 1 , . , ID h ) at time w. If w is an internal node on the binary tree, these values are
used for generating future decryption keys.
Computing Sw,h makes use of |w| -h number of secret values s w| k ,(ID 1
are
clear from the context. Given a node w on the binary tree and an ID-tuple (ID 1 , . , ID h ), there
is a secret value s k,j for every (time, ID-tuple) combination, where time corresponds to a node
that has some prefix w| k of node w (including w itself and excluding the root node #) and ID-tuple
is some ancestor (ID 1 , . , ID j ) of ID-tuple (ID 1 , . , ID h ) (including itself). Each s k,j is chosen
randomly from Z q .
Each s k,j is also used for computing Q k,j , which is called a Q-value. For each s k,j there is a
Q-value Q k,j , which is an element in G 1 . Q-values are used in Decrypt. Qw,h is a set of Q-values.
All s k,j values are erased once Sw,h and Q-values are computed. The construction is shown below.
Construction Let IG be a BDH parameter generator for which the BDH assumption holds.
Root The root PKG with ID 1 does the following:
1. IG is run to generate groups G 1 , G 2 of order q and bilinear map -
e.
2. A random generator P # G 1 is selected along with random s # Z q . Set
3. Choose a cryptographic hash function Choose a cryptographic hash function
n. The security analysis will treat H 1 and H 2 as random oracles
[5]. The message space is . The ciphertext space is
is the level of the recipient. The system parameters are params
e,
All operations of fs-HIBE are performed under params. The master key is s # Z q .
The root PKG needs to generate not only the sk key associated with the current time period
0, but also the sk keys corresponding to the internal nodes on the binary tree whose
bit representations are all 0 except the last bit. The sk key for time 0 is denoted as sk 0 l ,1 .
The rest of sk values are used by the root PKG to generate keys for future time periods, and
are represented as {sk 1,0 , sk (01),1 , . , sk (0 l-1 1),1 }. These values are generated recursively as
follows.
(a) Set the secret point S 0,1 to s
(b) Set secret key sk uses sk 0,1 to recursively
call algorithm Compute Next (defined below) to generate its secret keys. Let
(c) Set the root PKG's secret key for time period 0 as SK
and erase all other information.
Compute This is a helper method and is called by the Root Setup
and Update algorithms. It takes a secret key sk w,h , a node w, and an ID-tuple, and outputs keys
sk (w0),h , sk (w1),h for time nodes w0 and w1 of (ID 1 . ID h ). (Note that this is similar to the
Extraction algorithms in the Gentry-Silverberg HIBE and the Derivation algorithm in the
fs-PKE schemes, only here we extract keys corresponding to nodes in the time hierarchy for a given
ID-tuple.)
1. Parse w as w 1 . w d , where Parse ID-tuple as ID 1 , . , ID h . Parse sk w,h associated
with time node w as (S w,h , Qw,h ), where
h, except for
2. Choose random s (d+1),j # Z q for all 1 # j # h.
3. Set S
4. Set S
5. Set Q
6. Set Q (w0),h and Q (w1),h to be the union of Qw,h and Q (d+1),j for all 1 # j # h.
7. Output sk
8. Erase s (d+1),j for all 1 # j # h.
Lower-level be an entity that joins the hierarchy
during the time period i <
using its key SK i,(h-1) as follows:
1. Parse i as i 1 . i l where l = log 2 N . Parse SK i,(h-1) as (sk i,(h-1) , {sk (i| k-1 1),(h-1) } i k =0 ).
2. For each value sk w,(h-1) in SK i,(h-1) , E h 's parent does the following to generate E h 's key
(a) Parse w as w 1 . w d , where d # l, and parse the secret key sk w,(h-1) as (S w,(h-1) , Q
(b) Choose random s k,h # Z q for all 1 # k # d. Recall that s k,j is a shorthand for
associated with time node w| k and tuple (ID 1 . ID j ).
(c) Set the child entity E h 's secret point
(d) Set Q d. Let Qw,h be the union of Q w,(h-1) and Q k,h for all
to be (S w,h , Qw,h ).
3. E h 's parent sets E h 's SK
At the end of time i, an entity (PKG or
individual) with ID-tuple (ID 1 , . , ID h ) does the following to compute its private key for time i+1,
as in the fs-PKE scheme [13, 27].
1. Parse i as i 1 . i l , where
2. We distinguish two cases. If i simply output the remaining keys as the key SK (i+1),h for
the next period for ID-tuple (ID 1 , . , ID h ). Otherwise, let - k be the largest value such that
must exist since i < N - 1). Let i
1. Using sk (which is included as
part of SK i,h ), recursively apply algorithm Compute Next to generate keys sk (i # 0 d 1),h
for
. The key sk (i # 0 d- k ,h)
will be used for decryption in the
next time period the rest of sk keys are for computing future keys. Erase sk i # ,h and
output the remaining keys as SK (i+1),h .
1. Parse i as i 1 . i l . Select random r # Z q .
2. Denote P
1. Parse i as i 1 . i l . Parse SK i,h associated with the ID-tuple as (sk i,h , {sk (i| k-1 1),h } i k =0 ) and
the key sk i,h as (S i,h , Q h, except for
2. Parse C as (U 0 , U 2,1 , . , U l,1 , U 1,2 , . , U l,2 , . , U 1,h , . , U l,h , V ).
3.
is: # l
Verification of the correctness of our Decrypt algorithm is shown in the Appendix A. In Appendix
using Fujisaki-Okamoto padding [19] and the help of random oracles H 3 and H 4 , algorithm
Encrypt and Decrypt can be converted into ones with chosen ciphertext security, as in BF-IBE
[11] and GS-HIBE [22].
Theorem 3.1. Suppose there is a nonadaptive adversary A that has advantage # against the one-way
secure fs-HIBE scheme for some fixed time t and ID-tuple, and that makes q H 2
to the hash function H 2 and a finite number of lower-level setup queries. If the hash functions H 1 ,
are random oracles, then there is an algorithm B that solves the BDH in groups generated by
IG with advantage
and running time O(time(A)).
Theorem 3.2. Suppose there is an adaptive adversary A that has advantage # against the one-way
secure fs-HIBE scheme targeting some time and some ID-tuple at level h, and that makes
queries to the hash function H 2 and at most q E > 0 lower-level setup queries. Let
is the total number of time periods. If the hash functions H 1 , H 2 are random
oracles, then there is an algorithm B that solves the BDH in groups generated by IG with advantage
(#( h+l
and running time O(time(A)).
The proofs of the theorems are in the Appendix D.
4 Application: Forward-Secure Broadcast Encryption
In this section, we show how the fs-HIBE scheme can be used to build a scalable forward-secure
public-key broadcast encryption (fs-BE) scheme which is joining-time-oblivious. In what follows,
N denotes the total number of time periods, E denotes the universe of users and
4.1 fs-BE: Syntax
Forward-Secure Broadcast Encryption (fs-BE): An fs-BE scheme is specified by five poly-time
algorithms KeyGen, Reg, Upd, Enc, Dec:
KeyGen: The key generation algorithm, is a probabilistic algorithm run by the center to set up
the parameters of the scheme. KeyGen takes as input a security parameter k and possibly r max
(where r max is a revocation threshold, i.e. the maximum number of users that can be revoked).
The input also includes the total number E of users in the system and the total number of time
periods N . KeyGen generates the public key PK and the initial master secret key MSK 0 .
Reg: The registration algorithm, is a probabilistic algorithm run by the center to compute the
secret initialization data for a new user. Reg takes as input the master secret key MSK t at time
t, the identity u of the user and the current time period t < N - 1 and outputs the new secret
Upd: The key update algorithm, is a deterministic algorithm run by an entity (center or user) to
update its own secret key of time t into a new secret key valid for the following time period t + 1.
For a user, Upd takes as input the public key PK, the identity u of a user, the current time period
t < N - 1, and the user's secret key USK t,u , and outputs the new user's secret key USK t+1,u . For
the center, the algorithm takes as input the public key PK, the current time period t < N , and
the key MSK t , and outputs the secret key MSK t+1 .
Enc: The encryption algorithm, is a probabilistic algorithm that each content provider can use to
encrypt messages. Enc takes as input the public key PK, a message M , the current time period
t and a set R of revoked users (with |R| # r max , if a threshold has been specified to the KeyGen
algorithm), and returns the ciphertext C to be broadcast.
Dec: The decryption algorithm, is a deterministic algorithm run by each user to recover the content
from the broadcast. Dec takes as input the public key PK, the identity u of a user, a time period
t < N , the user's secret key USK t,u and a ciphertext C, and returns a message M .
An fs-BE scheme should satisfy the following correctness constraint: for any pair (PK,MSK t )
output by the algorithm KeyGen(k, r max , N,E), any t < N , any R # user
(properly generated for time period t) and any message M , it
should hold that:
t, USK t,u , Enc(PK,M, t, R)).
4.2 fs-BE: Security
In fs-BE scheme, if a user leaks his or her secret key and is not revoked by a content provider,
the security of subsequent communications broadcasted by such provider is compromised. As a
matter of fact, the forward security of broadcast encryption schemes guarantees that this is the
only case where unauthorized access to the broadcast content may occur. The advantage of the
adversary is not significantly improved even if she corrupts multiple users at di#erent time periods.
We formalize the security definition of fs-BE below.
Chosen-ciphertext Security: An fs-BE scheme is forward-secure against chosen-ciphertext attack
if no polynomial time bounded adversary A has a non-negligible advantage against the challenger
in the following game:
Setup: The challenger takes security parameters k, r max , and runs the KeyGen algorithm, for the
specified number of users E and time periods N . It gives the adversary the resulting system public
key PK and keeps the initial master secret key MSK 0 secret to itself.
Phase 1: The adversary issues, in any adaptively-chosen order, queries q 1 , . , q m , where q i is one
of the followings:
1. Corrupt query (u, t): the challenger runs algorithm Reg(MSK t , u, t) to generate the private
corresponding to user u at time t, and sends USK t,u to the adversary.
2. Decryption query (u, t, C): the challenger first runs the Reg(MSK t , u, t) algorithm to recover
private key USK t,u corresponding to user u at time t, and then runs decryption algorithm
Dec(PK, u, t, USK t,u , C) to decrypt C, and sends the resulting plaintext to the adversary.
Challenge: Once the adversary decides that Phase 1 is over, it outputs two equal-length plaintexts
and a time period t # on which it wishes to be challenged. The challenger picks a
random bit b # {0, 1}, and set C asked a query
It sends C # as a challenge to the adversary.
Phase 2: The adversary issues more queries q m+1 , . , q n , where q i is one of:
1. Corrupt query (u, t): the challenger first checks that either u # R t # or t > t # and if so, it
responds as in Phase 1. Notice that if a bound r max was specified in KeyGen, then the
adversary is restricted to corrupt at most r max distinct users via Corrupt queries.
2. Decryption query (u, t, C): the challenger first checks that either C #= C # or u # R t # or t #= t #
and if so, it responds as in Phase 1.
Guess: The adversary outputs a guess b # {0, 1} and wins the game if We define its
advantage in attacking the scheme to be |
4.3 fs-BE: A Construction Based on fs-HIBE
Here, we show how our fs-HIBE scheme can be applied to the construction of the public-key
broadcast encryption of [15] to obtain a forward-secure public-key BE scheme. Dodis and Fazio
[15] provided a construction that extends the symmetric-key broadcast encryption scheme of Naor
et al. [31] to the public-key setting, based on any secure HIBE scheme: for ease of reference, we
include it in Appendix E.1. The construction of [15] also applies to the scheme of Halevy and
Shamir [24], that improves upon the work of [31]. The symmetric-key BE scheme of Halevy and
Shamir is an instance of the Subset Cover Framework [31]. The main idea of the framework is to
define a family S of subsets of the universe E of users in the system, and to associate each subset
with a key, which is made available to all the users belonging to the given subset. To broadcast a
message to all the subscribers except those in some set R, a content provider first covers the set of
privileged users using subsets from the family S. This is done by identifying a partition of E \ R,
where all the subsets are elements of S. Then, the provider encrypts the message for all the subsets
in that partition. To decrypt, a user u /
first identifies the subset in the partition of E \ R to
which he belongs, and then recovers the corresponding secret keys from his secret information.
In the public-key BE scheme [15], the subsets containing a given user are organized into groups,
and a special secret key, protokey, is associated with each of these groups. A user only needs to
store these protokeys, from which he can derive the actual decryption keys corresponding to all the
subsets in the group. Such an organization of the subsets of the family S produces a hierarchy, in
which the leaves are elements of S and each internal node corresponds to a group of subsets. Using
HIBE, a secret key can be associated with each internal node in the hierarchy, and constitutes the
protokey for the group corresponding to that internal node.
In order to add forward secrecy in the public-key BE scheme, we essentially apply the fs-HIBE
scheme to the above hierarchy. In fs-BE scheme, a protokey is associated with not only a node in
the hierarchy, but also with a time period t. In the KeyGen operation, the center runs the Root
Setup algorithm of fs-HIBE to compute its master secret SK 0,1 . This key evolves with time, and is
used by the center to compute protokeys for users. In the Reg operation, a user joins the broadcast
at some time t, and the center uses its current master secret key SK t,1 to derive protokeys for the
user by running the Lower-level Setup of fs-HIBE. The center and users evolve their secret
keys with time autonomously by calling the Update algorithm of fs-HIBE. In the Enc algorithm,
a content provider uses the Encrypt algorithm of fs-HIBE to encrypt the message not only with
respect to the nodes in the hierarchy that represents the subsets in the partition of E \ R, but
also to the current time t. In the Dec operation, the user first runs the Lower-Level Setup
algorithm of fs-HIBE to derive the current secret keys from his protokey at time t. These secret
are used for decryption. The construction of our fs-BE scheme is given in Appendix E. We
analyze the complexity of fs-BE operations in Section 6.
5 Multiple Hierarchical Identity-Based Encryption Scheme
ID-based cryptographic schemes have been used in complex access control scenarios [25, 34]. In this
paper, we generalize the fs-HIBE into a collusion resistant multiple hierarchical ID-based encryption
(MHIBE) scheme, where a message can be encrypted under multiple ID-tuples. The applications
of MHIBE scheme include secure communications with users having multiple identities.
Motivations for MHIBE In role-based access control systems (RBAC) [33], individuals are
assigned roles according to their qualifications, and access decisions are based on roles. The use of
roles to control access is proven to be an e#ective means for streamlining the security management
process [33]. Communications to a specific role may need to be protected so that messages can
be read only by members of that role. This can be done using a shared key approach, which can
be realized by an HIBE scheme. Members of a role are given a secret group key that is used for
decrypting messages encrypted with the group public key of that role, which is an ID-tuple in HIBE.
For example, the public key of the role doctor in the Emergency Room at a hospital is the ID-
tuple (Hospital, ER, doctor), and members of the role doctor are given the corresponding private
key in HIBE. The hierarchical structure of public keys in HIBE makes it particularly suitable
for managing role communications in large organizations. This group key approach is e#cient
and scalable compared to encrypting the message with individual recipients' personal public keys,
because a message is encrypted only once (under the public key of the role).
A user may have multiple roles. Some messages are intended to be read only by those who have
multiple roles, and should not be recovered by collusions among role members. For example, the
intended message recipients are those who must take on both role doctor in ER and role research
manager at the a#liated medical school of the hospital. In healthcare systems, medical data such
as patient records are extremely sensitive, therefore, achieving this type of secure communications
is important. However, the GS-HIBE [22] scheme provides cryptographic operations only if the
message is encrypted under one identity (ID-tuple). It cannot be used for communications to an
intersection of identities. Note that the Dual-Identity-Based Encryption scheme by Gentry and
Silverberg [22] is di#erent from what we want to achieve here. The word "dual" in their scheme
[22] refers that the identities of both the sender and the recipient, rather than just the recipient,
are required as input into the encryption and decryption algorithms.
To solve the problem of secure communications to members having multiple roles, we develop a
multiple hierarchical identity-based encryption (MHIBE) scheme, where encryption is under multiple
ID-tuples. In addition, it can be used for authenticating multiple hierarchical identities in the
hidden credential protocol [25], where the success of authentication of identities is implied if one
can correctly decrypt the message encrypted with the required identities of the intended recipi-
ents. What makes the problem interesting is that the intersection of identities is di#erent from the
union of identities, which implies that a proper scheme should be collusion-resistant: secure even
if adversaries with partial roles collude. In other words, it requires that compromising the private
keys of individual identities does not compromise the messages encrypted with the intersection of
identities. This property cannot be achieved by the broken Scheme III described in Section 1.3,
where two separate HIBE schemes are used, as it is not collusion-resistant.
Next we use an example to describe the MHIBE scheme, including key acquisition, encryption,
and the properties of MHIBE implementation generalized from our fs-HIBE scheme.
5.1 Joining-path-obliviousness
In MHIBE, we define an identity-set as the set of identities that a user has, each represented as an
ID-tuple. For example, Bob's identity-set is {(Hospital, ER, Doctor), (Hospital, School, Manager)}.
An ancestor E # of a node E has the same number of ID-tuples in its identity-set as that of E, and
for each ID-tuple T in the identity-set of E, there is an ID-tuple in the identity-set of E # such that
it is either the ancestor of T in HIBE or the same as T . In addition, the ancestor E # of the node
cannot be E. All ancestors of node E are capable of generating secret keys for E.
In an MHIBE scheme, Bob may obtain his key directly from either of the two ancestor entities.
One is the entity whose identity-set is {(Hospital, ER), (Hospital, School, Manager)}. And the
other has the identity-set {(Hospital, ER, Doctor), (Hospital, School)}. Bob's parents obtain
their keys from their parents in the same way. The highest-level ancestor in this example is the
hospital and has the identity-set {Hospital, Hospital} (not {Hospital}). The root secret s # used for
computing the private key for identity-set {Hospital, Hospital} may be the same as the root secret
used in regular HIBE scheme [22]. The private key is set to s # H 1 (Hospital # Hospital). Bob's key
can be computed only by his ancestors in the MHIBE scheme. An MHIBE scheme needs to be
joining-path-oblivious. This means that encryption should be oblivious of the path from which the
receiver and his ancestors acquire their private keys. Having the receiver's identity-set is su#cient
to encrypt a message. For example, the sender does not need to know whether Bob obtains his keys
from entity {(Hospital, ER), (Hospital, School, Manager)} or from entity {(Hospital, ER, Doctor),
(Hospital, School)}.
5.2 Properties of Our MHIBE Implementation
Our fs-HIBE scheme naturally gives rise to an MHIBE scheme. In fs-HIBE, a message is encrypted
under both an ID-tuple and the current time. This can be viewed as the encryption under two tuples,
one being the current time. Therefore, the identities in MHIBE scheme capture a broader sense
of meaning. The MHIBE scheme generalized from our fs-HIBE scheme supports dynamic joins
and joining-path-oblivious encryption. More importantly, it is collusion-resistant, which cannot
be achieved by using multiple separate HIBE [22] schemes. In our MHIBE implementation, a
message encrypted under {(Hospital, ER, Doctor), (Hospital, School, Manager)} or {(Hospital,
School, Manager), (Hospital, ER, Doctor)} requires di#erent decryption keys. We note that in this
scheme, the fact that a user holds the private key corresponding to multiple identities does not
imply that he or she has the private key to any subset of identities.
We omit the details of MHIBE scheme (definition of security, description of scheme, and proof
of security), as this is a direct generalization of fs-HIBE scheme. The complexities of various
parameters of our MHIBE scheme are shown in Table 1 in Section 6.
6 Discussions
We analyze the complexity of our fs-HIBE scheme, the generalized MHIBE scheme, and the fs-
BE scheme in Table 1 showing running time complexities and key sizes. Key generation time of
fs-HIBE and MHIBE is the time to generate secret keys for a child node by the parent. Key
generation time of fs-BE scheme is the running time of Reg algorithm. In our fs-HIBE scheme,
the time periods correspond to leaf nodes of a binary tree, and the key update time is O(h log N ),
where N is the total number of time periods and h is the length of an ID-tuple. Because of the
node arrangement, the key generation time and key update time of our fs-HIBE scheme grows
logarithmically with the total number of time periods N . Faster key update time (O(h)) can be
achieved, if the time periods are associated with all the nodes of the tree in a pre-order traversal,
as in the fs-PKE scheme by Canetti et al. [13]. Because the realization of such an fs-HIBE scheme
can be easily derived from the construction in Section 3.2, it is omitted in this paper. We show the
optimized running time in Table 1.
Even dropping the joining-time-obliviousness requirement (as in the naive Scheme II of Section
1.3), our implementation cannot achieve a ciphertext with linear length O(h+log N ). It remains an
interesting open question whether a general fs-HIBE scheme with linear complexity can be realized.
Parameters fs-HIBE MHIBE fs-BE
Key generation time O(h log N) O(h m ) O(log 3 E log N)
Encryption time O(h log N) O(h m ) O(r log E log N)
Decryption time O(h log N) O(h m
Key update time O(h) N/A O(log 3 E)
Ciphertext length O(h log N) O(h m ) O(r log E log N)
Public
log

Table

1: Dependency of parameters of our fs-HIBE, MHIBE, and fs-BE schemes on the total number
N of time periods, the length h of an ID-tuple, the number m of ID-tuples in an identity-set in
MHIBE, the total number E of fs-BE users and the number r of actual revoked users in fs-BE
scheme. Key generation time of fs-HIBE and MHIBE is the time to generate secret keys for a child
node by the parent. Key generation time of fs-BE scheme is the running time of Reg algorithm.
7 Conclusion
The Multiple Hierarchical Identity-Based Encryption (MHIBE) scheme is an ID-Based encryption
scheme for complex hierarchies. The generalization of a collusion-resistant MHIBE scheme from
the Hierarchical Identity-Based Encryption (HIBE) scheme is significant, because MHIBE scheme
conveniently lends itself to a wide range of applications that cannot be accomplished using HIBE
schemes. To demonstrate this, we presented in detail a forward-secure HIBE scheme and a forward-
secure Broadcast Encryption scheme. We also described the application of MHIBE in the access
control paradigm. The forward-secure applications derived from our MHIBE scheme are joining-
time-oblivious and support dynamic joins, which make them scalable.

Acknowledgements

We are grateful to Shai Halevi and Jonathan Katz for helpful discussions. The first author is
thankful to Seth Proctor at Sun Microsystems Lab for his helpful comments.



--R


On the security of joint signature and encryption.
Two remarks on public-key cryptology
A forward-secure digital signature scheme
Random oracles are practical: a paradigm for designing e
Forward security in private-key cryptography
How to broadcast a secret.
Secure identity based encryption without random oracles.



Applications of multilinear forms to cryptography.
A forward-secure public-key encryption scheme



Chosen ciphertext security of multiple encryption.
Broadcast encryption.
Secure integration of asymmetric and symmetric encryption schemes.

An identity-based key exchange protocol
Hierarchical ID-based cryptography

The LSD broadcast encryption scheme.
Hidden credentials.
Toward hierarchical identity-based encryption
A forward-secure public-key encryption scheme

Combinatorial bounds for broadcast encryption.

Revocation and tracing schemes for stateless receivers.



A public-key traitor tracing scheme with revocation using dynamics shares

Secure group communications using key graphs.
--TR
An identity-based key-exchange protocol
Authentication and authenticated key exchanges
Random oracles are practical
Broadcast encryption
Role-Based Access Control Models
Secure group communications using key graphs
Forward-Secure Threshold Signature Schemes
A Forward-Secure Digital Signature Scheme
Long-Lived Broadcast Encryption
Identity-Based Encryption from the Weil Pairing
Revocation and Tracing Schemes for Stateless Receivers
The LSD Broadcast Encryption Scheme
Secure Integration of Asymmetric and Symmetric Encryption Schemes
Efficient Generic Forward-Secure Signatures with an Unbounded Number Of Time Periods
Toward Hierarchical Identity-Based Encryption
Hierarchical ID-Based Cryptography
Public Key Trace and Revoke Scheme Secure against Adaptive Chosen Ciphertext Attack
Role-based cascaded delegation
Hidden Credentials

--CTR
Vipul Goyal , Omkant Pandey , Amit Sahai , Brent Waters, Attribute-based encryption for fine-grained access control of encrypted data, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA
broadcast encryption;forward security;ID-Based encryption