1

CryptCloud : Secure And Flexible

Access Control for Cloud Storage
Qianhong Wu, Member, IEEE, Bo Qin, Lei Zhang, Member, IEEE, Josep Domingo-Ferrer, Fellow, IEEE
Oriol Farràs, and Jesús A. Manjón

Abstract—Traditional broadcast encryption (BE) schemes al- Nevertheless, a BE system heavily relies on a fully trusted key
low a sender to securely broadcast to any subset of members server who generates secret decryption keys for the members
but require a trusted party to distribute decryption keys. Group and can read all the communications to any members.
key agreement (GKA) protocols enable a group of members to
negotiate a common encryption key via open networks so that Group key agreement (GKA) is another well-understood
only the group members can decrypt the ciphertexts encrypted cryptographic primitive to secure group-oriented communica-
under the shared encryption key, but a sender cannot exclude tions. A conventional GKA [2] allows a group of members to
any particular member from decrypting the ciphertexts. In this establish a common secret key via open networks. However,
paper, we bridge these two notions with a hybrid primitive whenever a sender wants to send a message to a group, he
referred to as contributory broadcast encryption (ConBE). In
this new primitive, a group of members negotiate a common must first join the group and run a GKA protocol to share
public encryption key while each member holds a decryption key. a secret key with the intended members. More recently, and
A sender seeing the public group encryption key can limit the to overcome this limitation, Wu et al. introduced asymmetric
decryption to a subset of members of his choice. Following this GKA [3], in which only a common group public key is negoti-
model, we propose a ConBE scheme with short ciphertexts. The ated and each group member holds a different decryption key.
scheme is proven to be fully collusion-resistant under the decision
n-Bilinear Diffie-Hellman Exponentiation (BDHE) assumption in However, neither conventional symmetric GKA nor the newly
the standard model. Of independent interest, we present a new introduced asymmetric GKA allow the sender to unilaterally
BE scheme that is aggregatable. The aggregatability property is exclude any particular member from reading the plaintext 1.
shown to be useful to construct advanced protocols. Hence, it is essential to find more flexible cryptographic
Index Terms—Broadcast encryption, group key agreement, primitives allowing dynamic broadcasts without a fully trusted
contributory broadcast encryption, provable security. dealer.

A. Our Contributions
I. I NTRODUCTION
We present the Contributory Broadcast Encryption (ConBE)
ITH the fast advance and pervasive deployment of
W communication technologies, there is an increasing demand
of versatile cryptographic primitives to protect group
primitive, which is a hybrid of GKA and BE. Compared to
its preliminary Asiacrypt 2011 version [5], this full paper
provides complete security proofs, illustrates the necessity of
communications and computation platforms. These new plat- the aggregatability of the underlying BE building block and
forms include instant-messaging tools, collaborative comput- shows the practicality of our ConBE scheme with experiments.
ing, mobile ad hoc networks and social networks. These Specifically, our main contributions are as follows.
new applications call for cryptographic primitives allowing a First, we model the ConBE primitive and formalize its
sender to securely encrypt to any subset of the users of the security definitions. ConBE incorporates the underlying ideas
services without relying on a fully trusted dealer. Broadcast of GKA and BE. A group of members interact via open
encryption (BE) [1] is a well-studied primitive intended for networks to negotiate a public encryption key while each
secure group-oriented communications. It allows a sender member holds a different secret decryption key. Using the
to securely broadcast to any subset of the group members. public encryption key, anyone can encrypt any message to any
Q. Wu is with the School of Electronics and Information Engineering,
subset of the group members and only the intended receivers
Beihang University, and The State Key Laboratory of Integrated Services Net- can decrypt. Unlike GKA, ConBE allows the sender to exclude
works, Xidian University and State Key Laboratory of Information Security, some members from reading the ciphertexts. Compared to BE,
Institute of Information Engineering, Chinese Academy of Sciences, Beijing
100093, China (e-mail: [email protected]).
ConBE does not need a fully trusted third party to set up
B. Qin is with Key Laboratory of Data Engineering and Knowledge the system. We formalize collusion resistance by defining an
Engineering (Renmin University of China) Ministry of Education, School attacker who can fully control all the members outside the
of Information, Renmin University of China, ZhongGuanCun Street No. 59,
Haidian District, Beijing, China, Beijing, China (e-mail: [email protected]).
intended receivers but cannot extract useful information from
L. Zhang is with Shanghai Key Laboratory of Trustworthy Computing, the ciphertext.
Software Engineering Institute, East China Normal University, Shanghai,
1Dynamic symmetric GKA equipped with a leave sub-protocol allows the
China (e-mail: [email protected]).
J. Domingo-Ferrer, O. Farràs and J. A. Manjón are with Universitat Rovira i members to exclude some members from decrypting ciphertexts. In this case,
Virgili, Department of Computer Engineering and Mathematics, UNESCO if the sender (who is also a group member) wants to exclude some other
Chair in Data Privacy, Tarragona, Catalonia (e-mail: {josep.domingo, ori- members, he/she has to seek the agreement of the remaining members to run
ol.farras, jesus.manjon}@urv.cat). the leave sub-protocol. The sender cannot exclude any member unilaterally.
 2

Second, we present the notion of aggregatable broadcast C. Related Work

encryption (AggBE). Coarsely speaking, a BE scheme is
aggregatable if its secure instances can be aggregated into a A number of works have addressed key agreement protocols
new secure instance of the BE scheme. Specifically, only the for multiple parties. The schemes due to Ingemarsson et al.
aggregated decryption keys of the same user are valid decryp- [2] and Steiner et al. [7] are designed for n parties and
tion keys corresponding to the aggregated public keys of the require O(n) rounds. Tree key structures have been further
underlying BE instances. We observe that the aggregatability proposed, reducing the number of rounds to O(log n) [8],
of AggBE schemes is necessary in the construction of our [9], [10]. Multi-round GKA protocols pose a synchronism
ConBE scheme and the BE schemes in the literature are not requirement: in order to complete the protocol, all the group
aggregatable. We construct a concrete AggBE scheme tightly members have to stay online simultaneously. How to optimize
proven to be fully collusion-resistant under the decision BDHE the round complexity of GKA protocols has been studied in
assumption. The proposed AggBE scheme offers efficient several works (e.g., [11], [12], [13]). In [14], Tzeng presented
encryption/decryption and short ciphertexts. a constant-round GKA protocol that can identify cheaters.
Finally, we construct an efficient ConBE scheme with our Subsequently, Yi [15] constructed a fault-tolerant protocol
AggBE scheme as a building block. The ConBE construction in an identity-based setting. Burmester and Desmedt [16]
is proven to be semi-adaptively secure under the decision proposed a two-round n-party GKA protocol for n parties.
BDHE assumption in the standard model. Only one round is The Joux protocol [17] is one-round and only applicable to
required to establish the public group encryption key and set three parties. The work of Boneh and Silverberg [18] shows a
up the ConBE system. After the system set-up, the storage cost one-round (n + 1)-party GKA protocol with n-linear pairings.
of both the sender and the group members is O(n), where Dynamic GKA protocols provide extra mechanisms to han-
n is the number of group members participating in the set- dle member changes. Bresson et al. [19], [20] extended the
up stage. However, the online complexity (which dominates protocol in [21] to dynamic GKA protocols that allow mem-
the practicality of a ConBE scheme) is very low. We also bers to leave and join the group. The number of rounds in the
illustrate a trade-off between the set-up complexity and the set-up/join algorithms of the Bresson et al.’s protocols [19],
online performance. After a trade-off, the variant has O(n2/3) [20] is linear with the group size, but the number of rounds
complexity in communication, computation and storage. This in the leave algorithm is constant. The theoretical analysis
is comparable to up-to-date regular BE schemes which have in [22] shows that for any tree-based group key agreement
O(n1/2) complexity in the same performance metrics, but our scheme, the lower bound of the worst-case cost is O(log n)
scheme does not require a trusted key dealer. We conduct a rounds of interaction for a member to join or leave. Without
series of experiments and the experimental results validate the relying on a tree-based structure, Kim et al. [23] proposed a
practicality of our scheme. two-round dynamic GKA protocol. Recently, Abdalla et al.
[24] presented a two-round dynamic GKA protocol in which
B. Potential Applications only one round is required to cope with the change of members
A potential application of our ConBE is to secure data if they are in the initial group. Jarecki et al. [25] presented a
exchanged among friends via social networks. Since the Prism robust two-round GKA protocol in which a session key can be
scandal [4], people are increasingly concerned about the established even if some participants fail during the execution
protection of their personal data shared with their friends of the protocol. Observing that existing GKA protocols cannot
over social networks. Our ConBE can provide a feasible handle sender/member changes efficiently, Wu et al. presented
solution to this problem. Indeed, Phan et al. [6] underlined a group key management protocol [26] in which a change of
the applications of our ConBE [5] to social networks. In this the sender or monotone exclusion of group members does not
scenario, if a group of users want to share their data without require extra communication, and changes of other members
letting the social network operator know it, they can use our require one extra round.
ConBE scheme. Since the setup procedure of our ConBE only BE is another well-established cryptographic primitive de-
requires one round of communication, each member of the veloped for secure group communications. As the core of BE is
group just needs to broadcast one message to other intended to generate and distribute the key materials to the participants,
members in a send-and-leave way, without the synchronization BE schemes are also referred to as key distribution schemes
requirement. After receiving the messages from the other in some scenarios. While digital rights management motivated
members, all the members share the encryption key that allows most previous BE schemes [27], [28], recent efforts [29], [30],
any user to selectively share his/her data to any subgroup of [31], [32], [33], [34], [35] are devoted to modifying BE or
the members. Furthermore, it also allows sensitive data to be key distribution technologies in view of securing emerging
shared among different groups. Other applications may include information systems such as sensor networks, mobile ad hoc
instant messaging among family members, secure scientific networks, vehicular networks, etc.
research tasks jointly conducted by scientists from different BE schemes in the literature can be classified into two
places, and disaster rescue using a mobile ad hoc network. A categories, i.e., symmetric-key BE [1] and public-key BE [36].
common feature of these scenarios is that a group of users In the symmetric-key setting, only the trusted center generates
would like to exchange sensitive data but a fully trusted third all the secret keys and broadcasts messages to users. Hence,
party is unavailable. Our ConBE provides an efficient solution only the key generation center can be the broadcaster or
to these applications. the sender. Similarly to the GKA setting, tree-based key
 3

