# Adaptive Security of Broadcast Encryption, Revisited

Authors: Bingxin Zhu; Puwen Wei; Mingqiang Wang
Journal: Security and Communication Networks
 (2017)

---

## Abstract

We provide a strong security notion for broadcast encryption, called adaptive security in the multichallenge setting (MA-security), where the adversary can adaptively have access to the key generation oracle and the encryption oracle many times (multichallenge). The adversary specially can query for the challenge ciphertexts on different target user sets adaptively, which generalizes the attacks against broadcast encryptions in the real world setting. Our general result shows that the reduction of the adaptive secure broadcast encryption will lose a factor ofq in the MA setting, where q is the maximum number of encryption queries. In order to construct tighter MA-secure broadcast encryptions, we investigate Gentry and Water’s transformation and show that their transformation can preserve MA-security at the price of reduction loss on the advantage of the underlying symmetric key encryption. Furthermore, we remove the q-type assumption in Gentry and Water’s semistatically secure broadcast encryption by using Hofheinz-Koch-Striecks techniques. The resulting scheme instantiated in a composite order group is MA-secure with constant-size ciphertext header.


---

## Body

## 1. Introduction

Broadcast encryptions (BE), introduced by Fiat and Naor [1], allow a sender to broadcast encrypted messages in such a way that only a specified group of users can decrypt the messages. Such schemes are useful in many applications, for example, pay-TV systems, internet multicasting of video and music, DVD content protection, file system access control, and wireless sensor networks [2]. One basic security requirement for broadcast encryption is the fully collusion resistance, which means that even a coalition of all users outside of target user set S learns nothing about the target plaintext. Naor et al. [3] proposed a fully collusion secure broadcast encryption scheme with the private key overhead Olog2n, where n is the total number of users. Subsequent works [4, 5] reduced the private key size to O(log⁡n). However, the ciphertexts size of collusion resistant schemes, for example, [3–6], usually grows linearly with either the number of receivers or the number of revoked users. Boneh et al. [7] constructed a fully collusion secure broadcast encryption systems with low ciphertext overhead and short secret keys. But the security of their scheme was proven in a static model, where the adversary needs to choose the target user set before seeing the system parameter. To capture more powerful attacks, Gentry and Waters [8] provided a stronger security model, called adaptive security, where the adversary can compromise users’ keys and choose the target user set adaptively. They showed a generic method to construct adaptively secure broadcast encryption scheme by transforming semistatically secure broadcast encryption scheme, while the underlying semistatically secure scheme in [8] is based on a q-type assumption, which is considered to be too strong. By introducing the dual system, Waters [9] presented a broadcast encryption scheme with ciphertext overhead of constant size, and the resulting scheme can be proven adaptively secure under static assumption (non-q-type assumption). Then, Boneh, Waters, and Zhandry [10] made use of multilinear maps to construct a broadcast encryption where ciphertext overhead, private key size, and public key size are all poly-logarithmic in n. Other works [11–15] focus on the improvements of broadcast encryptions with special functionalities, for example, identity-based BE, anonymous BE, and traitor-tracing BE. Recently, Wee [16] presented the first broadcast encryption scheme with constant-size ciphertext overhead, constant-size user secret keys, and linear-size public parameters under static assumptions, while the resulting scheme is proven secure under static security model.It is worth noting that although adaptive security defined in [8] seems strong enough to capture the security of broadcast encryptions, attacks in the real world are more complex, for example, the adversary may adaptively get multiple challenge ciphertexts instead of only one. Such attacks are described in the so-called multiuser, multichallenge setting. Bellare et al. [17] initiated the study of the formal security in the multiuser setting, which shows that one-user, one-ciphertext security implies security in the multiuser, multichallenge setting. But the reduction loss of the proof is nu·nc, where nu and nc denote the number of users and the number of challenge ciphertexts per user, respectively. However, large reduction loss usually implies large cryptographic parameters, which leads to low efficiency in practice. Recent breakthrough was made by Hofheinz and Jager [18], which provided the first IND-CCA secure PKE in the multiuser/multichallenge setting and the security tightly relates to the decision linear assumption. Here, tight security means that the security loss is a constant. Hofheinz, Koch, and Striecks [19] extended Chen and Wee’s proof technique [20] to the multiuser/multichallenge setting and provided an almost tightly secure identity-based encryption (IBE) in the same setting, where the security loss only relies on the security parameter instead of the number of queries or instances of the scheme. Hence, an extension of broadcast encryptions in the multiuser/multichallenge setting is natural. However, the problem of constructing tightly secure broadcast encryptions in the multiuser/multichallenge setting is more subtle.Our Contribution. We define a stronger notion for broadcast encryption, called the adaptive security in the multichallenge setting (MA-security), where the adversary can not only adaptively have access to the key generation oracle and the encryption oracle many times (multichallenge) but also adaptively query for the challenge ciphertexts on different target user sets instead of only one target set as in previous security model. Since each target user set is actually the combination of different users chosen by the adversary adaptively, it is more challenging for the reduction algorithm to prepare the parameters of broadcast encryptions than that of ordinary PKE or IBE.Our general result shows that the reduction of the adaptive secure broadcast encryption will lose a factor ofq in the MA setting, where q is the maximum number of encryption queries. To achieve tighter MA-security, we investigate the following two methods. The first method is from Gentry and Waters transformation [8] mentioned above. By exploring the random self-reducibility of BDHE assumption, we show that their transformation still holds in terms of MA-security, but at the cost of reduction loss q on the advantage of underlying symmetric key encryption. We emphasize that the resulting broadcast encryption scheme’s security depends on both the BDHE assumption and the security of the symmetric key encryption. The reduction loss on the underlying symmetric key encryption is q, while the reduction on BDHE is tight due to the random self-reducibility of BDHE assumption, which is not implied by the general result of [17]. To remove the BDHE assumption, our second method applies the Hofheinz-Koch-Striecks techniques [19] to Gentry-Waters’ semistatic secure broadcast encryption. The resulting scheme is essentially the Hofheinz-Koch-Striecks IBE scheme instantiated in a composite order group, while the user’s decryption key of broadcast encryption is expressed in a different way from that of [19]. Both methods can turn Gentry-Waters’ semistatically secure broadcast encryption into a MA-secure one with constant-size ciphertext header.Note that the public key size of both schemes is linear with the number of users. An interesting problem is how to reduce the public key size of a MA-secure broadcast encryption under standard assumptions while preserving constant ciphertext header size.


## 2. Preliminaries

Notations. Let 1,n≔1,…,n, where n∈N. For a finite set S, we denote by x←RS the fact that x is picked uniformly at random from S. S can be denoted as a binary string; that is, S=s1⋯sn, where si∈0,1 for i∈1,n. We write vectors in bold font; for example, K=(K0,…,K2n) for a vector of length 2n+1. SDX;Y denotes the statistical distance of X and Y, where X and Y are random variables. We say X and Y are ε-close if SDX;Y≤ε.


### 2.1. Bilinear Map

LetG and GT be two groups of prime order p, and let g be a generator of G. e:G×G→GT is a bilinear map with the following properties.(1)
Bilinearity: for allu,v∈G and a,b∈Z, eua,vb=eu,vab.(2)
Nondegeneracy:eg,g≠1.(3)
Computability: there exists an efficient algorithm to computeeu,v, for any u,v∈G.


### 2.2. Assumptions

Decisional BDHE Problem [8]. Let G,GT,e,p be the description of the group parameter which is the output of group generator Gλ, where λ is the security parameter. Choose b←R0,1 and given 2n+2 elements(1)gs,g,ga,ga2,…,gan,gan+2,…,ga2n∈G2n+1,Z∈GT,where a,s←RZp∗, Z←egs,gan+1 if b=0 and Z←RGT if b=1. The problem is to guess b.The decisional BDHE assumption states that for any PPT adversaryA which takes as inputs the description of G,GT,e and the above elements and outputs b∗, the advantage(2)AdvG,ABDHEλ≔Prb=b∗-12is negligible in λ.