structures were independently proposed to improve efficiency ◆ CBSetup(U 1(x1), · · ·,U n(xn)). This interactive algorithm
in symmetric-key BE systems [37], [38], and further improved is jointly run by members 1U, , n·to· ·setU up a BE scheme.
in [39] with O(log n) keys. Cheon et al. [40] presented an Each member Ui takes private input xi (and her/his random
efficient symmetric BE scheme allowing new members to join coins representing the member’s random inner state infor-
the protocol anytime. Harn and Lin [41] proposed a group key mation). The communications between members go through
transfer protocol. Their protocol is based on secret sharing and authenticated and public channels. The algorithm will either
is considerably efficient, albeit it cannot revoke (compromised) abort or successfully terminate. If it terminates successfully,
users. each user U i outputs a decryption key dki securely kept by
In the public-key BE setting, the trusted center also gen- the user and a common group encryption key gek shared by
erates a public key for all the users so that any one can all the group members. The group encryption gek is publicly
play the role of a broadcaster or sender. Naor and Pinkas accessible. If the algorithm aborts, it outputs NULL. Here, we
presented in [36] the first public-key BE scheme in which up leave the input system parameters implicit. We denote this pro-
to a threshold of users can be revoked. Subsequently, [42] cedure by (U1(dk1), · · · , Un(dkn); gek) ←CBSetup(U1(x1),
presented a fully collusion-resistant public-key BE scheme · · · , Un(xn)).
exploiting new bilinear pairing technologies in which the key ◆ CBEncrypt(S, gek). This group encryption algorithm is run
√ by a sender who is assumed to know the public group encryp-
size, the ciphertext size, and the computation costs are O( n).
The scheme in [43] slightly reduces the size of the key and tion key. The sender may or may not be a group member.
the ciphertexts, although it still has sub-linear complexity. The The algorithm takes as inputs a receiver set S ⊆ { 1,· · · , n}
schemes presented in [44] strengthen the security concept of and the public group encryption key gek, and it outputs a pair
public-key BE schemes. As to performance, the sub-linear (c, ξ), where c is the ciphertext and ξ is the secret session key
√ in a key space K. Then (c, S) is sent to the receivers.
barrier O( n) has not yet been broken. In [45], Lewko et al. ◆ CBDecrypt(S, j, dkj, c). This decryption algorithm is run by
proposed two elegant schemes with constant public and secret each intended receiver j ∈ S. It takes as inputs the receiver set
keys, although their ciphertext size is linear with the number S, index j, the receiver’s decryption key dkj, and a ciphertext
of the revoked users, which is O(n) in the worst case. c, and it outputs the secret session key ξ.
D. Paper Organization A ConBE scheme is correct if the members in the receiver
set can always correctly decrypt when the members and the
The rest of this paper is organized as follows. In Section II, sender follow the scheme honestly. Formally, it is defined as
we model ConBE and define its security. In Section III, we follows.
present a collusion-resistant regular public-key BE scheme
with aggregatability. Efficient ConBE schemes are realized in Definition 1 (Correctness). A ConBE scheme is said to be
Section IV. We analyze the performance of our scheme in correct if for any parameter λ ∈ N and any element ξ
Section V and provide detailed proofs for the security results in the session key space, (U1(dk1), · · · , Un(dkn); gek) ←
in Section VI. Finally, Section VII concludes the paper. CBSetup(U1(x1), · · · , Un(xn)), and (c, ξ) ← CBEncrypt (S,
gek), it holds that CBDecrypt(S, j, dkj, c) = ξ for any j ∈ S.
II.M ODELING C ONTRIBUTORY B ROADCAST E NCRYPTION
A trivial ConBE scheme can be constructed by concurrently
We begin by formalizing the ConBE notion bridging the encrypting to each member with her/his public key in a
GKA and BE primitives. In ConBE, a group of members first traditional public-key cryptosystem. Unfortunately, the trivial
jointly establish a public encryption key; then a sender can solution incurs a heavy encryption cost and produces cipher-
freely select which subset of the group members can decrypt texts whose size grows linearly with the number of receivers.
the ciphertext. Since the negotiated public key is usually Another option would be a BE scheme in which the public key
employed to transmit session keys, we define a ConBE scheme is obtained by means of a multiparty computation protocol,
as a key encapsulation mechanism (KEM). but it would require extra communication and point-to-point
confidential channels between the users. The challenge is to
A. Syntax design ConBE schemes with efficient encryption and short
We first define the algorithms that compose a ConBE ciphertexts.
scheme. Let λ ∈ N denote the security parameter. Suppose that
a group of members{U1, · ·,· Un } want to jointly establish a B. Security Definitions
ConBE system, where n is a positive integer and each member
We next define the security of a ConBE scheme. Several
iU is indexed by i for 1 ≤ i ≤n. To focus on ConBE,
we assume that the communications between members are methods have been proposed to transform public key en-
authenticated. However, we do not assume any confidential cryption (PKE) with security against chosen-plaintext attacks
channel during the execution of the protocol. Formally, a (CPA) into encryption against adaptively chosen-ciphertext
ConBE scheme (ParaGen, CBSetup, CBEncrypt, CBDecrypt) attacks (CCA2) in the standard model. In [48], Canetti et
consists of the following four polynomial-time algorithms. al. suggested conversion from CPA-secure IBE to CCA2-
◆ ParaGen(1λ). This algorithm is used to generate global secure PKE using a one-time signature. In [49], Matsuda and
parameters. It takes as input a security parameter λ and it Hanaoka proposed to obtain a CCA2-secure PKE from any
outputs the system parameters, including the group size n. CPA-secure PKE with a universal computational extractor. In
 4

[50], Liu et al. obtained a CCA2-secure ABE from a CPA- The Corrupt oracle is used to model an attacker who
secure ABE without extra cryptographic primitives, but with compromises some members during the set-up stage to estab-
an additional on-the-fly dummy attribute. We note that these lish the group encryption key. The Reveal oracle is used to
methods are applicable to our ConBE setting with/without capture the decryption key leakage after the ConBE system has
modification (e.g., by adding an on-the-fly dummy receiver). been established. This difference can be used to differentiate
The cost depends on the methods, i.e., a universal compu- the security against attacks during the set-up stage from the
tational extractor, a one-time signature or a dummy user. security against attacks after a ConBE system is deployed.
Hence, it is sufficient to only define the CPA security of We assume that the communication channels between mem-
a ConBE scheme. However, noting that ConBE is designed bers are authenticated during the CBSetup stage to establish
for distributed applications where the users are likely to be the group encryption key. This is to allow each user to
corrupted, we include full collusion resistance into our security validate that the received protocol transcripts are from authen-
definition. tic members. The most usual way to establish authenticated
The fully collusion-resistant security of a ConBE scheme is channels is through a public-key infrastructure (PKI): each
defined by the following security game between a challenger user registers a public key to a certification authority CA and
CH and an attacker . A uses the corresponding private key to sign any message she
◆ Initialization. The challenger CH runs ParaGen with a generates during the CBSetup stage. Hence, the authenticity
security parameter λ and obtains the system parameters. The of the CBSetup transcript from a user can be verified by
system parameters are given to the attacker A. all other users. Note that after this stage has been completed
◆ Queries. Attacker A can make the following queries to and the group encryption key gek has been agreed upon,
challenger CH. messages encrypted under this group key cannot be understood
• Execute. A uses the identities of n members by CA, because the latter does not know the corresponding
1 ,
U ··· U , n to query CH . The challenger runs CBSetup decryption keys. For instance, in a social network application,
( U1(x1), ·, ·n·(xUn)) on behalf of the n members, and the social network operator can serve as the CA and certify the
responds with the group encryption key gek and the users’ public keys used to authenticate communication. In this
transcripts of CBSetup to A. way, the operator is only partially trusted and cannot decrypt
• Corrupt. A sends i to the Corrupt oracle maintained by the encrypted messages subsequently shared among the users
CH , where i ∈ { 1,· · · , n
} . The challengerCH returns under gek.
the private input and inner random coins ofUi during the
execution of CBSetup. III. AN AGGREGATABLE BE S CHEME
• Reveal. A sends i to the Reveal oracle maintained
In this section, we propose an efficient AggBE scheme that
by CH, where i ∈ { 1,· · · , n} . The challenger CH
is essential to construct ConBE schemes.
responds with dki, which is the decryption key of Ui
after execution of CBSetup.
◆ Challenge. At any point, attackerAcan choose a target set A. Definitions of AggBE
S∗ ⊆ 1,{ · · ·, n } to attack, with a constraint that the indices in A BE scheme [42], [1], [44] consists of the following
S∗ have never been queried to the Corrupt oracle or the Re- probabilistic algorithms.
veal oracle. Upon receiving S∗, the challenger randomly
CH ◆ BSetup(1λ). Take as input a security parameter λ. Output
selects ρ ∈ {0, 1} and responds with a challenge ciphertext the maximal size n of a group of broadcast receivers, and a
c∗, where c∗ is obtained from (c∗, ξ) ←CBEncrypt(S, gek) BE public/secret key pair (PK, SK).
if ρ = 1, or c∗ is randomly sampled from the image space of ◆ BKeyGen(i, SK). Take as input an index i ∈ {1,· · · , n}
CBEncrypt if ρ = 0. and the secret key SK. Output a private key di for user i.
◆ Output. Finally, Aoutputs a bit ρJ, its guess of ρ. The ◆ BEncryption(S, PK). Take as input a receiver set S ⊆
adversary wins if ρJ = ρ. {1, · · · , n} and the public key PK. If |S| > n, abort the
We define A ’s advantage Adv security−fc
ConBE,A in winning the protocol. if |S|
Else and
the ciphertext ξ∈≤ Kn,isoutput a pair (c,
the message ξ) where key.
encryption c is called
above fully collusion-resistant security game as
◆ BDecryption(S, i, di, c, PK). This algorithm allows each
security−f c = | Pr[ρ = ρJ ] − 1/2|.
AdvConBE,A receiver to extract the message encryption key ξ from the
Definition 2. An n-party ConBE scheme has adaptive ciphertext. Take as input the receiver set S, the index i ∈
(τ, n, ε)-security against a full-collusion attack if no adversary {1, · · · , n}, the receiver’s secret key di, the ciphertext c and
A can obtain in time at most τ an advantage Advsecurity−fc the public key PK. If |S| ≤ n and i ∈ S, output the message
ConBE, A
at least ε in the above security game. An n -party ConBE encryption key ξ.
scheme has semi-adaptive (τ, n, ε)-security against a full- The security for BE is defined by an experiment between an
if, for any attacker AJ running in time τ , AJ’s
collusion attack security−fc attacker A and a challenger CH. A is given the dealer’s public
advantage Adv is less than ε in the above security key including the system parameters. A can adaptively query
A
ConBE, t
(1) must commit to a set the decryption key of any user. At some point, the attacker
game, with extra constraints that AJ
of indices C ⊆ {1, · · · , n} before the Queries stage, (2) can specifies a challenge set S∗. The constraint is that, for any i ∈
only query Corrupt and Reveal with i ∈ / C and (3) can only S∗, the decryption key of user i has never been queried. The
choose S∗ ⊆ C to query CH in the Challenge stage. challenger sets (c∗, ξ0) ← BEncryption(S∗, PK) and ξ1 ←
 5