### 2.3. Broadcast Encryption Systems

A broadcast encryption system consists of four randomized algorithms described below.S
e
t
u
p
(
n
,
l
). Take as input the number of users n and the maximal size l≤n of a broadcast recipient group and output a public/secret key pair PK,SK. (The security parameter λ is taken as parts of the input implicitly.)K
e
y
G
e
n
(
i
,
S
K
). Take as input a user index i∈1,n and the secret key SK and output a private key di.E
n
c
(
S
,
P
K
). Take a user set S⊆1,n and the public key PK as input. It outputs a pair Hdr,K, where Hdr is the header and K∈K is the message encryption key from a key space K.D
e
c
(
S
,
i
,
d
i
,
H
d
r
,
P
K
). Take as input a user set S⊆1,n, a user index i∈1,n, and the corresponding private key di for user i, a header Hdr, and the public key PK. If i∈S, then the algorithm outputs the message encryption key K∈K.


## 2.1. Bilinear Map

LetG and GT be two groups of prime order p, and let g be a generator of G. e:G×G→GT is a bilinear map with the following properties.(1)
Bilinearity: for allu,v∈G and a,b∈Z, eua,vb=eu,vab.(2)
Nondegeneracy:eg,g≠1.(3)
Computability: there exists an efficient algorithm to computeeu,v, for any u,v∈G.


## 2.2. Assumptions

Decisional BDHE Problem [8]. Let G,GT,e,p be the description of the group parameter which is the output of group generator Gλ, where λ is the security parameter. Choose b←R0,1 and given 2n+2 elements(1)gs,g,ga,ga2,…,gan,gan+2,…,ga2n∈G2n+1,Z∈GT,where a,s←RZp∗, Z←egs,gan+1 if b=0 and Z←RGT if b=1. The problem is to guess b.The decisional BDHE assumption states that for any PPT adversaryA which takes as inputs the description of G,GT,e and the above elements and outputs b∗, the advantage(2)AdvG,ABDHEλ≔Prb=b∗-12is negligible in λ.


## 2.3. Broadcast Encryption Systems

A broadcast encryption system consists of four randomized algorithms described below.S
e
t
u
p
(
n
,
l
). Take as input the number of users n and the maximal size l≤n of a broadcast recipient group and output a public/secret key pair PK,SK. (The security parameter λ is taken as parts of the input implicitly.)K
e
y
G
e
n
(
i
,
S
K
). Take as input a user index i∈1,n and the secret key SK and output a private key di.E
n
c
(
S
,
P
K
). Take a user set S⊆1,n and the public key PK as input. It outputs a pair Hdr,K, where Hdr is the header and K∈K is the message encryption key from a key space K.D
e
c
(
S
,
i
,
d
i
,
H
d
r
,
P
K
). Take as input a user set S⊆1,n, a user index i∈1,n, and the corresponding private key di for user i, a header Hdr, and the public key PK. If i∈S, then the algorithm outputs the message encryption key K∈K.


## 3. Adaptive Security in the Multichallenge Setting (MA-Security)

In this section, we define the adaptive security of broadcast encryption in the multichallenge setting. LetBE=(Setup,KeyGen,Enc,Dec) be a broadcast encryption scheme. The experiment for BE is described in Table 1.Table 1
MA experiment.
E
x
p
A
,
B
E
M
A
(
λ
)
P
K
,
S
K
⟵
S
e
t
u
p
n
,
l;
b
⟵
R
0,1;
b
′
⟵
A
O
K
e
y
G
e
n
⋅
,
S
K
,
O
E
n
c
⋅
,
P
K;
Ifb′=b, return 1; otherwise, 0.During the experiment, the adversaryA takes λ and the description of BE including PK as inputs and A can have access to the following two kinds of oracles.(i)
OKeyGen·,SK is the secret key generation oracle which takes a user index i as input and outputs KeyGeni,SK. Note that A cannot make i as the key generation query if i∈Sj, where Sj has been queried to the encryption oracle. Suppose the adversary can make qkey key generation queries at most.(ii)
OEnc·,PK is the encryption oracle which takes Sj as input and outputs the challenge ciphertext Cj=Hdrj∗,Kb,j, where Hdrj∗,K0,j←EncSj,PK, K1,j←RK. The restriction on encryption query is that Sj can not include any user index i which has been queried to OKeyGen. Suppose that the adversary A can only query encryption oracle OEnc·,PK at most qEnc times.A broadcast encryption schemeBE is adaptively secure in the multichallenge setting (MA-secure) if, for any PPT adversary A, the advantage(3)AdvA,BEMAλ≔Pr⁡ExpA,BEMAλ=1-12 is negligible in λ.Remark 1.
The main difference between our MA-security and the adaptive security defined in [8] is the encryption queries. In MA-security experiment, the adversary can not only adaptively have access to the encryption oracle many times but also query for the challenge ciphertexts on different target user sets, while the adversary can make only one encryption query for one target user set in adaptive security experiment ExpA,BEA [8], where the related advantage of ExpA,BEA is denoted as AdvA,BEA(λ)≔Pr⁡ExpA,BEAλ=1-1/2.To investigate Gentry and Waters transformation in the multichallenge setting, we also need to extend semistatic security defined in [8] to the multichallenge setting, which is called semistatic security in the multichallenge setting (MS-security). The MS-security is defined in a similar way as that of MA-security, where the adversary also takes λ and the description of BE including PK as inputs and can have access to OKeyGen·,SK and OEnc·,PK as defined in MA-security. But additional restrictions in MS-security are that A has to choose a target user set S∗ at the beginning of the experiment and encryption queries Sj are such that Sj⊆S∗. Details of MS experiment are shown in Table 2Table 2
MS experiment.
E
x
p
A
,
B
E
M
S
(
λ
)
S
∗
⟵
A;
P
K
,
S
K
⟵
S
e
t
u
p
n
,
l;
b
⟵
R
0,1;
b
′
⟵
A
O
K
e
y
G
e
n
⋅
,
S
K
,
O
E
n
c
⋅
,
P
K;
Ifb′=b, return 1; otherwise, 0.A broadcast encryption schemeBE is semistatically secure in the multichallenge setting (MS-secure) if, for any PPT adversary A, the advantage(4)AdvA,BEMS≔Pr⁡ExpA,BEMSλ=1-12 is negligible in λ.


## 4. MA-Secure Broadcast Encryption

First we give a general result on the reduction loss of an adaptive secure broadcast encryption in the MA setting. Then, to derive a tighter reduction, we show how to extend Gentry-Waters transformation to the multichallenge setting and construct a concrete MA-secure broadcast encryption based on BDHE assumption.


### 4.1. General Construction

Theorem 2.
For any PPT adversaryA which can make at most qkey=qkeyλ key generation queries and qEnc=qEncλ encryption queries with running time t′, there exists an algorithm B with about the same running time as A, such that(5)AdvA,BEMAλ≤qEnc·AdvB,BEAλ.Proof.
The proof proceeds via the following games.(i)
Game0: Game0 is the real MA experiment except the following differences. When the adversary adaptively makes encryption query for set Sj, the challenger responds with EncSj,PK=Hdrj,K0,j, where j∈1,qEnc.(ii)
Game1: Game1 is identical to Game0 except that the challenger replies the encryption queries with Hdrj,K1,j for j∈1,qEnc, where Hdrj,K0,j←EncSj,PK,K1,j←RK∗ and K∗ denotes the key space. Now we construct a series of subgames 0,ι for ι=0,…,qEnc to prove the indistinguishability between Game0 and Game1. (i)
Game0,1. Game0,1 is the same as Game0 except that the challenger chooses K1,1←RK∗ to construct challenge (Hdr1,K1,1) for the first encryption query S1.(ii)
Game0,ι. Game0,ι is the same as Game0,ι-1 except that the challenger chooses K1,ι←RK∗ to construct challenge (Hdrι,K1,ι) for the ιth encryption query Sι, where ι∈1,qEnc. Let Game0,ι=1 denote the event that the adversary outputs 1 in Game0,ι. Note that Game0,0 and Game0,qEnc are identical to Game0 and Game1, respectively. Thus,(6)AdvA,BEMAλ≔Pr⁡ExpA,BEMAλ=1-12=12·Pr⁡ExpA,BEMAλ=0∣b=0+12·Pr⁡ExpA,BEMAλ=1∣b=1-12=12·Pr⁡ExpA,BEMAλ=1∣b=1-1-Pr⁡ExpA,BEMAλ=0∣b=0=12·Pr⁡ExpA,BEMAλ=1∣b=1-Pr⁡ExpA,BEMAλ=1∣b=0=12·Pr⁡Game1=1-Pr⁡Game0=1=12·Pr⁡Game0,qEnc=1-Pr⁡Game0,0=1=12·Pr⁡Game0,qEnc=1-Pr⁡Game0,qEnc-1=1+Pr⁡Game0,qEnc-1=1-Pr⁡Game0,qEnc-2=1+⋯+Pr⁡Game0,1=1-Pr⁡Game0,0=1≤12·∑ι=1qEncPr⁡Game0,ι=1-Pr⁡Game0,ι-1=1.Next, we show that PrGame0,ι=1-Pr⁡Game0,ι-1=1 is negligible, for ι∈1,qEnc. That is, if there exists a PPT adversary A1 which can distinguish the adjacent games for some ι, we can construct a PPT algorithm B which can break the adaptive security of the underlying scheme.
Claim
G
a
m
e
0
,
ι
-
1
t
o
G
a
m
e
0
,
ι
. For any PPT adversary A1 which can make at most qkey=qkeyλ key generation queries and qEnc=qEncλ encryption queries with running time t′, there exists algorithm B with about the same running time as A1, such that(7)12·Pr⁡Game0,ι=1-Pr⁡Game0,ι-1=1=AdvB,BEAλ.Proof. B simulates the experiment as follows. (i)
The challenger runsSetupn,l and sends PK to B which will send PK to A1.(ii)
A1 adaptively makes key generation queries for user index i.(iii)
B sends user index i to the challenger which runs KeyGeni,SK and sends back the secret key di for user i. Then B sends di to A1.(iv)
A1 adaptively makes encryption queries for Sj, where j denotes the jth query.
(a)
Ifj∈1,ι-1, B runs EncSj,PK=Hdrj,K0,j and chooses K1,j←RK∗ and sends Hdrj,K1,j to A1.(b)
Ifj∈ι+1,qEnc, B runs EncSj,PK=Hdrj,K0,j and sends Hdrj,K0,j to A1.(c)
Ifj=ι, B sends Sι to the challenger which then chooses b←R{0,1} and sends back Cι∗=Hdrι,Kb,ι where K1,ι←RK∗,Hdrι,K0,ι←EncSι,PK. Next B sends Cι∗ to A1.(v)
A1 outputs b′. If b′=b, B outputs 1, otherwise, 0. Observe that if b=1, A1’s view is identical to that of Game0.ι. Otherwise A1’s view is identical to that of Game0.ι-1. Thus(8)AdvB,BEA≔Pr⁡ExpB,BEAλ=1-12=12·Pr⁡ExpB,BEAλ=1∣b=1+12·Pr⁡ExpB,BEAλ=0∣b=0-12=12·Pr⁡ExpB,BEAλ=1∣b=1-1-Pr⁡ExpB,BEAλ=0∣b=0=12·Pr⁡ExpB,BEAλ=1∣b=1-Pr⁡ExpB,BEAλ=1∣b=0=12·Pr⁡Game0,ι=1-Pr⁡Game0,ι-1=1.Hence we have(9)AdvA,BEMAλ≤qEnc·AdvB,BEAλ,which completes the proof of Theorem 2.


### 4.2. MS-Secure Broadcast Encryption Based on BDHE Assumption

To reduce the reduction loss, we investigate Gentry-Waters broadcast encryption [8] in the MA setting. First we briefly recall the semistatically secure broadcast encryption scheme in [8]. Let G(λ,n) be a PPT algorithm which takes as input the security parameter λ and the number of users n and generates the description of group parameter (G,GT,e,p), where G,GT denotes the group of prime order p=pλ,n and e is the bilinear map.S
e
t
u
p
(
n
). (G,GT,e)←RG(λ,n), g,h1,…,hn←RGn+1, where g,h1,…,hn are generators of G and α←RZp. Set(10)PK=G,GT,e;g,eg,gα,h1,…,hn,(11)SK=gα. Output PK,SK.K
e
y
G
e
n
(
i
,
S
K
). Choose ri←RZp and output user i’s private key(12)di=di,0,di,1,…,di,i-1,di,i,di,i+1,…,di,n=g-ri,h1ri,…,hi-1ri,gαhiri,hi+1ri,…,hnri.E
n
c
(
S
,
P
K
). Choose t←RZp and compute C1=gt,C2=∏j∈Shjt. Set(13)Hdr=gt,∏j∈Shjt,(14)K=eg,gα·t. Output (Hdr,K).D
e
c
(
S
,
i
,
d
i
,
H
d
r
,
P
K
). If i∈S, parse di as (di,0,…,di,n) and Hdr as (C1,C2) and output(15)K=edi,i·∏j∈S∖idi,j,C1·edi,0,C2.Theorem 3.
For any PPT adversaryA which can make at most qkey=qkey(λ) key generation queries, qEnc=qEnc(λ) encryption queries with running time t′, there exists an algorithm B with about the same running time as A, such that(16)AdvA,BEMSλ=AdvG,BBDHEλ.The proof is similar to that of [8] except that we have to deal with multiple challenges in the simulation. Furthermore, to derive a tighter reduction, we need the following lemma which makes use of the random self-reducibility of BDHE.Lemma 4.
There exists an efficient algorithm that takes as inputgs,g,ga,ga2,…,gan,gan+2,…,ga2n,Z for Z=egan,gc and generates many tuples of the form(17)gsj,g,ga,ga2,…,gan,gan+2,…,ga2n,Zj, where Zj=egan,gcj and sj,cj∈Zp.Proof.
Computegsj=gsvj·guj and Zj=Zvj·egan,gauj, where uj,vj←RZp. Let e=c-as mod p. We implicitly set(18)sj=s·vj+ujmodp,cj=asj+evjmodp.Hence, we have(19)Zj=egan,gasjifc=asmodpegan,gasj+evjifc≠asmodp. If e=0, namely, c=as, then cj=asj. If e≠0, namely, c≠as, then cj=asj+evj. Since evj are uniformly distributed, we have cj uniformly distributed over Zp.Next, more details of the concrete proof of Theorem3 can be found in Appendix A.


### 4.3. Transforming MS-Security to MA-Security