K. It sets b ← {0, 1} and gives (c∗, ξb) to A. Finally, A aggregated public key PK = PK 1 ~ · · · ~ PK n . A wins
outputs a guess bit bJ ∈ {0, 1} for b and wins the game if if A outputs a correct1guess bit. Denote A’s advantage by
b = bJ . The adversary A’s advantage in the game above is AdvA = | Pr[win] − |.
1
A,n,N (1 ) = | Pr[b = b ] − 2 |.
defined as AdvBE λ J
(τ, ε, n)-aggregatable if no τ -
A BE scheme is said2 to be
Definition 3 (Adaptive security). We say that a BE scheme time algorithm A has advantage AdvA ≥ ε in the above
aggregatability game.
has adaptive security if, for any polynomial-time algorithm
A, its advantage AdvBE
A,n,N (1 ) is negligible in λ.
λ
B. An AggBE Scheme
In [44], a slightly weaker notion of semi-adaptive security
is defined. In this case, the attacker must commit to a set of Let PairGen be an algorithm that, on input a security
indices C at the beginning of the above game. The attacker parameter 1λ, outputs a tuple Υ = (p, G, GT , e), where G
is allowed to query the decryption key of any user not in and GT have the same prime order p, and e : × G G→ GT is
C, and can choose any S∗ ⊆ C for a challenge ciphertext. an efficient non-degenerate bilinear map such that e(g, g) 1
Gentry and Waters also illustrate a generic transformation for any generator g of G, and for all u, v ∈ Z∗p , it hold-
[44] to convert any semi-adaptively secure BE scheme into s that e(gu, gv) = e(g, g)uv. Let Υ = (p, G, GT , e) ←
an adaptively secure one. PairGen(1λ), g be a generator of G. Let hj ∈ G be
Before formalizing aggregatability, we define a weaker randomly chosen for j = 1, · ·,· n. The system parameters
key homomorphic property for BE schemes. The key ho- are π = (Υ, g, h1· ,· · , hn). Assume n users in the system.
momorphic property was first defined in the static broadcast Our AggBE scheme extends the aggregatable signature-based
encryption scenario by Wu et al. [3]. Recently, Boneh et al. ex- broadcast [3] with user revocation and is constructed as
follows.
tended this concept to the attribute-based encryption scenario
[46]. For our dynamic BE scenario, the key homomorphism ◆ BSetup(1λ ): The dealer randomly chooses Xi ∈ G, ri ∈ Z∗p
states that, by combining the decryption keys associated with and computes Ri = g −ri , Ai = e(Xi , g). The BE public key
the same index of different BE instances, one can obtain a is PK = ((R0, A0), · · · , (Rn, An)) and the BE secret key is
functional decryption key associated with the same index of sk = ((r0, X0), · · · , (rn, Xn)).
the combined BE instances. ◆ BKeyGen(j, SK): For j = 1, · · · , n, the private key of the
user j is dj = (σ0,j, · · · , σj−1,j, σj+1,j, · · · , σn,j):
Definition 4 (Key homomorphism). A BE scheme is said
to be key homomorphic if for any two public/secret key σi,j = Xi hrji .
pairs (PK 1 , SK1), (PK 2 , SK2) ← BSetup(1λ), any index ◆ BEncryption(S, PK): Set S = { 0, 1, · · ·, n}\ S. Randomly
i ∈ S ⊆ 1, { · · ·, n }, any d1,i =BKeyGen(i, SK 1 ) and pick t in Z∗p and compute c = (c1 , c2 ) :
d2,i =BKeyGen(i, SK2 ), it holds that BDecryption(S, i, Y
d1,i © d2,i, c, PK 1 ~ PK 2 )= ξ for any KEM ciphertext c1 = g t , c2 = ( Ri ) t.
BEncryption(S, PK1 ~ PK2), where ~ : Γ Γ×
(c, ξ) ← Γ → i∈S
and © : Ω× Ω →Ω are two efficient operations in the public Set the session key ξ = ( i S∈
Q
A i )t .
Output (c, ξ) and send
key space Γ and the decryption key space Ω, respectively.
(S, c) to receivers.
The key homomorphic property just indicates that the com- ◆ BDecryption(S, j, d j , c, PK): If j ∈ S, the receiver j
bined decryption key works for the combined BE instance. It extracts ξ from c with private key dj by computing
does not exclude the possibility that valid decryption keys for Y
the combined BE instance might be obtained in other ways; e( σi,j, c1)e(hj , c2) = ξ.
in contrast, aggregatability excludes this possibility. A BE i∈S
scheme is aggregatable if n instances of the BE scheme can be The correctness of the BE scheme above follows from direct
aggregated into a new BE instance secure against an attacker verification of the following equalities
accessing some decryption keys of each instance, provided Y
that the i-th decryption key corresponding to the i-th instance e( σi,j , c1 )e(hj , c2 )
is unknown to the attacker for i = 1,· · ·, n. Formally, this i∈S
property is defined as follows. Y Y
= e( Xi hrji , g t )e(hj , g −ri t )
Definition 5 (Aggregatability). Consider the following game i∈S i∈S
Y Y
between an adversary A and a challenger CH: = e( Xi , g)t = ( Ai )t = ξ.
◆ Setup: A initializes the game with an integer n. CH replies i∈S i∈S
with (π, PK 1 , · · · , PK n ), that is, the system parameters and The security of our BE scheme relies on the well-established
the n independent public keys of the BE scheme.
decision n-BDHE assumption [47].
◆ Corruption: For 1 ≤ i, j ≤ n, where i j, the adversary Definition 6 (Decision n-BDHE Assumption). Let G be a
A is allowed to know the decryption keys dkj,i corresponding
to index j with respect to the public key PK i . bilinear group of prime order p as defined above, g a generator
◆ Challenge: CH and A run a standard Ind-CPA (indistin- of G, and h = g t for some unknown t ∈ Z∗p . Denote → −
y g,α,n =
(g1, · · · , gn , gn+2 , · · · , g2n ) ∈ G2n−1, where gi = g α for
i
guishability under chosen-plaintext attack) game under the
 6

some unknown α ∈ Z∗p . We say that an algorithm B that A. High-Level Description

outputs b ∈ {0, 1}has advantage ε in solving the decision n-
BDHE assumption if |Pr[ B (g, h, → − Our basic idea is to introduce the revocation mechanism of
y g,α,n , e(gn+1 , h)) = 0] − a regular BE scheme into the asymmetric GKA scheme [3]. To
→
−
Pr[B (g, h, y g,α,n , Z) = 0)] | ≥ ε, where the probability this end, each member acts as the dealer of the aggregatable
is over the random choice of g in G, the random choice t, α BE scheme above. The k-th user publishes PK k and dj,k,
Z∗p , ∈
the random choice of Z GT∈, and the random bits where dj,k is the decryption key of PK k corresponding to
consumed by . We B say that the decision (τ, ε, n)-BDHE the index j ∈ {1, · · · , n} \ {k}. Then the negotiated public
assumption holds in G if no τ -time algorithm has advantage key is PK = PK 0 ~ · · · ~ PK n . Each member j can
at least ε in solving the decision n-BDHE assumption. compute the decryption key dkj = dkj,j ©n dkj,k.
Observe that dk k=1,k j
According to the BE security definition in [44], our scheme j,j has never been published. Due to the
is fully collusion-resistant under the decision n-BDHE as- key homomorphism of the BE scheme above, dkj is a valid
sumption. The proof is given in Section VI-A. One can further decryption key corresponding to PK. Hence, anyone knowing
apply the generic Gentry-Waters transformation [44] to convert PK can encrypt to any subset of the members and the intended
our semi-adaptive BE scheme into an adaptively secure one. receivers can decrypt. To guarantee the security of the resulting
ConBE scheme, we also need to show that only the intended
Theorem 1. The proposed BE scheme for dynamic groups receivers can decrypt. This is ensured by the aggregatabilty of
has full collusion resistance against semi-adaptive attacks the underlying BE scheme.
in the standard model if the decision n-BDHE assumption
holds. More formally, if there exists a semi-adaptive attacker
A breaking our scheme with advantage ε in time τ , then there B. The Proposal
exists an algorithmB breaking the n-BDHE assumption with Based on our aggregatable BE scheme, we implement a
advantage ε in time τ J = τ + O (n2 )τExp , where τExp is the ConBE scheme with short ciphertexts. Assume that the group
time to compute an exponentiation in G or GT . size is at most n. Let Υ = (p, G, GT , e) ← PairGen(1λ),
One may observe that our BE scheme is key-homomorphic. and g, h1, · · · , hn be independent generators of G. The system
Consider the system parameters defined as above. Let PK1 = parameters are π = (λ, n, Υ, g, h1, · · · , hn).
◆ Setup. The set-up of a ConBE system consists of the
((R0,1, A0,1), · · · ,(Rn,1, An,1)) and PK2 = ((R0,2, A0,2), following three procedures:
· · · , (Rn,2, An,2)) be the respective public keys of two random
instances of the above BE scheme, and for j = 1, · · · , n, let • Group Key Agreement. For 1 ≤ k ≤ n, member k does
dj,1 = (σ0,j,1 , · · · , σj−1,j,1 , σj+1,j,1 , · · · , σn,j,1 ) ∈ Gn and the following:
dj,2 = (σ0,j,2 , · · · , σj−1,j,2 , σj+1,j,2 , · · · , σn,j,2 ) ∈ Gn be – Randomly choose X i,k ∈ G, ri,k ∈ Z∗p ;
the respective decryption keys corresponding to index j under – Compute Ri,k = g −ri,k , Ai,k = e(Xi,k , g);
PK1 and PK2. Define PK = PK1 ~ PK2 = ((R0,1R0,2, – Set PKk = ((R0,k, A0,k), · · · , (Rn,k, An,k));
A0,1 A0,2 ), · · · , (Rn,1 Rn,2 , An,1 An,2 )) and dkj = dj,1 © dj,2 – For j = 1, · · · , n, j k, compute σi,j,k =
= (σ0,j,1σ0,j,2, · ,· · σj−1,j,1σj−1,j,2, σj+1,j,1σj+1,j,2, · · · , Xi,khjri,k for i = 0, · · · , n, with i ƒ= j;
σn,j,1σn,j,2). Then PK is the public key of a new instance – Set dj,k = (σ0,j,k , · · · , σj−1,j,k , σj+1,j,k , · · · , σn,j,k );
of the above BE scheme and dkj is the new decryption key – Publish (PK k , d1,k, · · · , dk−1,k, dk+1,k, · · · , dn,k);
corresponding to the index j. This fact can be directly verified. – Compute dk,k accordingly and keep it secret.
Indeed, the following theorem shows that our BE scheme
• Group Encryption Key Derivation. The group encryp-
enjoys the stronger notion of aggregatability. tion key is
Theorem 2. If there exists an attacker A who wins the
aggregatability game with advantage ε in time τ , then there PK = PK ~0 · · · ~ PK n = ((R 0, A 0), · · · , (R
n , nA ))
Qn Qn
exists an algorithm B breaking the n-BDHE assumption with where Ri = Ri,k, Ai = Ai,k for i =
advantage ε in time τ J = τ + O((n3 )τExp ). 0, · · · , n k=1 k=1 is publicly
For the proof of the previous theorem, we refer to The- . The group encryption key PK
computable.
orem 3 where we prove a stronger property in the sense • Member Decryption Key Derivation: For 0 ≤ i ≤ n,
that the attacker is additionally allowed to know the internal 1 ≤ j ≤ n and i =ƒ j, member j can compute her
randomness used to compute dkj,i corresponding some PK i decryption key
for 1 ≤ i, j ≤ n where i ƒ= j.
dj = (σ0,j, · · · , σj−1,j, σj+1,j, · · · , σn,j)
where
IV. P ROPOSED C ON BE S CHEME n n nY
Y Y ri,k
In this section, we propose a ConBE based on the above σi,j = σi,j,j σi,j,k = σi,j,k = Xi,kjh .
k=1,kƒ= k=1 k=1
aggregatable BE scheme. The basic construction has short j
ciphertexts and long protocol transcripts. Then we show an ◆ CBEncrypt. Assume that a sender (not necessarily a group
efficient trade-off between ciphertexts and protocol transcripts. member) wants to send to receivers in S ⊆ {1, · · · , n} a
 7

session key ξ. Set S ={ 0, 1, · · ·, n} \ S. Randomly pick t = e(g, g)xt = ξ.

in Z∗p and compute the ciphertext c = (c1 , c2 ) where
Y We define ©, ~, § as s1i © s2i = (s 1i,0 s2i,0 , · · · ,
c1 = g t , c 2 = ( Ri)t. s1 i,n s2 i,n ), PK1 ~ PK2 = PK1PK2, k1 § k2 = k1k2,
i∈S respectively. Then it is easy to verify that the Gentry-Waters
Q BE scheme is key-homomorphic.
Output (c, ξ) where ξ = ( i ∈S Ai)t. Send (S, c) to the 2) Analog of Our ConBE Using the Gentry-Waters BE
receivers.
Scheme: Following the same paradigm, it is easy to give an
◆ CBDecrypt. If j ∈ S, receiver j can extract ξ from the
ciphertext c with decryption key dj by computing analog of our ConBE scheme by using the Gentry-Waters BE
Y scheme. Assume the same system parameters as above. The
e( σi,j, c1)e(hj, c2) = ξ. analog of the ConBE can work as follows.
i∈S
◆ CBSetup. This algorithm consists of the following proce-
dures.
The correctness of the scheme directly follows from the
fact that the underlying BE scheme is correct and key- • Group Key Agreement. For 1 ≤ k ≤ n, user k randomly
homomorphic. As to security, we have the following theorem, chooses xk ∈ Z∗p and computes P Kk = e(g, g)xk and
whose proof is given in Section VI-B. di,k = (si,0,k, si,1,k, · · · , si,k−1,k, si,k,k,
Theorem 3. The proposed ConBE scheme has fully collusion- si,k+1,k, · · · , si,n,k), (1)
resistant security against semi-adaptive attacks in the stan-
dard model if the decision n-BDHE assumption holds. More where
r r
formally, if there exists a semi-adaptive attacker A breaking si,0,k = g −ri,k , si,1,k = h i,k , · · · , si,k−1,k = h i,k ,
our scheme with advantage ε in time τ , then there exists an 1 k−1
algorithm B breaking the n-BDHE assumption with advantage s = gxk hri,k , s = hri,k , · · · , s ri,k
i,k,k k i,k+1,k k+1 i,n,k = hn
ε in time τ J = τ + O((n3 )τ Exp).
for randomly chosen ri,k from Z∗p . User k’s private key
C. Insecure Analog of ConBE Using Gentry-Waters BE is dk,k. User k publicly broadcasts
The above BE scheme bears some similarities to the Gentry- (PK k , d1,k, · · · , dk−1,k, dk+1,k, · · · , dn,k) (2)
Waters BE scheme [44]. However, our BE scheme is aggregat-
• Group Encryption Key Derivation. Anyone can com-
able while the Gentry-Waters BE scheme is not. In this section,
pute the group encryption key:
with the Gentry-Waters BE scheme as an example, we show
that an analog of our ConBE scheme is insecure due to the K = P K1 · · · P Kn = e(g, g)x1 +···+xn = e(g, g)x ,
lack of aggregatability of the Gentry-Waters BE scheme.
1) Review of the Gentry-Waters BE Scheme: Gentry and where we define x = x1 + · · · + xn.
Waters presented a semi-adaptively secure BE scheme [44]. • Member Decryption Key Derivation. For i = 1, · · · , n,
Let h1, · ·, ·hn and g be independent generators of a group G user i can compute her decryption key
equipped with a bilinear map e. Assume that the order of G
is a prime p. The Gentry-Waters BE scheme is as follows. di = (si,0, si,1, · · · , si,i−1, si,i, si,i+1, · · · , si,n),
◆ BSetup(n, n): Randomly select x in Z∗p and compute where
gx, e(g, g)x. The BE public key is PK = e(g, g)x and the n n
Y Y
BE secret key is SK = g x . si,0 = si,0,k , · · · , si,n = si,n,k.
◆ BKeyGen(i, SK): Run ri ← Z∗p and output user i’s secret k=1 k=1
decryption key si = (si,0, · · · , si,n) where Define ri = ri,1 + · · · + ri,n for 1 ≤ i ≤ n. Then we
si,0 = g −ri , si,1 = hri , · · · , si,i−1 = hri , have that
1 i−1

si,i = g x hri , si,i

i +1 = hri , · · · si,n
i+1 = h ri .
n si,0 = g −ri , s i,1 = hr1i , · · · , s i,i−1 = hri−1,
i

◆ BEnc(S, P K): Randomly pick t in Z∗p and compute c = si,i = g x hri , si,i+1 = hri , · · · , si,n = hri .
i i+1 n
(c1, c2) where Y
c1 = g t , c2 = ( h j ) t . ◆ CBEncrypt. Decide the receiver set S⊆ {1,· · ·, n} . Invoke
j∈S the underlying Gentry-Waters encryption algorithm to compute
the ciphertext c = (c1, c2):
Set ξ = e(g, g)xt and output (c, k). Send (S, c) to the receivers.
Y
◆ BDec(S, i, si, c, PK): If i ∈ S, the receiver i extracts ξ c1 = g t , c2 = ( h j )t
from c with private key di by computing j∈S
Y Y
e(si,i si,j , c1 )e(si,0 , c2 ) = e( si,j , c1 )e(si,0 , c2 ) where t is randomly chosen from Z∗p . Set
j∈S\{i} j∈S t t(x +···+x ) tx
Y Y ξ = K = e(g, g) 1 n
= e(g, g)
= e((gx hri ), g t )e(g −ri , ( hj)t)
j
j∈S j∈S and send (S, c) to the receivers.
 8

◆ CBDecrypt. If i ∈ S, the user i can extract ξ from c with relationship with the decrypted value e(g, g)xt by the intended
t
her decryption key di by computing receivers. Hence, the value e(g, g)x t extracted by the attackers
Y Y
can be viewed as a shadow of the original value e(g, g)xt.
e(si,i si,j, c1)e(si,0, c2) = e( si,j, c1)e(si,0, c2) The above shadow property of the Gentry-Waters BE
j∈S\{i} j ∈S
scheme does not affect the security of their proposal as a
Y Y
= e((g x hrji ), g t )e(g −ri , ( hj )t ) = e(g, g)xt = ξ. regular BE scheme. However, this property may prevent the
Gentry-Waters BE scheme from being used as a building block
j∈S j∈S for certain advanced protocols.
3) Attack on the Analog: In the sequel we show that the
above Gentry-Waters BE-based ConBE scheme is insecure. An
explicit attack is presented to allow an attacker to decrypt any V. P ERFORMANCE ANALYSIS
ciphertext encrypted to any subset of the group members. The A. Theoretical Analysis
attacker only needs to see the public key of the users and the We first examine the online complexity that is critical for
ciphertext, both of which are transmitted over public channels. the practicality of a ConBE scheme. When evaluating the per-
The attack proceeds as follows. formance, we use the widely adopted metrics [42], [43], [44]
Seeing the public protocol transcripts (Formula (2)) for regular BE schemes. In these metrics, the costs of simple
(PK k , d1,k, · · · , dk−1,k, dk+1,k, · · · , dn,k) from users k = operations (e.g., read the indices of receivers and perform some
1, · · · , n, the attacker can know (from Formula (1)): simple quantifications of group elements associated to these
r r
si,0,k = g −ri,k , si,1,k = h i,k , · · · , si,k−1,k = h i,k , indices) and communication (e.g., the binary representation of
1 k−1
ri,k
the receivers’ set) are not taken into consideration. After the
si,k,k = gxk hri,k , s
k i,k+1,k = hk+1, · · · , si,n,k = hn
ri,k CBSetup procedure, a sender needs to retrieve and store the
for i = 1, · · · , n, iQƒ= k. The attacker also knows the ciphertext group public key PK consisting of n elements in G and n
elements in GT . Moreover, for encryption, the sender needs
(c1, c2) = (gt, ( j∈S hj)t). For each k = 1, · · · , n, the
attacker can compute only two exponentiations and the ciphertext merely contains
Y two elements in G. This is about n times more efficient
ξk = e( si,j,k, c1)e(si,0,k, c2) than the trivial solution. At the receiver’s side, in addition
j∈S to the description of the bilinear pair which may be shared by
Y Y many other security applications, a receiver needs to store n
= e(g xk ( hj )ri,k , g t )e(g −ri,k , ( hj )t ) elements in G for decryption. For decryption, a receiver needs
j∈S j∈S to compute two single-base bilinear pairings (or one double-
= e(g, g)xk t. base bilinear pairing). The online costs on the sides of both
the sender and the receivers are really low.
Then the attacker can decrypt the ciphertext by computing of the CBSetup
n n to We next
set up discuss system.
a ConBE the complexity
The overhead procedure
incurred by this pro-
Y Y
ξk = e(g, g)xk t = e(g, g)(x1 +···+xn )t = ξ. cedure is O(n2). This procedure needs to be run only once and
k=1 k=1 this can be done offline before the online transmission of secret
The attacker obtains the secret session key if he knows session keys. For instance, in the social networks example, a
the public transcripts of the CBSetup sub-protocol and the number of friends exchange their CBSetup transcripts and
ciphertext. Hence, the construction based on the Gentry-Waters establish a ConBE system to secure their subsequent sharing
BE scheme is insecure. of private picture/videos. Since ConBE allows revoking mem-
We observe that the above attack roots in a specific property bers, the members do not need to reassemble for a new run
(which we call shadow property) of the Gentry-Waters BE of the CBSetup procedure until some new friends join. From
scheme. Suppose that there are two instances sharing the sys- our personal experience, the group lifetime usually lasts from
tem parameters of the Gentry-Waters BE scheme. Their public weeks to months. These observations imply that our protocol
t
keys are P K = e(g, g)x and P K J = e(g, g)x , respectively. is practical in the real world.
Assume that a user indexed by i in the first instance has Furthermore, if the initial group is too large, an efficient
secret decryption key si computed from secret value ri and trade-off can be employed [42] to balance the online and
the master secret key x corresponding to P K = e(g, g)x, offline costs. Suppose that n is a cube, i.e., n = n13, and the
and a user also indexed by i (the users identified by the initial group has n members. We divide the full group into n12
same index in two BE instances can be different or not) in subgroups, each of which has n1 members. By applying our
another instance has secret decryption key sJi computed from basic ConBE to each subgroup, we obtain a ConBE scheme
secret value rJi and the master secret key xJ corresponding to with O(n21)-size transcripts per member during the offline
J tx 2
PK = e(g, g) , as defined in the Gentry-Waters BE scheme. stage of group key establishment; a sender needs to do O(n1)
Q
Let (c1, c2) = (gt, ( j S h∈j)t) be the ciphertext sent to a encryption operations of the basic ConBE scheme, which
receiver group S in the first instance. Then any receiver inxt produces O(n21)-size ciphertexts. Consequently,
2
we obtain a
S in the first instance can decrypt the session key e(g, g) . semi-adaptive ConBE scheme with O(n 3 ) complexity. This
However, a user with the same index in S in the second is comparable to up-to-date public-key BE systems whose
t 1
instance can extract a value e(g, g)x t which has a meaningful complexity is O(n 2 ).
 9