In this section, we show that Gentry-Waters transformation still holds in the multichallenge setting, but at the cost of reduction lossqEnc in the advantage of underlying symmetric encryption scheme. First, we briefly recall Gentry-Waters transformation [8]. Let BEMS=(SetupMS,KeyGenMS, EncMS,DecMS) be a MS-secure broadcast system and Πsym=SymSetup,SymEnc,SymDec be a symmetric encryption scheme with key space K′.S
e
t
u
p
(
n
). Run SetupMS(2n)→PK′,SK′. Let s←R0,1n and si denotes ith bit of s. Let PK=PK′ and SK=(SK′,s). Output PK,SK.K
e
y
G
e
n
(
i
,
S
K
). Run KeyGenMS(2i-si,SK′)→di′. Set di=di′,si. Output private key di.E
n
c
(
S
,
P
K
). Generate random S bits: t←ti←R0,1:i∈S and K←RK. Set(20)S0⟵2i-ti:i∈S,EncMSS0,PK′⟶Hdr0,κ0,SymEncκ0,K⟶C0;S1⟵2i-1-ti:i∈S,EncMSS1,PK′⟶Hdr1,κ1,SymEncκ1,K⟶C1;Hdr⟵Hdr0,Hdr1,C0,C1,t.Output (Hdr,K).D
e
c
(
S
,
i
,
d
i
,
H
d
r
,
P
K
). Parse Hdr as Hdr0,Hdr1,C0,C1,t and di as di′,si. Set S0 and S1 as above. Run(21)κsi⊕ti⟵DecMSSsi⊕ti,i,di′,Hdrsi⊕ti,PK′,K⟵SymDecκsi⊕ti,Csi⊕ti.Output K.Theorem 5.
For any PPT adversaryA which can make at most qkey=qkey(λ) key generation queries and qEnc=qEnc(λ) encryption queries with running time t′, there exist algorithms A1,A2,A3, and A4, each with about the same running time as A, such that(22)AdvA,BE,nMAλ≤AdvA1,BE,2nMSλ+AdvA2,BE,2nMSλ+qEnc·AdvA3,ΠsymCPAλ+qEnc·AdvA4,ΠsymCPAλ.Notice thatAdvB,ΠsymCPAλ denotes the advantage of Πsym=(SymSetup, SymEnc,SymDec), which is defined by the following one-time symmetric key IND-CPA experiment described in Table 3.Table 3
IND-CPA experiment.
E
x
p
A
,
Π
s
y
m
C
P
A
(
λ
)
b
⟵
R
0,1;
k
⟵
S
y
m
S
e
t
u
p
1
λ;
b
′
⟵
A
O
E
n
c
′
k
,
⋅;
Ifb′=b, return 1; otherwise, 0.During the experiment,A takes the security parameter and the description of Πsym as input and can make only one encryption query to encryption oracle O′Enc(k,·). More precisely, A chooses a pair of plaintexts (m0,m1) of the same length as the query and O′Enc(k,·) returns SymEnc(k,mb) as the challenge ciphertext.We say the symmetric key encryption schemeΠsym is one-time CPA-secure if, for any PPT adversary A, the advantage(23)AdvA,ΠsymCPA≔Pr⁡ExpA,ΠsymCPAλ=1-12 is negligible in λ, where the probability is taken over the random coins used in the experiment, as well as the random coins used by A.Proof of Sketch.The main idea of the proof is similar to that of [8] except that we need to deal with multiple challenges, which incurs a reduction loss in the advantage of symmetric key encryption scheme. More precisely, we need to prove the indistinguishability of the following games.(i)
Game0 is identical to ExpA,BEMAλ.(ii)
Game1 is the same as Game0 except that for each encryption query the challenger chooses κ0,j←RK′ to construct C0,j=SymEncκ0,j,K0,j, where K0,j=K1,j.(iii)
Game2 is the same as Game1 except that for each encryption query the challenger chooses κ1,j←RK′ to construct C1,j=SymEncκ1,j,K1,j, where K0,j=K1,j.(iv)
Game3 is the same as Game2 except that the challenger chooses K0,j←RK to construct C0,j=SymEnc(κ0,j,K0,j).(v)
Game4 is the same as Game3 except that the challenger chooses K1,j←RK to construct C1,j=SymEnc(κ1,j,K1,j). The indistinguishability among Game0, Game1, and Game2 relies on the MS-security of BE. By using hybrid arguments, we show the indistinguishability between Game2 and Game3 (Game3 and Game4), which relies on the one-time CPA security of the underlying symmetric key encryption. It is easy to check that the adversary has no advantage in Game4. More details are shown in Appendix B.


## 4.1. General Construction

Theorem 2.
For any PPT adversaryA which can make at most qkey=qkeyλ key generation queries and qEnc=qEncλ encryption queries with running time t′, there exists an algorithm B with about the same running time as A, such that(5)AdvA,BEMAλ≤qEnc·AdvB,BEAλ.Proof.
The proof proceeds via the following games.(i)
Game0: Game0 is the real MA experiment except the following differences. When the adversary adaptively makes encryption query for set Sj, the challenger responds with EncSj,PK=Hdrj,K0,j, where j∈1,qEnc.(ii)
Game1: Game1 is identical to Game0 except that the challenger replies the encryption queries with Hdrj,K1,j for j∈1,qEnc, where Hdrj,K0,j←EncSj,PK,K1,j←RK∗ and K∗ denotes the key space. Now we construct a series of subgames 0,ι for ι=0,…,qEnc to prove the indistinguishability between Game0 and Game1. (i)
Game0,1. Game0,1 is the same as Game0 except that the challenger chooses K1,1←RK∗ to construct challenge (Hdr1,K1,1) for the first encryption query S1.(ii)
Game0,ι. Game0,ι is the same as Game0,ι-1 except that the challenger chooses K1,ι←RK∗ to construct challenge (Hdrι,K1,ι) for the ιth encryption query Sι, where ι∈1,qEnc. Let Game0,ι=1 denote the event that the adversary outputs 1 in Game0,ι. Note that Game0,0 and Game0,qEnc are identical to Game0 and Game1, respectively. Thus,(6)AdvA,BEMAλ≔Pr⁡ExpA,BEMAλ=1-12=12·Pr⁡ExpA,BEMAλ=0∣b=0+12·Pr⁡ExpA,BEMAλ=1∣b=1-12=12·Pr⁡ExpA,BEMAλ=1∣b=1-1-Pr⁡ExpA,BEMAλ=0∣b=0=12·Pr⁡ExpA,BEMAλ=1∣b=1-Pr⁡ExpA,BEMAλ=1∣b=0=12·Pr⁡Game1=1-Pr⁡Game0=1=12·Pr⁡Game0,qEnc=1-Pr⁡Game0,0=1=12·Pr⁡Game0,qEnc=1-Pr⁡Game0,qEnc-1=1+Pr⁡Game0,qEnc-1=1-Pr⁡Game0,qEnc-2=1+⋯+Pr⁡Game0,1=1-Pr⁡Game0,0=1≤12·∑ι=1qEncPr⁡Game0,ι=1-Pr⁡Game0,ι-1=1.Next, we show that PrGame0,ι=1-Pr⁡Game0,ι-1=1 is negligible, for ι∈1,qEnc. That is, if there exists a PPT adversary A1 which can distinguish the adjacent games for some ι, we can construct a PPT algorithm B which can break the adaptive security of the underlying scheme.
Claim
G
a
m
e
0
,
ι
-
1
t
o
G
a
m
e
0
,
ι
. For any PPT adversary A1 which can make at most qkey=qkeyλ key generation queries and qEnc=qEncλ encryption queries with running time t′, there exists algorithm B with about the same running time as A1, such that(7)12·Pr⁡Game0,ι=1-Pr⁡Game0,ι-1=1=AdvB,BEAλ.Proof. B simulates the experiment as follows. (i)
The challenger runsSetupn,l and sends PK to B which will send PK to A1.(ii)
A1 adaptively makes key generation queries for user index i.(iii)
B sends user index i to the challenger which runs KeyGeni,SK and sends back the secret key di for user i. Then B sends di to A1.(iv)
A1 adaptively makes encryption queries for Sj, where j denotes the jth query.
(a)
Ifj∈1,ι-1, B runs EncSj,PK=Hdrj,K0,j and chooses K1,j←RK∗ and sends Hdrj,K1,j to A1.(b)
Ifj∈ι+1,qEnc, B runs EncSj,PK=Hdrj,K0,j and sends Hdrj,K0,j to A1.(c)
Ifj=ι, B sends Sι to the challenger which then chooses b←R{0,1} and sends back Cι∗=Hdrι,Kb,ι where K1,ι←RK∗,Hdrι,K0,ι←EncSι,PK. Next B sends Cι∗ to A1.(v)
A1 outputs b′. If b′=b, B outputs 1, otherwise, 0. Observe that if b=1, A1’s view is identical to that of Game0.ι. Otherwise A1’s view is identical to that of Game0.ι-1. Thus(8)AdvB,BEA≔Pr⁡ExpB,BEAλ=1-12=12·Pr⁡ExpB,BEAλ=1∣b=1+12·Pr⁡ExpB,BEAλ=0∣b=0-12=12·Pr⁡ExpB,BEAλ=1∣b=1-1-Pr⁡ExpB,BEAλ=0∣b=0=12·Pr⁡ExpB,BEAλ=1∣b=1-Pr⁡ExpB,BEAλ=1∣b=0=12·Pr⁡Game0,ι=1-Pr⁡Game0,ι-1=1.Hence we have(9)AdvA,BEMAλ≤qEnc·AdvB,BEAλ,which completes the proof of Theorem 2.


## 4.2. MS-Secure Broadcast Encryption Based on BDHE Assumption

To reduce the reduction loss, we investigate Gentry-Waters broadcast encryption [8] in the MA setting. First we briefly recall the semistatically secure broadcast encryption scheme in [8]. Let G(λ,n) be a PPT algorithm which takes as input the security parameter λ and the number of users n and generates the description of group parameter (G,GT,e,p), where G,GT denotes the group of prime order p=pλ,n and e is the bilinear map.S
e
t
u
p
(
n
). (G,GT,e)←RG(λ,n), g,h1,…,hn←RGn+1, where g,h1,…,hn are generators of G and α←RZp. Set(10)PK=G,GT,e;g,eg,gα,h1,…,hn,(11)SK=gα. Output PK,SK.K
e
y
G
e
n
(
i
,
S
K
). Choose ri←RZp and output user i’s private key(12)di=di,0,di,1,…,di,i-1,di,i,di,i+1,…,di,n=g-ri,h1ri,…,hi-1ri,gαhiri,hi+1ri,…,hnri.E
n
c
(
S
,
P
K
). Choose t←RZp and compute C1=gt,C2=∏j∈Shjt. Set(13)Hdr=gt,∏j∈Shjt,(14)K=eg,gα·t. Output (Hdr,K).D
e
c
(
S
,
i
,
d
i
,
H
d
r
,
P
K
). If i∈S, parse di as (di,0,…,di,n) and Hdr as (C1,C2) and output(15)K=edi,i·∏j∈S∖idi,j,C1·edi,0,C2.Theorem 3.
For any PPT adversaryA which can make at most qkey=qkey(λ) key generation queries, qEnc=qEnc(λ) encryption queries with running time t′, there exists an algorithm B with about the same running time as A, such that(16)AdvA,BEMSλ=AdvG,BBDHEλ.The proof is similar to that of [8] except that we have to deal with multiple challenges in the simulation. Furthermore, to derive a tighter reduction, we need the following lemma which makes use of the random self-reducibility of BDHE.Lemma 4.
There exists an efficient algorithm that takes as inputgs,g,ga,ga2,…,gan,gan+2,…,ga2n,Z for Z=egan,gc and generates many tuples of the form(17)gsj,g,ga,ga2,…,gan,gan+2,…,ga2n,Zj, where Zj=egan,gcj and sj,cj∈Zp.Proof.
Computegsj=gsvj·guj and Zj=Zvj·egan,gauj, where uj,vj←RZp. Let e=c-as mod p. We implicitly set(18)sj=s·vj+ujmodp,cj=asj+evjmodp.Hence, we have(19)Zj=egan,gasjifc=asmodpegan,gasj+evjifc≠asmodp. If e=0, namely, c=as, then cj=asj. If e≠0, namely, c≠as, then cj=asj+evj. Since evj are uniformly distributed, we have cj uniformly distributed over Zp.Next, more details of the concrete proof of Theorem3 can be found in Appendix A.


## 4.3. Transforming MS-Security to MA-Security

In this section, we show that Gentry-Waters transformation still holds in the multichallenge setting, but at the cost of reduction lossqEnc in the advantage of underlying symmetric encryption scheme. First, we briefly recall Gentry-Waters transformation [8]. Let BEMS=(SetupMS,KeyGenMS, EncMS,DecMS) be a MS-secure broadcast system and Πsym=SymSetup,SymEnc,SymDec be a symmetric encryption scheme with key space K′.S
e
t
u
p
(
n
). Run SetupMS(2n)→PK′,SK′. Let s←R0,1n and si denotes ith bit of s. Let PK=PK′ and SK=(SK′,s). Output PK,SK.K
e
y
G
e
n
(
i
,
S
K
). Run KeyGenMS(2i-si,SK′)→di′. Set di=di′,si. Output private key di.E
n
c
(
S
,
P
K
). Generate random S bits: t←ti←R0,1:i∈S and K←RK. Set(20)S0⟵2i-ti:i∈S,EncMSS0,PK′⟶Hdr0,κ0,SymEncκ0,K⟶C0;S1⟵2i-1-ti:i∈S,EncMSS1,PK′⟶Hdr1,κ1,SymEncκ1,K⟶C1;Hdr⟵Hdr0,Hdr1,C0,C1,t.Output (Hdr,K).D
e
c
(
S
,
i
,
d
i
,
H
d
r
,
P
K
). Parse Hdr as Hdr0,Hdr1,C0,C1,t and di as di′,si. Set S0 and S1 as above. Run(21)κsi⊕ti⟵DecMSSsi⊕ti,i,di′,Hdrsi⊕ti,PK′,K⟵SymDecκsi⊕ti,Csi⊕ti.Output K.Theorem 5.
For any PPT adversaryA which can make at most qkey=qkey(λ) key generation queries and qEnc=qEnc(λ) encryption queries with running time t′, there exist algorithms A1,A2,A3, and A4, each with about the same running time as A, such that(22)AdvA,BE,nMAλ≤AdvA1,BE,2nMSλ+AdvA2,BE,2nMSλ+qEnc·AdvA3,ΠsymCPAλ+qEnc·AdvA4,ΠsymCPAλ.Notice thatAdvB,ΠsymCPAλ denotes the advantage of Πsym=(SymSetup, SymEnc,SymDec), which is defined by the following one-time symmetric key IND-CPA experiment described in Table 3.Table 3
IND-CPA experiment.
E
x
p
A
,
Π
s
y
m
C
P
A
(
λ
)
b
⟵
R
0,1;
k
⟵
S
y
m
S
e
t
u
p
1
λ;
b
′
⟵
A
O
E
n
c
′
k
,
⋅;
Ifb′=b, return 1; otherwise, 0.During the experiment,A takes the security parameter and the description of Πsym as input and can make only one encryption query to encryption oracle O′Enc(k,·). More precisely, A chooses a pair of plaintexts (m0,m1) of the same length as the query and O′Enc(k,·) returns SymEnc(k,mb) as the challenge ciphertext.We say the symmetric key encryption schemeΠsym is one-time CPA-secure if, for any PPT adversary A, the advantage(23)AdvA,ΠsymCPA≔Pr⁡ExpA,ΠsymCPAλ=1-12 is negligible in λ, where the probability is taken over the random coins used in the experiment, as well as the random coins used by A.Proof of Sketch.The main idea of the proof is similar to that of [8] except that we need to deal with multiple challenges, which incurs a reduction loss in the advantage of symmetric key encryption scheme. More precisely, we need to prove the indistinguishability of the following games.(i)
Game0 is identical to ExpA,BEMAλ.(ii)
Game1 is the same as Game0 except that for each encryption query the challenger chooses κ0,j←RK′ to construct C0,j=SymEncκ0,j,K0,j, where K0,j=K1,j.(iii)
Game2 is the same as Game1 except that for each encryption query the challenger chooses κ1,j←RK′ to construct C1,j=SymEncκ1,j,K1,j, where K0,j=K1,j.(iv)
Game3 is the same as Game2 except that the challenger chooses K0,j←RK to construct C0,j=SymEnc(κ0,j,K0,j).(v)
Game4 is the same as Game3 except that the challenger chooses K1,j←RK to construct C1,j=SymEnc(κ1,j,K1,j). The indistinguishability among Game0, Game1, and Game2 relies on the MS-security of BE. By using hybrid arguments, we show the indistinguishability between Game2 and Game3 (Game3 and Game4), which relies on the one-time CPA security of the underlying symmetric key encryption. It is easy to check that the adversary has no advantage in Game4. More details are shown in Appendix B.