120
100 GK Agreement AES-80 level GEKD AES-80 level CBEncrypt AES-80 level
GK Agreement AES-128 level 2 MDKD AES-80 level 100 CBDecrypt AES-80 level
80 GEKD AES-128 level CBEcrypt AES-128 level

Execution time (ms)

Execution time (s)

Execution time (s)

MDKD AES-128 level 80 CBDecrypt AES-128 level
1.5
60
60
1
40
40
20 0.5
20
0 0
0
0 50 100 150 0 50 100 150 0 50 100 150
n n n
Fig. 1. Execution time of Group Key Agreement, Group Encryption Key Derivation, Member Decryption Key Derivation, CBEncrypt, and CBDecrypt for
AES-80 and AES-128 levels.

B. Experimental Analysis once and then one can broadcast to any subset of the users,
In this section we present experimental results on our without re-running the protocol or any extra revocation sub-
ConBE scheme. The experiments were run on a PC with Intel protocol.
Core i7-2600 CPU at 3.4GHz, using the C programming lan- The central graph in Figure 1 shows the time to extract
guage. The cryptographic operations were implemented using the group encryption key and the decryption key for different
the Pairing-Based Cryptography library2. Following the NIST- group sizes and different security levels. Similarly to the
2012 key size recommendation3, we realized our protocol for group key agreement time, the key extraction time also grows
a moderate AES-80 level and a more usual AES-128 level, with the security level and the group size. However, even in
corresponding to the security level of an ideal symmetric the worst case, only about 3 seconds are required, which is
cipher with 80-bit and 128-bit secret keys, respectively. We affordable in practice.
used Type A pairings constructed on the curve y2 = x3 + x The rightmost graph in Figure 1 illustrates the online session
with embedding degree 2. Accordingly, in the first case for key encryption/decryption time. It can be seen that the time is
AES-80 level, G has 512-bit elements of a 160-bit prime almost constant for different group sizes, which is consistent
order and GT has 1024-bit/128-byte elements; and in the with the theoretical analysis. Both the session key encryption
second case for AES-128 level, G has 1536-bit elements of a and decryption take less than 10ms for a 80-bit security level,
256-bit prime order and GT has 3072-bit/386-byte elements, and less than 80ms for a 128-bit security level. After the
respectively. system is set up, the session key transmission is really efficient,
We performed experiments on the offline procedures in- which is user-friendly and definitely makes our ConBE scheme
cluding Group Key Agreement, Group Encryption Key practical.
Derivation and Member Decryption Key Derivation, and We also performed experiments on cost tradeoff between
the online procedures including CBEncrypt andCBDecrypt set-up and online encryption. For n = 180 and AES-128 level,
for different group sizes n = 6, 30, 60, 90, 120, 150, 180. The the execution times for Group Key Agreement, Group En-
values for CBEncrypt and CBDecrypt consider the worst cryption Key Derivation, Member Decryption Key Derivation,
case, i.e., |S| = 1. Also, we did not optimize the underlying CBEncrypt and CBDecrypt are 101s, 2.20s, 1.86s, 55.3ms, and
pairing-related parameters or operations, e.g., by choosing a 57.6ms, respectively. However, using the trade-off described
large prime characteristic of the base field and the prime order in the previous section, specifically taking subgroups of 6
p with most bits 0 (or 1), and by accelerating multi-base users, the times become 410ms, 2.05ms, 1.63ms, 1.33s, and
exponentiations/multi-base pairings [51]. Hence, the practical 57.6ms. The set-up efficiency was significantly improved, at
performance of our protocol can be better than the illustrated the cost of a 1.33s encryption time, to be compared to a 55.3ms
experimental results. encryption time without tradeoff.
In Figure 1, the security level of our protocol is measured by
the secret key size of AES (assumed to be an ideal symmetric
VI. S ECURITY P ROOFS
cipher), i.e., AES with a truncated 80-bit key and AES with
a standard 128-bit key. The leftmost graph in the figure illus- A. Proof of Theorem 1
trates the group key agreement time for different group sizes
and different security levels. The execution time grows almost Proof: A semi-adaptive attacker must commit to a set
quadratically with the group size, and also grows with the of the group members at the beginning of the game. She is
allowed to corrupt all the users outside the committed set.
security level. This is consistent with our theoretical analysis,
Finally, she can choose any subset of the committed set as a
because the pairings and the exponentiations dominate the
target set to attack and try to get useful information sent to
computation costs. To achieve a moderate 128-bit security, the
the target group. Suppose thatA is a semi-adaptive τ -time
execution time is about 3 minutes for a group of 180 users.
This is realistic as the GKA procedure only needs to be run adversary breaking our BE scheme with advantage ε for a
system parameterized with a given n. We build an algorithm
2Version 0.5.12, available at http://crypto.stanford.edu/pbc. B with advantage ε in solving the decision n-BDHE problem
in time τ J .
3http://www.keylength.com/en/4/.
 10