## 5. Removeq-Type Assumption

In this section, we show how to remove theq-type assumption of the MS-secure Gentry-Waters scheme in Section 4 by using Hofheinz-Koch-Striecks techniques [19], where the original Gentry-Waters scheme is lifted to composite order groups.LetG(λ,4) be a composite-order group generator which generates group parameters (G,GT,N,e,g, g1,g2,g3,g4), where e:G×G→GT is a nondegenerate bilinear map and G,GT are cyclic groups of order N and N is the product of different primes p1,p2,p3, and p4, and let g be the generator of group G and gi, for i∈1,4, be the random generators of subgroups Gp1,Gp2,Gp3,Gp4 of orders p1,p2,p3,p4, respectively.LetUH be a family of universal hash functions H:GT→0,1τ with the property that for any nontrivial subgroup GT′⊆GT and for H←UH,X←GT′ and U←0,1τ, we have SDH,HX,H,U=O(2-τ). In addition, the resulting scheme relies on the following assumptions [19].Dual System Assumption 1 (DS1). For any PPT adversary A, the advantage function (24)AdvADS1λ≔Pr⁡AD,T0=1-Pr⁡AD,T1=1is negligible in λ, where (25)G,GT,N,e,g,gii⟵Gλ,4;D≔G,GT,N,e,g,g1,g3,g4;T0⟵RGp1,T1⟵RGp1p2.Dual System Assumption 2 (DS2). For any PPT adversary A, the advantage function(26)AdvADS2λ≔Pr⁡AD,T0=1-Pr⁡AD,T1=1is negligible in λ, where (27)G,GT,N,e,g,gii⟵Gλ,4;D≔G,GT,N,e,g,g1,g4,g1,2,g2,3;g1,2⟵RGp1p2,g2,3⟵RGp2p3;T0⟵RGp1p2,T1⟵RGp1p3.Dual System Assumption 3 (DS3). For any PPT adversary A, the advantage function(28)AdvADS3λ≔Pr⁡AD,T^0,T~0=1-Pr⁡AD,T^1,T~1=1is negligible inλ, where (29)G,GT,N,e,g,gii⟵Gλ,4;D≔G,GT,N,e,g,gii,g2xX^4,g2yY^4,g3xX~4,g3yY~4;X^4,X~4,Y^4,Y~4⟵RGp4,x,y⟵ZN∗,γ′⟵ZN∗;T^0=g2xy,T^1=g2xy+γ′;T~0=g3xy,T~1=g3xy+γ′.Dual System Bilinear DDH Assumption (DS-BDDH). For any PPT adversary A, the advantage function(30)AdvADS-BDDHλ≔Pr⁡AD,T0=1-Pr⁡AD,T1=1is negligible in λ, where (31)G,GT,N,e,g,gii⟵Gλ,4;D≔G,GT,N,e,g,gii,g1a,g2a,g2b,g2,4,g2,4b,g2,4c;T0=eg2,g2abc,T1=eg2,g2z;g2,4⟵RGp2p4,a,b,c,z⟵ZN∗.


### 5.1. Construction

S
e
t
u
p
(
n
,
n
). Generate α,ω1,…,ω2n←RZN and compute g1,g1ω1,…,g1ω2n∈Gp12n+1. Set h←RGN, generate R4,1,…,R4,2n←RGp42n, and compute h1,…,h2n=hω1·R4,1,…,hω2n·R4,2n. Set(32)mpk=g1,g1ω1,…,g1ω2n,g4,h,eg1,hα,h1,…,h2n,(33)msk=hα. Output (mpk,msk).K
e
y
G
e
n
(
u
,
m
s
k
). Take an index u∈1,n and the master key msk as input. Set ru←RZN, generate R4,1′,…,R4,2n′←RGp42n, and compute K0=hru,K1=h1ru·R4,1′,…,K2n=h2nru·R4,2n′ and output a user secret key(34)sku=K0,K1,…,msk·K2u-1,K2u+1,…,K2n=hru,h1ru·R′4,1,…,msk·h2u-1ru·R4,2u-1′,h2u+1ru·R4,2u+1′,…,h2nru·R4,2n′.Note that K2u is not used in sku.E
n
c
(
S
,
m
p
k
). Take a set S⊆1,n as well as a master public key mpk as input. We denote S as a binary string; that is, S=s1⋯sn, where su∈{0,1} and u∈1,n. That is, su=1 if user u is in S. Otherwise, su=0. Generate t←RZN and output(35)Hdr=C0,C1=g1t,∏j=1ng1ω2j-sjt,(36)K=Heg1,hαt.D
e
c
(
S
,
u
,
s
k
u
,
H
d
r
,
m
p
k
). If u∈S, parse sku as K0,K1,…,msk·K2u-1,K2u+1,…,K2n and Hdr as C0,C1 and output(37)K=HeC0,msk·∏j=1nK2j-sjeC1,K0.Correctness.
(38)
e
C
0
,
m
s
k
·
∏
j
=
1
n
K
2
j
-
s
j
e
C
1
,
K
0
=
e
g
1
t
,
m
s
k
·
∏
j
=
1
n
h
2
j
-
s
j
r
u
·
R
4,2
j
-
s
j
′
e
∏
j
=
1
n
g
1
ω
2
j
-
s
j
,
h
t
·
r
u
=
e
g
1
t
,
h
α
·
e
g
1
,
∏
j
=
1
n
h
2
j
-
s
j
t
·
r
u
e
∏
j
=
1
n
g
1
ω
2
j
-
s
j
,
h
t
·
r
u
=
e
g
1
,
h
α
t
·
e
g
1
,
∏
j
=
1
n
h
ω
2
j
-
s
j
t
·
r
u
e
∏
j
=
1
n
g
1
ω
2
j
-
s
j
,
h
t
·
r
u
=
e
g
1
,
h
α
t
.


### 5.2. Security Proof

Theorem 6.
For any PPT adversaryA which can make at most qkey=qkeyλ key generation queries and qEnc=qEncλ encryption queries with running time t′, there exist algorithm B1 on DS1, B2 on DS2, B3 on DS3, and B4 on DS-BDDH with running time t′+Onλcqkey+qEnc, respectively, for some constant c∈N, such that(39)AdvA,BEMAλ≤AdvB1DS1λ+2n·AdvB2DS2λ+n·AdvB3DS3λ+AdvB4DS-BDDH+qEnc·O2-τ.The proof follows that of [19] and proceeds via a series of games described in Appendix C, where the user set S is considered as a special kind of identity id.The main difference between games is presented in Table4. Random function families, auxiliary secret key generation, auxiliary encryption function, semifunctional user secret keys, pseudo-normal ciphertexts, and semifunctional ciphertexts are defined as follows. More details can be found in Table 4.Table 4
Sequence of games, where a dash(−) means the same as in the previous game. Note that user setS∗ and user identity u are interpreted as id∗ and id, respectively.
G
a
m
e
Challenge ciphertexts for identityS∗
User secret keys for identityu∈1,n
0
E
n
c
(
S
∗
,
m
p
k
)
K
e
y
G
e
n
u
,
m
s
k
1
E
n
c
¯
S
∗
,
m
p
k
,
g
1,2
,
m
s
k
K
e
y
G
e
n
¯
u
,
m
s
k
,
K
2,i, 0
E
n
c
¯
-
,
-
,
g
1,2
,
m
s
k
⋅
R
F
^
i
-
1
i
d
∗
i
-
1
KeyGen¯u,msk⋅RF^i-1idi-1⋅RF~i-1idi-1,K
2,i, 1
ifidi∗=0: Enc¯-,-,g1,2,msk⋅RF^i-1id∗i-1
KeyGen¯u,msk⋅RF^i-1idi-1⋅RF~i-1idi-1,K
ifidi∗=1: Enc¯-,-,g1,3,msk⋅RF~i-1id∗i-1
2,i, 2
ifidi∗=0: Enc¯-,-,g1,2,msk⋅RF^iid∗i
KeyGen¯u,msk⋅RF^iidi⋅RF~iidi,K
ifidi∗=1: Enc¯-,-,g1,3,msk⋅RF~iid∗i
3
E
n
c
¯
-
,
-
,
g
1,2
,
m
s
k
⋅
R
F
^
n
i
d
∗
K
e
y
G
e
n
¯
u
,
m
s
k
⋅
R
F
^
n
i
d
⋅
R
F
~
n
i
d
,
K
4
E
n
c
¯
-
,
-
,
g
1,2
,
m
s
k
⋅
R
F
^
n
i
d
∗, Kb⟵R0,1τ
K
e
y
G
e
n
¯
u
,
m
s
k
⋅
R
F
^
n
i
d
⋅
R
F
~
n
i
d
,
K(i) Random Function Families. In our scheme each user index u∈1,n is interpreted as n-bit binary string u=0⋯010⋯0, where only u-th bit is 1. Both user index u and user set S are denoted as identity id. Let idi≔id1⋯idi be i-bit prefix of id and denote IDi≔0,1i. For i∈0,n, define two random functions as follows.(a)
RF^iidi:IDi→Gp2Gp4; idi↦g2g4γ^iidi;
γ^iidi:IDi→Zp2p4∗; idi↦γ^i, where γ^i←RZp2p4∗.(b)
RF~iidi:IDi→Gp3Gp4; idi↦g3g4γ~iidi;
γ~iidi:IDi→Zp3p4∗; idi↦γ~i, where γ~i←RZp3p4∗.(ii) Auxiliary Secret Key Generation
(40)
K
e
y
G
e
n
¯
u
,
m
s
k
,
K
=
K
0
,
K
1
,
…
,
m
s
k
·
K
2
u
-
1
,
K
2
u
+
1
,
…
,
K
2
n
,where K=(K0,K1,K2,…,K2n)∈GN2n+1.(iii) Auxiliary Encryption Function
(41)
E
n
c
¯
S
∗
,
m
p
k
,
g
1
,
m
s
k
=
H
d
r
;
K
=
g
1
t
,
∏
j
=
1
n
g
1
ω
2
j
-
s
j
t
;
H
e
g
1
,
m
s
k
t
,where g1=g1t,g1ω1t,…,g1ω2nt.(iv) Semi-Functional Type-i User Secret Keys
(42)
K
e
y
G
e
n
¯
u
,
m
s
k
·
R
F
^
i
i
d
i
·
R
F
~
i
i
d
i
,
K
=
K
0
,
K
1
,
…
,
m
s
k
·
R
F
^
i
i
d
i
·
R
F
~
i
i
d
i
·
K
2
u
-
1
,
K
2
u
+
1
,
…
,
K
2
n
,where user u=id1⋯idn is denoted as id.(v) Pseudo-Normal Ciphertexts
(43)
E
n
c
¯
S
∗
,
m
p
k
,
g
1,2
,
m
s
k
=
H
d
r
;
K
=
g
1,2
t
,
∏
j
=
1
n
g
1,2
ω
2
j
-
s
j
t
;
H
e
g
1,2
,
m
s
k
t
,where g{1,2}=g1,2t,g1,2ω1t,…,g1,2ω2nt.(vi) Semi-Functional
T
y
p
e
-
∧
,
i
Ciphertexts
(44)
E
n
c
¯
S
∗
,
m
p
k
,
g
1,2
,
m
s
k
·
R
F
^
i
i
d
i
·
R
F
~
i
i
d
i
=
H
d
r
;
K
=
g
1,2
t
,
∏
j
=
1
n
g
1,2
ω
2
j
-
s
j
t
;
H
e
g
1,2
,
m
s
k
·
R
F
^
i
i
d
i
·
R
F
~
i
i
d
i
t
=
g
1,2
t
,
∏
j
=
1
n
g
1,2
ω
2
j
-
s
j
t
;
H
e
g
1,2
,
m
s
k
·
R
F
^
i
i
d
i
t
,where g{1,2}=g1,2t,g1,2ω1t,…,g1,2ω2nt and id denotes S∗=s1⋯sn.(vii) Semi-Functional
T
y
p
e
-
(
~
,
i
)
Ciphertexts
(45)
E
n
c
¯
S
∗
,
m
p
k
,
g
1,3
,
m
s
k
·
R
F
^
i
i
d
i
·
R
F
~
i
i
d
i
=
H
d
r
;
K
=
g
1,3
t
,
∏
j
=
1
n
g
1,3
ω
2
j
-
s
j
t
;
H
e
g
1,3
,
m
s
k
·
R
F
^
i
i
d
i
·
R
F
~
i
i
d
i
t
=
g
1,3
t
,
∏
j
=
1
n
g
1,3
ω
2
j
-
s
j
t
;
H
e
g
1,3
,
m
s
k
·
R
F
~
i
i
d
i
t
,where g{1,3}=g1,3t,g1,3ω1t,…,g1,3ω2nt and id denotes S∗=s1⋯sn.


## 5.1. Construction

S
e
t
u
p
(
n
,
n
). Generate α,ω1,…,ω2n←RZN and compute g1,g1ω1,…,g1ω2n∈Gp12n+1. Set h←RGN, generate R4,1,…,R4,2n←RGp42n, and compute h1,…,h2n=hω1·R4,1,…,hω2n·R4,2n. Set(32)mpk=g1,g1ω1,…,g1ω2n,g4,h,eg1,hα,h1,…,h2n,(33)msk=hα. Output (mpk,msk).K
e
y
G
e
n
(
u
,
m
s
k
). Take an index u∈1,n and the master key msk as input. Set ru←RZN, generate R4,1′,…,R4,2n′←RGp42n, and compute K0=hru,K1=h1ru·R4,1′,…,K2n=h2nru·R4,2n′ and output a user secret key(34)sku=K0,K1,…,msk·K2u-1,K2u+1,…,K2n=hru,h1ru·R′4,1,…,msk·h2u-1ru·R4,2u-1′,h2u+1ru·R4,2u+1′,…,h2nru·R4,2n′.Note that K2u is not used in sku.E
n
c
(
S
,
m
p
k
). Take a set S⊆1,n as well as a master public key mpk as input. We denote S as a binary string; that is, S=s1⋯sn, where su∈{0,1} and u∈1,n. That is, su=1 if user u is in S. Otherwise, su=0. Generate t←RZN and output(35)Hdr=C0,C1=g1t,∏j=1ng1ω2j-sjt,(36)K=Heg1,hαt.D
e
c
(
S
,
u
,
s
k
u
,
H
d
r
,
m
p
k
). If u∈S, parse sku as K0,K1,…,msk·K2u-1,K2u+1,…,K2n and Hdr as C0,C1 and output(37)K=HeC0,msk·∏j=1nK2j-sjeC1,K0.Correctness.
(38)
e
C
0
,
m
s
k
·
∏
j
=
1
n
K
2
j
-
s
j
e
C
1
,
K
0
=
e
g
1
t
,
m
s
k
·
∏
j
=
1
n
h
2
j
-
s
j
r
u
·
R
4,2
j
-
s
j
′
e
∏
j
=
1
n
g
1
ω
2
j
-
s
j
,
h
t
·
r
u
=
e
g
1
t
,
h
α
·
e
g
1
,
∏
j
=
1
n
h
2
j
-
s
j
t
·
r
u
e
∏
j
=
1
n
g
1
ω
2
j
-
s
j
,
h
t
·
r
u
=
e
g
1
,
h
α
t
·
e
g
1
,
∏
j
=
1
n
h
ω
2
j
-
s
j
t
·
r
u
e
∏
j
=
1
n
g
1
ω
2
j
-
s
j
,
h
t
·
r
u
=
e
g
1
,
h
α
t
.