A commits to a set C ⊆ { 1,· · · , n} to B . B queries For the case i ∈ C and j =ƒi, from Equation (4), the
the decision n-BDHE challenger and obtains a random deci- following equations hold.
sion n-BDHE challenge (g, g t , → −
y g,α,n , Z), where →
−y g,α,n =
(g1, · · · , gn n+2 , · · · , g2n ) = (g , · · · , g , g
, g α
1
α
n
α
n+2
, · · ·, e(σi,j,ag)e(h j, Ri )
2n
= e(g i g −ri g R−vj , g)e(g g vj , R )
gα ) and Z is either e(g n+1 , gt) or a random element of j n+1−i+j i j i
GT . B proceeds as follows. = e(g ai g −ri gn
j +1−i+j , g)e(gj , Ri )
Preparation for simulation. = e(g ai g −ri gn+1−i+j , g)e(gj , g ri g −1 )
j n+1−i
For j = 1, · · · , n, B randomly selects vj ∈ Z∗p and −1
computes hj = gj g vj . Denote C = {1, · · · , n} \ C. = e(g ai gn+1−i+j , g)e(gj, gn+1−i )
For i ∈ C ∪ {0}, randomly select ai , ri ∈ Z∗p . For j ∈ C, = e(g ai gn+1−i+j , g)e(g, g −1n+1−i+j )
compute = e(g, g)ai = Ai . (7)
Y For the case that i ∈ C and j ∈ {1,· · · ,n }, from Equation
gn+1−k ), A0 = e(g, g)a0+α
n+1
R 0 = g r0 ( ,
(5), the following equation holds.
k∈C
e(σi,j, g)e(hj, Ri)
kƒ=j
Y )R −vj . (3) a −r r
σ0,j = ga0 gj−r0 ( g−1 0 = e(g haji i , g)e(hj, g i )
k∈C n+1−k+j
i
= e(g, g) = Ai . (8)
For i ∈ C and j ƒ= i, compute Hence, for j ∈ C, i = 0, · · · , n and i ƒ= j, we have that
Ri = g ri g −1 e(σi,j, g)e(hj, Ri) = Ai. (9)
n+1−i
, Ai = e(g, g)ai ,

σi,j = g ai g j−ri gn+1−i+j R i

−vj
. (4) Since g is a generator of G, there exist X i ∈ G and γi ∈ Z∗p
satisfying e(Xi , g) = Ai and Ri = g −γi . The above Equation
For i ∈ C and j ∈ {1, · · · , n}, compute (9) further implies that σi,j = Xi hγji . Therefore, for user j ∈
r a a −r C = {1, · · · , n} \ C, her decryption key (σ0,j, · · · , σj−1,j,
Ri = g i , Ai = e(g, g) i , σi,j = g i hj i . (5) σj+1,j, · · · , σn,j) is well formed. The simulation of decryption
keys for users outside C is perfect.
Then B can answer all the queries from A. Query challenge ciphertext. At some point, the attacker A
Query public key.A can query the BE public key as well submits a target set S∗ ⊆ C ⊆ { 1,· · · , n} for a challenge
as the system parameters π = ((p, G, GT , e), g, h·1·,· , hn) ciphertext sent to S∗. Since S∗ ⊆ C, we have that S∗ =
∗
and the maximum group size n. From the decision n-BDHE { 0, 1, · · ·, n} \ S ⊇ { 0, 1,· · · , n} \ C = C ∪ {0 }. Notice that
challenge, the simulation of π is straightforward. B needs to B knows Z and gt from the decision n-BDHE challenger,
generate a BE public key PK = (pk0, pk1,· · · , pkn), where and the values of ri , ai ∈ Z∗p which are chosen during the
pki is the public key of the underlying aggregatable signature- preparation for the simulation for i =·1, · · , n. Hence B can
based broadcast [3]. B sets pki = (Ri, Ai) and forwards them compute
to A. Note that ri and ai are uniformly distributed in Z∗p , so Σ
ri
Σ
ai
the simulated public keys have an identical distribution as in c∗1 = g t , c∗2 = (g t ) i∈S∗ , ξ ∗ = Ze(g t , g) i∈S∗ . (10)
the real world, and the simulation is perfect. The algorithm B sets c∗ = (c∗1 , c∗2 ) and challenges A with
Query decryption key. A can query the decryption key of any (c∗ , ξ ∗ ). In the following we show that (c∗ , ξ ∗ ) is well formed.
user j ∈ C = { 1,· · · , n} \ C.B returns (σ0,j,· · · , σj−1,j, Define SJ = S∗ \ {C ∪ {0 }}. Then SJ ⊆ C and S∗ = C ∪
σj+1,j, ,·σ· n,j
· ). Now we show that the simulated decryption { } ∪ SJ . From Equations (3, 4, 5), the following equations
0
keys are well formed and perfect. hold:
Y Y Y
For the case that i = 0 and j ∈ C, from Equation (3), the ( Ri)t = (
Y
R i )t
Ri)t = (R0 Ri
following equations hold.
i∈S∗ i∈C∪{0}∪St i∈C i∈St
Y Y Y
e(σ0,j, g)e(hj, R0) gn+1−k ) g ri g −1
= (g r0 (
n+1−i
g ri )t
kYj k∈C i∈C i∈St
Y Y Σ
= e(ga0 g−r0 ( g−1 )R−vj , g)e(gj g vj , R0 ) r r r t r t

k
i∈St i∈S∗ i )
j n+1−k+j 0 = (g 0
g i g i ) = (g
i∈C
Σ
k∈C
Y = (gt)
), g)e(g , gr0 ( g )) = c 2; (11)
i∈S∗ ri
j
Y
= e(ga0 g−r0 ( g −1
 11

Y Y

j n+1−k+j j n+1−k
0
Y Σ
( Ai)t t i∈S∗ a
tαn+1

= e(g, g) e(g, g) i
. (12)
k∈C k∈C

kƒ=j

k∈C
n+1−k+j
= e(ga0 ( g −1
 12

a well-formed ciphertext of the session

), g)e(g, ( gn+1 −k+j)) i∈S∗

k∈C Hence, (c∗1 , c∗2 ) is

13
 14

) = e(g, g)a0+α
n+1 n+1
=A . (6) key ξ if Z = e(g, g)tα . Else if Z is chosen at random
 15

from GT , (c∗1 , c∗2 ) is also well formed but independent of Case 1.1.2: k k∗ and k ∈ C. Randomly select
ξ. Therefore, B can answer the decision n-BDHE challenge ∗
a0,k , γ0,k ∈ Zp and compute
that Z = e(g, g)tα if and only if A answers that c∗ is a R0,k = gγ0,k g−1 , A0,k = e(g, g)a0,k ,
n+1

ciphertext of ξ. Algorithm B has the same success probability n+1−k

−γ0,k −vj
as A to break the above BE scheme. σ0,j,k = g a0,k g (gn+1−k+j )R ,j k.
j 0,k
Time complexity: B’s overhead is dominated by computing
hj and (σi,j, Ri, Ai) for j ƒ= i. Computing hj requires O(n) In this case, one can verify that for j k, k ƒ= k∗ ∈ C
exponentiations in G. Computing σi,j requires O(n2) expo- e(σ0,j,k )e(hj, R 0,k ) = e(g, g)a0,k = A0,k . (15)
nentiations in G. Computing Ri requires O(n) exponentiations
in G. B can compute Ai by O(n) exponentiations in GT . Let Case 1.2: i = 1, · · · , n
τExp denote the time to compute one exponentiation in G or Case 1.2.1: i ∈ C and k = k∗. Randomly select
GT . The time complexity of B is τ J = τ + O(n2 )τExp . ai,k , γi,k ∈ Z∗p and compute
Ri,k = g γi,k g −1 , Ai,k = e(g, g)ai,k ,
B. Proof of Theorem 3 n+1−i
−γi,k −v
σi,j,k = g ai,k g gn+1−i+j R j , j i.
j i,k
Proof: Suppose that A is a semi-adaptive τ -time ad-
versary breaking our ConBE scheme with advantage ε for In this case, one can verify that
a system parameterized with n. We build an algorithm B e(σi,j,k , g)e(hj , Ri,k ) = e(g, g)ai,k = Ai,k , j i. (16)
with advantage ε in solving the decision n-BDHE problem
in time τ J . Case 1.2.2: i ∈ C or k ƒ= k∗. Randomly select ai,k, γi,k ∈
A commits to a set C ⊆ {1, · · · , n} to B. B queries the Z∗p and compute
decision n-BDHE challenger and obtains a random decision −γi,k
n-BDHE challenge (g, g t , →
−
y g,α,n , Z), where Ri,k = g γi,k , Ai,k = e(g, g)ai,k , σ i,j,k = g ai,k gj .
−
→y = (g , · · · , g , g , · · · , g )
In this case, one can verify that
g,α,n 1 n n+2 2n
1
= (gα , · · · , αgn , gα , · · · , gα )
n+2 2n
e(σi,j,k , g)e(hj , Ri,k ) = e(g, g)ai,k = Ai,k , j ƒ= i. (17)
and Z is either e(gn+1, gt) or a random element of GT . Denote By summarizing Equations (13, 14, 15, 16, 17), we have
the following equations:
C = 1,{ ,·n· ·C. proceeds
}\ B as follows.
Preparation for simulation. For the sake of clarity, we let
B first prepare for all the answers of various possible queries e(σi,j,k , g)e(hj , Ri,k ) = e(g, g)ai,k = Ai,k , k ∈ C; (18)
that the attacker A may query. Assuming the same parameter
setting as in the proof of Theorem 1, B prepares the answers
e(σ0,j,k∗ )e(hj, R0,k∗ ) = e(g, g) a0,k∗ e(g, g) α
n+1

as follows.
For j = 1, · · · , n, compute hj = gj g vj where vj is chosen = A0,k∗ , j ƒ= k∗ ∈ C; (19)
at random in Z∗p .
Case 0: k ∈ C. In this case, B does as in the real scheme. B e(σi,j,k , g)e(hj , Ri,k ) = e(g, g)ai,k
randomly selects ai,k , γi,k ∈ Z∗p and computes = Ai,k, j k, k ∈ C, k ƒ= k∗, j ƒ= i. (20)

Ri,k = g γi,k , Ai,k = e(g, g)ai,k , σi,j,k = g ai,k h−γji,k . After the preparation above,Bcan answer all the queries
from A .
In this case, we have that Query transcript.A can query the system parameters and
e(σi,j,k , g)e(hj , Ri,k ) = e(g, g)ai,k = Ai,k . (13) the transcripts from all the group members participating in the
CBSetup sub-protocol. The system parameters except hj can
Case 1: k ∈ C. be trivially simulated from the decision n-BDHE challenge. As
Case 1.1: i = 0. B randomly selects k∗ ∈ C and sets in the preparation for simulation, hj = gj g vj for a randomly
Ck∗ = {1,· · · , n} \ { k∗} . chosen value vj ∈ Z∗p . Hence, all the system parameters
Case 1.1.1: k = k ∗ . Randomly select a0,k∗ , γ0,k∗ ∈ Z∗p are correctly simulated. Upon receiving the query for the
and compute transcripts from the members, B responds with
Y a ∗ αn+1
R0,k∗ = g γ0,k∗ ( gn+1−A ), A0,k∗ = e(g, g) 0,k e(g, g) , M = {(σi,j,k, Ri,k, Ai,k)|0 ≤ i ≤ n, 1 ≤ j ≤ n,
A∈Ck∗ 1 ≤ k ≤ n, j ƒ= i, j k}.
Aƒ=
jY
a0,k∗ −γi,k∗ −1 −vj ∗ Due to Equations (18, 19, 20), one can see that transcripts
σ0,j,k∗ = g gj ( gn+1−A+j )R0,k∗ , j ƒ= k . in M are well formed. Furthermore, since γi,k and ai,k are
A∈Ck∗ uniformly distributed in Z∗p , the simulated transcripts have an
In this case, one can verify that for j k∗ ∈ C identical distribution as in the real world and the simulation
n+1 is perfect.
e(σ0,j,k∗ , g)e(hj, R0,k∗ ) = e(g, g)a0,k∗ e(g, g)α Query secret inputs and internal states. A can query the
= A0,k∗ . (14) secret inputs and internal states of members in {1, · · · , n} \
 16

C = C. For these members, their transcripts are generated as Success probability. At some point, answers A whether (c∗1 , c∗2 )
in the real scheme in Case 0. Hence,B can answer this query is a valid ciphertext for ξ or is independent of ξ ∗ . From
∗
correctly.
Query decryption keys. Note that in our ConBE one can Equations (18, 19, 20), we have that
Q
always compute the decryption key of a member if one knows ( i∈S Q i∈SQ ∗ k=1 Ai,k)
n t
∗ A i) t = (
Σ n
n+1 Σ i∈S∗ k=1 ai,k )t = e(g, g)tα +at
n+1
the member’s secret inputs and internal states during the = (e(g, g)α + .
CBSetup stage. Hence, the challenger B can handle these
queries as those for secret inputs and internal states. Note that ξ∗ = Ze(g, g)at. Hence, (c1, c2) is a valid ciphertext
n+1

Query challenge ciphertext. In the test stage, the attacker A for the session key ξ∗ if and only if Z = e(g, g)tα .
Then Banswers the decision n-BDHE challenger with Z =
submits a target set S∗ ⊆ C ⊆ { 1,· · · , n} for a challenge
e(g, g)tα if and only if Aanswers that c∗ is a valid
n+1

ciphertext sent to S∗.

Similarly to the proof of Theorem 1, since S∗ ⊆ C, it ciphertext for ξ ∗ . Clearly,B has the same success probability
as the success probability of A breaking the above ConBE
follows that JS∗ = ∗{0, 1, · · · , n}\S∗ ⊇ {0, 1, · ∗· · , n}\C = C∪
{0}. Then S = S \{C∪{0}} ⊆ C. Hence, S = C∪{0}∪SJ . scheme.

n n
Define Σ Σ γi,k = r and Σ Time-complexity: B’s overhead is dominated by computing
Σ ai,k = a
(σi,j,k, Ri,k, Ai,k) for j i, j ƒ= k. Computing σi,j,k requires
i∈S∗ k=1 i∈S∗ k=1
3
which
B. are known
Since B Balso to B because
Z and γ i,k and ai,k are chosen by
g from the
t decisionasn-BDHE O(n ) exponentiations.
ponentiations. Computing
Computing Ri,kO(n
Ai,k needs 2
requires O(n2) ex-
) exponentiations.
challenger, canknows
compute the challenge ciphertext follows:
The time for B to solve the decision n-BDHE problem is
∗ ∗ ∗
c1 = g , c2 = (g ) , ξ = Ze(g, g) .
t t r at τ J = τ + O(n3 )τExp .
Then B sets c∗ = (c∗1 , c∗2 ) and sends (c∗ , ξ ∗ ). In the following, VII. C ONCLUSIONS
we show that (c∗, ξ ∗ ) is well formed.
From Case 1.1, we have that In this paper, we formalized the ConBE primitive. In
ConBE, anyone can send secret messages to any subset
Yn Y Yn
R0,k = (gγ0,k∗ R0,k of the group members, and the system does not require a
gn+1−A) trusted key server. Neither the change of the sender nor the
k=1 A∈Ck∗ k=1,k k∗
Σ
dynamic choice of the intended receivers require extra rounds
Y Y −1 n
= (gγ0,k∗ gn+1−A )( gn+1−k )g k=1,kƒ=k∗ γ0,k to negotiate group encryption/decryption keys. Following the
A∈Ck∗ k∈C,kƒ=k
ConBE model, we instantiated an efficient ConBE scheme that
Y ∗ Σ is secure in the standard model. As a versatile cryptographic
−1 n
γ0,k
=( gn+1−A Y gn+1−k )g k=1 . primitive, our novel ConBE notion opens a new avenue to
A∈Ck∗ establish secure broadcast channels and can be expected to se-
k∈C,kƒ=k
∗
From Case 1.2.1 and Case 1.2.2, we have that cure numerous emerging distributed computation applications.
n
YY Y Σ Σn ACKNOWLEDGMENTS AND DISCLAIMER
−1 k=1 γi,k
Ri,k = n+1−i
g i∈C
The authors are supported by by the Chinese National
i∈C k=1 i∈C
n g Key Basic Research Program (973 program) through project
Σ
Y Y Σ n
γi,k . 2012CB315905, the Natural Science Foundation of China
Ri,k = g i∈St k=1
through projects 61370190, 61173154, 61472429, 61402029,
i∈St k=1
61272501, 61202465, 61321064 and 61003214, the Beijing
Note that Ck∗ = C ∪ C \ { k ∗ } and S∗ = C ∪ {0 } ∪ SJ . We Natural Science Foundation through project 4132056, the
have that Fundamental Research Funds for the Central Universities, and
Yn YY n YY n Σ the Research Funds (No. 14XNLF02) of Renmin University of
Σ n
R0,k Ri,k Ri,k = g i∈S∗ k=1 γi,k = gr. China and the Open Research Fund of Beijing Key Laboratory
k=1 i∈C k=1 i∈St k=1 of Trusted Computing, the European Union through projects
Hence the following equalities hold: FP7 “DwB”, FP7 “Inter-Trust” and H2020 “CLARUS”, the
Spanish Government through projects TSI-020302-2010-153
Y Y Yn and TIN2011-27076-C03-01, the Catalan Government under
( R i )t = ( Ri,k)t grant 2014 SGR 537, the Templeton World Charity Foundation
∗
i∈S∗ i∈S k=1 under grant no.the
TWCF0095, the Shanghai NSF under grant
n n n 12ZR1443500; Shanghai Chen Guang Program (12CG24);
Y YY YY
= (( R0,k )( Ri,k )( Ri,k ))t the Science and Technology Commission of Shanghai Munici-
k=1 i∈C k=1 i∈St k=1 pality under grant 13JC1403500. The fourth author is partially
supported as an ICREA-Acadèmia researcher by the Catalan
= (g r )t = (g t )r = c∗2 .
Government and by a Google Faculty Research Award. The
Q
So far, we obtain that c∗1 = g t , c∗2 = ( ∈i S∗ Ri )t . Hence, URV authors are with the UNESCO Chair in Data Privacy, but
(c∗1 , c∗2 ) is well formed and the simulation of the challenge this paper does not necessarily reflect the position of UNESCO
ciphertext is perfect. nor does it commit that organization.
 17

REFERENCES [25] S. Jarecki, J. Kim and G. Tsudik, “Flexible Robust Group Key Agree-
ment,” IEEE Transactions on Parallel Distributed Systetems, vol. 22, no.
[1] A. Fiat and M. Naor, “Broadcast Encryption,” in Proc. Crypto 1993, 5, pp. 879-886, 2011.
1993, vol. LNCS 773, Lecture Notes in Computer Science, pp. 480- [26] Q. Wu, B. Qin, L. Zhang, J. Domingo-Ferrer and J. Manjón, “Fast
491. Transmission to Remote Cooperative Groups: A New Key Management
[2] I. Ingemarsson, D.T. Tang and C.K. Wong, “A Conference Key Distri- Paradigm,” IEEE/ACM Transactions on Networking, vol. 21, no. 2, pp.
bution System,” IEEE Transactions on Information Theory, vol. 28, no. 621-633, 2013.
5, pp. 714-720, 1982. [27] E. Bertino, N. Shang and S.S. Wagstaff Jr., “An Efficient Time-Bound
[3] Q. Wu, Y. Mu, W. Susilo, B. Qin and J. Domingo-Ferrer, “Asymmetric Hierarchical Key Management Scheme for Secure Broadcasting,” IEEE
Group Key Agreement,” in Proc. Eurocrypt 2009, 2009, vol. LNCS Transactions on Dependable Secure Computing, vol. 5, no. 2, 65-70,
5479, Lecture Notes in Computer Science, pp. 153-170. 2008.
[4] http://en.wikipedia.org/wiki/PRISM %28surveillance program%29, [28] A. Shoufan and S.A. Huss, “High-Performance Rekeying Processor
2014. Architecture for Group Key Management,” IEEE Transactions on Com-
[5] Q. Wu, B. Qin, L. Zhang, J. Domingo-Ferrer and O. Farràs, “Bridging puters, vol. 58, no. 10, 1421-1434, 2009.
Broadcast Encryption and Group Key Agreement,” in Proc. Asiacrypt [29] W. Gu, S. Chellappan, X. Bai and H. Wang, “Scaling Laws of Key Pre-
2011, 2011, vol. LNCS 7073, Lecture Notes in Computer Science, pp. distribution Protocols in Wireless Sensor Networks,” IEEE Transactions
143-160. on Information Forensics and Security, vol. 6, no. 4, 1370-1381, 2011.
[6] D. H. Phan, D. Pointcheval and M. Strefler, “Decentralized Dynamic [30] M.-H. Park, G.-P. Gwon, S.-W. Seo and H.-Y. Jeong, “RSU-Based
Broadcast Encryption,” in Proc. SCN 2012, 2011, vol. LNCS 7485, Distributed Key Management (RDKM) For Secure Vehicular Multicast
Lecture Notes in Computer Science, pp. 166-183 Communications,” IEEE Journal on Selected Areas in Communications,
[7] M. Steiner, G. Tsudik and M. Waidner, “Key Agreement in Dynamic vol. 29, no. 3, pp. 644-658, 2011.
Peer Groups,” IEEE Transactions on Parallel and Distributed Systems, [31] Y. Hao, Y. Cheng, C. Zhou and W. Song, “A Distributed Key Manage-
vol. 11, no. 8, pp. 769-780, 2000. ment Framework with Cooperative Message Authentication in VANET-
[8] A. Sherman and D. McGrew, “Key Establishment in Large Dynamic s,” IEEE Journal on Selected Areas in Communications, vol. 29, no. 3,
Groups Using One-way Function Trees,” IEEE Transactions on Software pp. 616-629, 2011.
Engineering, vol. 29, no. 5, pp. 444-458, 2003. [32] Z. Liu, J. Ma, Q. Pei, L. Pang and Y. Park, “Key Infection, Secrecy
[9] Y. Kim, A. Perrig and G. Tsudik, “Tree-Based Group Key Agreement,” Transfer and Key Evolution for Sensor Networks,” IEEE Transactions
ACM Transactions on Information System Security, vol. 7, no. 1, pp. 60- on Wireless Communications, vol. 9, no. 8, 2643-2653, 2010.
96, 2004. [33] Z. Yu and Y. Guan, “A Key Management Scheme Using Deployment
[10] Y. Mao, Y. Sun, M. Wu and K.J.R. Liu, “JET: Dynamic Join-Exit- Knowledge for Wireless Sensor Networks,” IEEE Transactions Parallel
Tree Amortization and Scheduling for Contributory Key Management,” Distributed Systems, vol. 19, no. 10, pp. 1411-1425, 2008.
IEEE/ACM Transactions on Networking, vol. 14, no. 5, pp. 1128-1140, [34] B.-J. Chang and S.-L. Kuo, “Markov Chain Trust Model for Trust-Value
2006. Analysis and Key Management in Distributed Multicast MANETs,”
[11] C. Boyd and J.M. González-Nieto, “Round-Optimal Contributory Con- IEEE Transactions on Vehicular Technology, vol. 58, no. 4, pp. 1846-
ference Key Agreement,” in Proc. PKC 2003, 2003, vol. LNCS 2567, 1862, 2009.
Lecture Notes in Computer Science, pp. 161-174.
[35] B. Rong, H.-H. Chen, Y. Qian, K. Lu, R. Q. Hu and S. Guizani, “A
[12] W.-G. Tzeng and Z.-J. Tzeng, “Round Efficient Conference Key Agree- Pyramidal Security Model for Large-Scale Group-Oriented Computing
ment Protocols with Provable Security,” in Proc. Asiacrypt 2000, 2000, in Mobile Ad Hoc Networks: The Key Management Study,” IEEE
vol. LNCS 1976, Lecture Notes in Computer Science, pp. 614-627. Transactions on Vehicular Technology, vol. 58, no. 1, pp. 398-408, 2009.
[13] R. Dutta and R. Barua, “Provably Secure Constant Round Contributory
[36] M. Naor and B. Pinkas, “Efficient Trace and Revoke Schemes,” in Proc.
Group Key Agreement in Dynamic Setting,” IEEE Transactions on
FC 2000, 2000, vol. LNCS 1962, Lecture Notes in Computer Science,
Information Theory, vol. 54, no. 5, 2007-2025, 2008.
pp. 1-20.
[14] W.-G. Tzeng, “A Secure Fault-Tolerant Conference-Key Agreement
[37] C.K. Wong, M. Gouda and S. Lam, “Secure Group Communications
Protocol,” IEEE Transactions on Computers, vol. 51, no.4, pp. 373-379,
Using Key Graphs,” IEEE/ACM Transactions on Networking, vol. 8,
2002.
no. 1, pp. 16-30, 2000.
[15] X. Yi, “Identity-Based Fault-Tolerant Conference Key Agreement,”
IEEE Transactions Dependable Secure Computing vol. 1, no. 3, 170- [38] D. Wallner, E. Harder and R. Agee, “Key Management for Multicast:
178, 2004. Issues and Architectures”, The RFC Repaort 2627, 1999. Available at:
http://www.rfc-editor.org/rfc/pdfrfc/rfc2627.txt.pdf.
[16] M. Burmester and Y. Desmedt, “A Secure and Efficient Conference Key
Distribution System,” in Proc. Eurocrypt 1994, 1994, vol. LNCS 950, [39] M.T. Goodrich, J. Z. Sun and R. Tamassia, “Efficient Tree-Based
Lecture Notes in Computer Science, pp. 275-286. Revocation in Groups of Low-State Devices,” in Proc. Crypto 2004,
[17] A. Joux, “A One Round Protocol for Tripartite Diffie-Hellman,” Journal 2004, vol. LNCS 3152, Lecture Notes in Computer Science, pp. 511-
of Cryptology, vol. 17, no. 4, pp. 263-276, 2004. 527.
[18] D. Boneh and A. Silverberg, “Applications of Multilinear Forms to [40] J.H. Cheon, N.S. Jho, M.H. Kim and E.S. Yoo, “Skipping, Cascade and
Crytography,” Contemporary Mathematics, vol. 324, pp.71-90, 2003. Combined Chain Schemes for Broadcast Encryption,” IEEE Transac-
[19] E. Bresson, O. Chevassut and D. Pointcheval, “Provably Authenticated tions Information Theory, vol. 54, no. 11, pp. 5155-5171, 2008.
Group Diffie-Hellman Key Exchange – The Dynamic Case,” in Proc. [41] L. Harn and C. Lin, “Authenticated Group Key Transfer Protocol Based
Asiacrypt 2001, 2001, vol. LNCS 2248, Lecture Notes in Computer on Secret Sharing,” IEEE Transactions on Computers, vol. 59, no. 6,
Science, pp. 290-309. pp. 842-846, 2010.
[20] E. Bresson, O. Chevassut and D. Pointcheval, “Dynamic Group Diffie- [42] D. Boneh, C. Gentry and B. Waters, “Collusion Resistant Broadcast
Hellman Key Exchange under Standard Assumptions,” in Proc. Euro- Encryption with Short Ciphertexts and Private Keys,” in Proc. Crypto
crypt 2002, 2002, vol. LNCS 2332, Lecture Notes in Computer Science, 2005, 2005, vol. LNCS 3621, Lecture Notes in Computer Science, pp.
pp. 321-336. 258-275.
[21] E. Bresson, O. Chevassut, D. Pointcheval and J.-J. Quisquater, “Provably [43] J.H. Park, H.J. Kim, M.H. Sung and D.H. Lee, “Public Key Broadcast
Authenticated Group Diffie-Hellman Key Exchange,” in Proc. ACM CCS Encryption Schemes With Shorter Transmissions,” IEEE Transactions
2001, 2001, pp. 255-264. on Broadcasting, vol. 54, no. 3, pp. 401-411, 2008.
[22] J. Snoeyink, S. Suri and G. Varghese, “A Lower Bound for Multicast [44] C. Gentry and B. Waters, “Adaptive Security in Broadcast Encryption
Key Distribution,” in Proc. INFOCOM 2001, 2001, pp. 422-431. Systems (with Short Ciphertexts),” in Proc. Eurocrypt 2009, 2009, vol.
[23] H.J. Kim, S.M. Lee and D. H. Lee, “Constant-Round Authenticated LNCS 5479, Lecture Notes in Computer Science, pp. 171-188.
Group Key Exchange for Dynamic Groups,” in Proc. Asiacrypt 2004, [45] A. B. Lewko, A. Sahai, B. Waters, “Revocation Systems with Very Small
2004, vol. LNCS 3329, Lecture Notes in Computer Science, pp. 245- Private Keys,” in Proc. IEEE S&P 2010, 2010, pp. 273-285.
259. [46] D. Boneh, C. Gentry, S. Gorbunov, S. Halevi, V. Nikolaenko, G. Segev,
[24] M. Abdalla, C. Chevalier, M. Manulis and D. Pointcheval, “Flexible V. Vaikuntanathan and D. Vinayagamurthy, “Fully Key-Homomorphic
Group Key Exchange with On-demand Computation of Subgroup Keys,” Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits,”
in Proc. Africacrypt 2010, 2010, vol. LNCS 6055, Lecture Notes in in Proc. Eurocrypt 2014, 2014, vol. LNCS 8441, Lecture Notes in
Computer Science, pp. 351-368. Computer Science, pp. 533-556.
 18

[47] D. Boneh, X. Boyen and E.J. Goh, “Hierarchical Identity Based Encryp- Josep Domingo-Ferrer is a Full Professor of Com-
tion with Constant Size Ciphertext,” in Proc. Eurocrypt 2005, 2005, vol. puter Science and an ICREA-Acadèmia Researcher
LNCS 3494, Lecture Notes in Computer Science, pp. 440-456. at Universitat Rovira i Virgili, Tarragona, Catalonia,
[48] R. Canetti, S.Halevi, and J. Katz, “Chosen-Ciphertext Security from where he holds the UNESCO Chair in Data Privacy.
Identity-based Encryption,” in: Proc. EUROCRYPT 2004, 2004, vol. His research interests are in data privacy and data se-
LNCS 3027, pp. 207-222. curity. He received his M. Sc. and Ph. D. degrees in
[49] T. Matsuda and G. Hanaoka, “Chosen Ciphertext Security via UCE,” in Computer Science from the Autonomous University
Proc. PKC 2014, 2014, vol. LNCS 8383, Lecture Notes in Computer of Barcelona in 1988 and 1991, respectively. He also
Science, pp. 56-76. holds an M. Sc. in Mathematics. He has won several
[50] W. Liu, J. Liu, Q. Wu, B. Qin, Y Zhou, “Practical Direct Chosen research and technology transfer awards, including
Ciphertext Secure Key-Policy Attribute-based Encryption with Public the IEEE Fellow Grade, a Google Faculty Research
Ciphertext Test,” in Proc. ESORICS 2014, 2014, vol. LNCS 8713, pp. Award, and the Government of Catalonia’s “Narc´ıs Monturiol” Medal to the
91-108. scientific merit and twice the ICREA Acadèmia Prize. He has authored 5
[51] M. Scott, “On the Efficient Implementation of Pairing-Based Protocols,” patents and over 340 publications. He has been the co-ordinator of projects
http://eprint.iacr.org/2011/334.pdf, 2011. funded by the European Union and the Spanish government, among which
the CONSOLIDER ARES project on security and privacy, one of Spain’s 34
strongest research teams. He has been the PI of US-funded research contracts.
He has held visiting appointments at Princeton, Leuven and Rome. He is a co-
Editor-in-Chief of Transactions on Data Privacy.

Qianhong Wu received his Ph.D. in Cryptography

from Xidian University in 2004. Since then, he has
been with Wollongong University (Australia) as an
associate research fellow, with Wuhan University
(China) as an associate professor, with Universitat
Rovira i Virgili (Catalonia) as a research director
and now with Beihang University (China) as a full
professor. His research interests include cryptogra-
phy, information security and privacy, and ad hoc
network security. He has been a holder/co-holder
of 7 China/Australia/Spain funded projects. He has Oriol Farràs is a Juan de la Cierva postdoctoral
authored 7 patents and over 100 publications. He has served in the program researcher at the UNESCO Chair in Data Privacy
committee of several international conferences in information security and and the CRISES Research Group in the Department
privacy. He is a member of IACR, ACM and IEEE. of Computer Engineering and Maths at Universitat
Rovira i Virgili, Tarragona, Catalonia. He received
his M.Sc. degree in Mathematics and his M.Sc.
degree in Telecommunication Engineering from Uni-
versitat Politècnica de Catalunya in 2004 and 2005,
respectively. He received his Ph.D. degree in Math-
ematics from Universitat Politècnica de Catalunya
in 2010. He has been a postdoctoral fellow in the
Bo Qin received her Ph.D. degree in Cryptography Department of Computer Science at Ben Gurion University of the Negev,
from Xidian University in 2008 in China. Since then, Israel, and a Director of Research at Universitat Rovira i Virgili. His research
she has been with Xi’an University of Technology interests include cryptography, secret sharing, and information theory.
(China) as a lecturer, with Universitat Rovira i Virgili
(Catalonia) as a postdoctoral researcher, and now
with Renmin University of China as a lecturer. Her
research interests include pairing-based cryptogra-
phy, data security and privacy, and VANET security.
She has been a holder/co-holder of 6 China/Spain
funded projects. She has authored over 60 publica-
tions and served in the program committee of several
international conferences in information security.

Jesús A. Manjón is a computer engineer with the

UNESCO Chair in Data Privacy and the CRISES
Research Group at the Department of Computer En-
Lei Zhang received his Ph.D. degree in computer gineering and Maths at Universitat Rovira i Virgili,
engineering from Universitat Rovira i Virgili, Tar- Tarragona, Catalonia. He got his B.Sc. in Computer
ragona, Spain, in 2010. He is an Associate Research Engineering in 2004 and his M.Sc. in Computer
Fellow with Software Engineering Institute, East Security in 2008. He has participated in several
China Normal University, Shanghai, China. Before Spanish-funded projects and he is a co-author of
this, he had been a Postdoctoral Researcher with several research publications on security and privacy.
Universitat Rovira i Virgili. His fields of activity
are information security, cryptography, data privacy,
and network security. He has been a holder/co-holder
of 5 China/Spain funded projects. He has authored
over 50 publications. He has served in the program
committee of several international conferences in information security and
privacy. He is a member of IEEE.