## 5.2. Security Proof

Theorem 6.
For any PPT adversaryA which can make at most qkey=qkeyλ key generation queries and qEnc=qEncλ encryption queries with running time t′, there exist algorithm B1 on DS1, B2 on DS2, B3 on DS3, and B4 on DS-BDDH with running time t′+Onλcqkey+qEnc, respectively, for some constant c∈N, such that(39)AdvA,BEMAλ≤AdvB1DS1λ+2n·AdvB2DS2λ+n·AdvB3DS3λ+AdvB4DS-BDDH+qEnc·O2-τ.The proof follows that of [19] and proceeds via a series of games described in Appendix C, where the user set S is considered as a special kind of identity id.The main difference between games is presented in Table4. Random function families, auxiliary secret key generation, auxiliary encryption function, semifunctional user secret keys, pseudo-normal ciphertexts, and semifunctional ciphertexts are defined as follows. More details can be found in Table 4.Table 4
Sequence of games, where a dash(−) means the same as in the previous game. Note that user setS∗ and user identity u are interpreted as id∗ and id, respectively.
G
a
m
e
Challenge ciphertexts for identityS∗
User secret keys for identityu∈1,n
0
E
n
c
(
S
∗
,
m
p
k
)
K
e
y
G
e
n
u
,
m
s
k
1
E
n
c
¯
S
∗
,
m
p
k
,
g
1,2
,
m
s
k
K
e
y
G
e
n
¯
u
,
m
s
k
,
K
2,i, 0
E
n
c
¯
-
,
-
,
g
1,2
,
m
s
k
⋅
R
F
^
i
-
1
i
d
∗
i
-
1
KeyGen¯u,msk⋅RF^i-1idi-1⋅RF~i-1idi-1,K
2,i, 1
ifidi∗=0: Enc¯-,-,g1,2,msk⋅RF^i-1id∗i-1
KeyGen¯u,msk⋅RF^i-1idi-1⋅RF~i-1idi-1,K
ifidi∗=1: Enc¯-,-,g1,3,msk⋅RF~i-1id∗i-1
2,i, 2
ifidi∗=0: Enc¯-,-,g1,2,msk⋅RF^iid∗i
KeyGen¯u,msk⋅RF^iidi⋅RF~iidi,K
ifidi∗=1: Enc¯-,-,g1,3,msk⋅RF~iid∗i
3
E
n
c
¯
-
,
-
,
g
1,2
,
m
s
k
⋅
R
F
^
n
i
d
∗
K
e
y
G
e
n
¯
u
,
m
s
k
⋅
R
F
^
n
i
d
⋅
R
F
~
n
i
d
,
K
4
E
n
c
¯
-
,
-
,
g
1,2
,
m
s
k
⋅
R
F
^
n
i
d
∗, Kb⟵R0,1τ
K
e
y
G
e
n
¯
u
,
m
s
k
⋅
R
F
^
n
i
d
⋅
R
F
~
n
i
d
,
K(i) Random Function Families. In our scheme each user index u∈1,n is interpreted as n-bit binary string u=0⋯010⋯0, where only u-th bit is 1. Both user index u and user set S are denoted as identity id. Let idi≔id1⋯idi be i-bit prefix of id and denote IDi≔0,1i. For i∈0,n, define two random functions as follows.(a)
RF^iidi:IDi→Gp2Gp4; idi↦g2g4γ^iidi;
γ^iidi:IDi→Zp2p4∗; idi↦γ^i, where γ^i←RZp2p4∗.(b)
RF~iidi:IDi→Gp3Gp4; idi↦g3g4γ~iidi;
γ~iidi:IDi→Zp3p4∗; idi↦γ~i, where γ~i←RZp3p4∗.(ii) Auxiliary Secret Key Generation
(40)
K
e
y
G
e
n
¯
u
,
m
s
k
,
K
=
K
0
,
K
1
,
…
,
m
s
k
·
K
2
u
-
1
,
K
2
u
+
1
,
…
,
K
2
n
,where K=(K0,K1,K2,…,K2n)∈GN2n+1.(iii) Auxiliary Encryption Function
(41)
E
n
c
¯
S
∗
,
m
p
k
,
g
1
,
m
s
k
=
H
d
r
;
K
=
g
1
t
,
∏
j
=
1
n
g
1
ω
2
j
-
s
j
t
;
H
e
g
1
,
m
s
k
t
,where g1=g1t,g1ω1t,…,g1ω2nt.(iv) Semi-Functional Type-i User Secret Keys
(42)
K
e
y
G
e
n
¯
u
,
m
s
k
·
R
F
^
i
i
d
i
·
R
F
~
i
i
d
i
,
K
=
K
0
,
K
1
,
…
,
m
s
k
·
R
F
^
i
i
d
i
·
R
F
~
i
i
d
i
·
K
2
u
-
1
,
K
2
u
+
1
,
…
,
K
2
n
,where user u=id1⋯idn is denoted as id.(v) Pseudo-Normal Ciphertexts
(43)
E
n
c
¯
S
∗
,
m
p
k
,
g
1,2
,
m
s
k
=
H
d
r
;
K
=
g
1,2
t
,
∏
j
=
1
n
g
1,2
ω
2
j
-
s
j
t
;
H
e
g
1,2
,
m
s
k
t
,where g{1,2}=g1,2t,g1,2ω1t,…,g1,2ω2nt.(vi) Semi-Functional
T
y
p
e
-
∧
,
i
Ciphertexts
(44)
E
n
c
¯
S
∗
,
m
p
k
,
g
1,2
,
m
s
k
·
R
F
^
i
i
d
i
·
R
F
~
i
i
d
i
=
H
d
r
;
K
=
g
1,2
t
,
∏
j
=
1
n
g
1,2
ω
2
j
-
s
j
t
;
H
e
g
1,2
,
m
s
k
·
R
F
^
i
i
d
i
·
R
F
~
i
i
d
i
t
=
g
1,2
t
,
∏
j
=
1
n
g
1,2
ω
2
j
-
s
j
t
;
H
e
g
1,2
,
m
s
k
·
R
F
^
i
i
d
i
t
,where g{1,2}=g1,2t,g1,2ω1t,…,g1,2ω2nt and id denotes S∗=s1⋯sn.(vii) Semi-Functional
T
y
p
e
-
(
~
,
i
)
Ciphertexts
(45)
E
n
c
¯
S
∗
,
m
p
k
,
g
1,3
,
m
s
k
·
R
F
^
i
i
d
i
·
R
F
~
i
i
d
i
=
H
d
r
;
K
=
g
1,3
t
,
∏
j
=
1
n
g
1,3
ω
2
j
-
s
j
t
;
H
e
g
1,3
,
m
s
k
·
R
F
^
i
i
d
i
·
R
F
~
i
i
d
i
t
=
g
1,3
t
,
∏
j
=
1
n
g
1,3
ω
2
j
-
s
j
t
;
H
e
g
1,3
,
m
s
k
·
R
F
~
i
i
d
i
t
,where g{1,3}=g1,3t,g1,3ω1t,…,g1,3ω2nt and id denotes S∗=s1⋯sn.



---

*Source: 1404279-2017-07-03.xml*