# Shorter Decentralized Attribute-Based Encryption via Extended Dual System Groups

Authors: Jie Zhang; Jie Chen; Aijun Ge; Chuangui Ma
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Decentralized attribute-based encryption (ABE) is a special form of multiauthority ABE systems, in which no central authority and global coordination are required other than creating the common reference parameters. In this paper, we propose a new decentralized ABE in prime-order groups by using extended dual system groups. We formulate some assumptions used to prove the security of our scheme. Our proposed scheme is fully secure under the standardk-Lin assumption in random oracle model and can support any monotone access structures. Compared with existing fully secure decentralized ABE systems, our construction has shorter ciphertexts and secret keys. Moreover, fast decryption is achieved in our system, in which ciphertexts can be decrypted with a constant number of pairings.


---

## Body

## 1. Introduction

Attribute-based encryption (ABE), which enables fine-grained access control, was first introduced by Sahai and Waters [1]. Subsequently, Goyal et al. [2] classified ABE as key-policy ABE (KP-ABE) and ciphertext-policy ABE (CP-ABE). In KP-ABE, ciphertexts are associated with a set of attributes and secret keys are associated with access policies, while the opposite is true for CP-ABE. The ciphertext can be decrypted by secret keys if and only if the attributes satisfy the access policy.Over the past decade, there have been a number of ABE schemes [3–9] proposed for supporting fairly expressive policies. However, the classical ABE system has only a single authority, which manages all attributes and issues private keys for all users. This may be unable to meet the requirements of some applications due to the lack of flexibility. There are three major aspects that impact the application value of single authority ABE systems. First, the single authority system failed to achieve the collaboration between different institutions since it cannot verify attributes across different organizations. Second, there exists key escrow problem in single authority system. The authority must be highly trustworthy as it can decrypt any ciphertext. Finally, key generation for all users that relied on a single authority is a huge workload and can easily become a performance bottleneck in the system. Furthermore, failure of the authority affects the whole system.Multiauthority or decentralized ABE [10, 11] systems are put forward to address this issue. Lewko and Waters [11] provided the first fully secure decentralized ABE system. In their system, any party can become an authority by creating a public key. Authorities can issue private keys independently, and some authorities that go wrong will only affect the attributes in their domain and not the system as a whole. In addition, the scheme in [11] supports any monotone access structures.Though the Lewko-Waters decentralized ABE scheme is expressive, the construction is based on composite-order bilinear group. The current research [12] showed that prime-order bilinear groups outperform composite-order groups in terms of both time efficiency and space efficiency. To be specific, elements with 3072 or 3248 bits are required for a 128-bit security level in composite-order groups according to NIST or ECRYPT II recommendations, while elements with 256 bits are sufficient in prime-order groups for the same security level. As for the time efficiency, [12] indicated that a pairing over an elliptic curve of composite order is 254 times slower than over a prime-order elliptic curve for the 128-bit security level. For the above reasons, it is preferable to design schemes on prime-order groups. In a subsequent work by Okamoto and Takashima [13], a decentralized ABE system on prime-order groups was presented by using dual pairing vector spaces [5]. The construction improves the efficiency of decentralized ABE systems, but there is still a significant performance penalty due to the required size of the vectors. Hence, it is worth constructing a more compact decentralized ABE system in prime-order setting.We present a new construction of decentralized ABE by using extended dual system group (EDSG). Our proposed scheme is built on prime-order groups with better space and time efficiency and can be proved fully secure under standardk-Lin assumption in the random oracle model.To prove that full security of decentralized ABE system is a challenging job, even using the powerful dual system encryption methodology [14, 15], [11] used two subgroups for semifunctional space. The first subgroup is used to hide nominal semifunctionality from the attacker’s view by appending blinding factors to each key at a time. The second subgroup is used to avoid leakage of information about the first one by switching the semifunctional components from the first subgroup to it.Dual system groups (DSG) [16] are an attractive tool for simulating composite-order groups in the prime-order setting. In contrast to prior works [17–19], which attempted to maximize the properties satisfied by both composite-order and prime-order groups, the dual system groups seek to investigate the minimal properties needed for the application to dual system encryption. The benefit is that we can obtain more efficient and compact schemes, and that is why our scheme can reduce the size of ciphertext compared with previous work [13]. Unfortunately, we observe that dual system groups in [16] are insufficient for constructing fully secure decentralized ABE since it only has one semifunctional space. To overcome this, we extend the basis of dual system groups from 2k×2k matrix to 3k×3k matrix inspired by [20]. The first k-dimension subspace is the normal space, the next k-dimension subspace is used to construct type 1 semifunctional secret keys, and the last k-dimension subspace is used to construct type 2 semifunctional secret keys. In addition, we also realize the left subgroup indistinguishability, right subgroup indistinguishability 1, and right subgroup indistinguishability 2. These assumptions are used to mimic the effect of the subgroup decision assumption in composite-order groups.The paper is organized as follows. In Section2, we introduced the related works. In Section 3, a brief summary of the relevant concepts in multiauthority CP-ABE and prime-order bilinear groups was presented. In Section 4, we gave our revised definition of dual system groups and realized it in the prime-order setting in Section 5. In Section 6, we gave our decentralized CP-ABE system, outlined the security proof, and discussed its efficiency. In Section 7, we concluded the paper.


## 2. Related Works

Attribute-based encryption was introduced by Sahai and Waters [1], which can encrypt a message for multiple receivers by their attributes, rather than designating recipient in advance. Subsequently, Goyal et al. [2] extended this idea and classified ABE system into two categories: key-policy attribute-based encryption (KP-ABE) and ciphertext-policy attribute-based encryption (CP-ABE). The first fully secure ABE system was presented by Lewko et al. [4]; all ABE systems can only be proved to be selective secure ones before that. In addition, several variants of ABE have been proposed. Ostrovsky et al. [21] showed how to realize negation by incorporating specific revocation schemes into the construction of [2]. Lewko et al. [22] provided a fully secure ABE system which is resilient to continual leakage. With regard to the public parameter optimization problems, large universe ABE system, in which the size of the attribute universe can be exponentially large, was proposed in [23, 24]. The first multiauthority ABE system was introduced in [10] by Chase, which has one central authority (CA) and multiple attribute authorities (AAs). Subsequently, Chase and Chow [25] removed the CA by using a distributed pseudorandom function. Both of [10, 25] can only support AND-gates policy. A multiauthority ABE that supports threshold policy was provided by Lin et al. [26]. CA is not required for their system. However, the authorities are fixed and they must interact with each other during setup. The multiauthority ABE proposed in [10, 25, 26] looked only at the KP-ABE setting. Müller et al. [27] proposed the first multiauthority CP-ABE supported policies written in disjunctive normal form (DNF) with one CA and multiple AAs. The system can be only proved to be secure in generic group model. In addition, all these above systems can only defend selective attacks; that is, the attacker must commit to a target access structure before setup phase. Lewko and Waters [11] first obtained a fully secure multiauthority CP-ABE by using dual system encryption technique [14, 15]. Their system is decentralized; that is, the authorities are equal and with no need for CA and can support any monotone access structures. They proved security under static assumptions in the random oracle model. Liu et al. [28] proposed a multiauthority CP-ABE where there are multiple CAs and AAs. In their system, all of the CAs must work together to issue an identity-related key to the user. They used (n,n) threshold policy to distribute the master secret to prevent the authority decrypting ciphertexts independently. The system can be proved fully secure in the standard model. Scheme [11] is built on the composite-order group, which resulted in low efficiency of the systems. An improvement design was carried out in prime-order bilinear groups in [13]. Recently, Rouselakis and Waters [29] proposed an efficient large universe decentralized ABE system. However, the scheme only achieved static security, in which all queries (about both ciphertexts and secret keys) done by the attacker should be sent to the challenger immediately after seeing the global parameters.In addition, some extension researches on multiauthority ABE have been proposed. Ma et al. [30] presented a multiauthority ABE with traitor tracing. The system is not practical due to infeasible large sizes of public key and ciphertext. Li et al. [31] proposed a multiauthority CP-ABE scheme with accountability, which allows tracing the identity of a misbehaving user who leaked the decryption key to others. The system supported AND-gates policy. A large universe decentralized KP-ABE scheme was proposed in [32]. The system supported any monotone access policy and can be proved as selectively secure in the standard model. Gorasia et al. [33] presented a multiauthority CP-ABE with fast decryption, which only supports threshold policy. Zhong et al. [34] proposed a decentralized CP-ABE scheme with hidden policy. It also supported user revocation but only achieved selective security. An adaptively secure multiauthority CP-ABE scheme with verifiable outsourced decryption was given in [35].


## 3. Preliminaries

Notation. We use s←RS to denote that s is picked randomly from a set S. We denote probabilistic polynomial-time by PPT. [n] denotes the set {1,…,n} for any n∈Z+.


### 3.1. Prime-Order Bilinear Groups and Computational Assumptions

Prime-Order Bilinear Groups. The asymmetric prime-order group generator G takes a security parameter λ as input and outputs (p,G1,G2,GT,g1,g2,e), where G1, G2, and GT are cyclic groups of prime order p, g1, g2 are generators of G1, G2, respectively, e:G1×G2→GT is an effective computable nondegenerate bilinear pairing, that is, e(g1a,g2b)=e(g1,g2)ab, and gT=e(g1,g2)≠1.Assumption 1 (k-Lin: the k-linear assumption in G1).
For any PPT adversaryA, the advantage of A is negligible in λ: (1)AdvAk-Lin≔PrAD,T0=1-PrAD,T1=1,where(2)D≔p,G1,G2,GT,e,g1,g2,g1a1,…,g1ak,g1ak+1,g1a1s1,…,g1aksk,T0≔g1ak+1s1+⋯+sk,T1≔g1ak+1s1+⋯+sk+sk+1,s1,…,sk⟵Zp,a1,…,ak,ak+1,sk+1⟵Zp∗.Assumption 2 ((k,l)-LLin: the k,l-lifted linear assumption in G1).
For any PPT adversaryA, the advantage of A is negligible in λ: (3)AdvAk,l-LLin≔PrAD,T0=1-PrAD,T1=1,where (4)D≔p,G1,G2,GT,e,g1,g2,g1a1,…,g1ak,g1bi,ji∈l,j∈k,g1a1s1,…,g1aksk,T0≔g1bi,1s1+⋯+bi,kski∈l,T1≔g1bi,1s1+⋯+bi,ksk+sk+ii∈l,s1,…,sk⟵Zp,a1,…,ak,bi,j,sk+i⟵Zp∗,i∈l,j∈k.Lemma 3 (see [20]).
For any PPT adversaryA, there exists an adversary B such that (5)AdvAk,l-LLin⩽l·AdvBk-Lin+1p-1.


### 3.2. Multiauthority CP-ABE

#### 3.2.1. Definition

In this paper, we used the definition of multiauthority CP-ABE and security model presented in [11]. We let Ui denote the attribute set managed by AAi and U=⋃‍Ui denote the universe of attributes. For i≠j, we assume that Ui∩Uj=Φ. A multiauthority CP-ABE system consists of the following five algorithms:GlobalSetup
(
1
λ
)
→
G
P. This algorithm takes as input a security parameter λ and outputs the global public parametersGP.Authority Setup
G
P
→
A
P
K
i
,
A
S
K
i. This algorithm is run by attribute authority AAi. It takes as input global parametersGP and outputs its own public key APKi and secret key ASKi.KeyGen
(
G
P
,
G
I
D
,
A
S
K
j
,
a
t
t
i
)
→
S
K
G
I
D
,
i. This algorithm is run by AAj. It takes as inputGP, ASKj, an identityGID, and an attribute atti belonging to AAj and returns a secret key SKGID,i.Enc
(
G
P
,
(
M
,
ρ
)
,
{
A
P
K
i
}
,
m
)
→
C
T. This algorithm takes as inputGP, an access matrix (M,ρ), the set of public keys for relevant authorities, and a message m and outputs a ciphertextCT.Dec
(
C
T
,
{
S
K
G
I
D
,
i
}
,
G
P
)
→
m. This algorithm takes as inputGP, {SKGID,i}, andCT. If the collection of attributes satisfies the access policy, it outputs the message m; otherwise, it outputs ⊥.


#### 3.2.2. Security Model

The security of multiauthority CP-ABE is defined by the following game run between a challengerB and an adversary A.Setup. The challenger B executesGlobalSetup andAuthority Setup algorithm. It givesGP and {APKi} to the adversary A. For corrupt authorities, B also gives the corresponding {ASKi} to A.Key Query Phase 1. In this phase, A makes key queries by submitting (GID,atti) to B, where atti belonged to uncorrupted authorities. B returns SKGID,i to A.Challenge. A submits two equal-length messages m0, m1 and an access policy (M,ρ) with the following constraint. We let V denote the subset of attributes controlled by corrupt AAs. For each identityGID, VGID denotes the subset of attributes atti which A has queried. For eachGID, we require that V∪VGID cannot satisfy (M,ρ). B randomly chooses β∈{0,1} and encrypts mβ under (M,ρ). It sends the ciphertext to A.Key Query Phase 2. A continually queries B as in phase 1 in the same constraint.Guess. A outputs a guess β′ for β.The adversary’s advantage is defined to be|Pr⁡[β′=β]-1/2|.Definition 4.
A multiauthority CP-ABE scheme is secure if, for all PPT adversaries, the advantage is negligible in the above security game.


## 3.1. Prime-Order Bilinear Groups and Computational Assumptions

Prime-Order Bilinear Groups. The asymmetric prime-order group generator G takes a security parameter λ as input and outputs (p,G1,G2,GT,g1,g2,e), where G1, G2, and GT are cyclic groups of prime order p, g1, g2 are generators of G1, G2, respectively, e:G1×G2→GT is an effective computable nondegenerate bilinear pairing, that is, e(g1a,g2b)=e(g1,g2)ab, and gT=e(g1,g2)≠1.Assumption 1 (k-Lin: the k-linear assumption in G1).
For any PPT adversaryA, the advantage of A is negligible in λ: (1)AdvAk-Lin≔PrAD,T0=1-PrAD,T1=1,where(2)D≔p,G1,G2,GT,e,g1,g2,g1a1,…,g1ak,g1ak+1,g1a1s1,…,g1aksk,T0≔g1ak+1s1+⋯+sk,T1≔g1ak+1s1+⋯+sk+sk+1,s1,…,sk⟵Zp,a1,…,ak,ak+1,sk+1⟵Zp∗.Assumption 2 ((k,l)-LLin: the k,l-lifted linear assumption in G1).
For any PPT adversaryA, the advantage of A is negligible in λ: (3)AdvAk,l-LLin≔PrAD,T0=1-PrAD,T1=1,where (4)D≔p,G1,G2,GT,e,g1,g2,g1a1,…,g1ak,g1bi,ji∈l,j∈k,g1a1s1,…,g1aksk,T0≔g1bi,1s1+⋯+bi,kski∈l,T1≔g1bi,1s1+⋯+bi,ksk+sk+ii∈l,s1,…,sk⟵Zp,a1,…,ak,bi,j,sk+i⟵Zp∗,i∈l,j∈k.Lemma 3 (see [20]).
For any PPT adversaryA, there exists an adversary B such that (5)AdvAk,l-LLin⩽l·AdvBk-Lin+1p-1.


## 3.2. Multiauthority CP-ABE

### 3.2.1. Definition

In this paper, we used the definition of multiauthority CP-ABE and security model presented in [11]. We let Ui denote the attribute set managed by AAi and U=⋃‍Ui denote the universe of attributes. For i≠j, we assume that Ui∩Uj=Φ. A multiauthority CP-ABE system consists of the following five algorithms:GlobalSetup
(
1
λ
)
→
G
P. This algorithm takes as input a security parameter λ and outputs the global public parametersGP.Authority Setup
G
P
→
A
P
K
i
,
A
S
K
i. This algorithm is run by attribute authority AAi. It takes as input global parametersGP and outputs its own public key APKi and secret key ASKi.KeyGen
(
G
P
,
G
I
D
,
A
S
K
j
,
a
t
t
i
)
→
S
K
G
I
D
,
i. This algorithm is run by AAj. It takes as inputGP, ASKj, an identityGID, and an attribute atti belonging to AAj and returns a secret key SKGID,i.Enc
(
G
P
,
(
M
,
ρ
)
,
{
A
P
K
i
}
,
m
)
→
C
T. This algorithm takes as inputGP, an access matrix (M,ρ), the set of public keys for relevant authorities, and a message m and outputs a ciphertextCT.Dec
(
C
T
,
{
S
K
G
I
D
,
i
}
,
G
P
)
→
m. This algorithm takes as inputGP, {SKGID,i}, andCT. If the collection of attributes satisfies the access policy, it outputs the message m; otherwise, it outputs ⊥.


### 3.2.2. Security Model

The security of multiauthority CP-ABE is defined by the following game run between a challengerB and an adversary A.Setup. The challenger B executesGlobalSetup andAuthority Setup algorithm. It givesGP and {APKi} to the adversary A. For corrupt authorities, B also gives the corresponding {ASKi} to A.Key Query Phase 1. In this phase, A makes key queries by submitting (GID,atti) to B, where atti belonged to uncorrupted authorities. B returns SKGID,i to A.Challenge. A submits two equal-length messages m0, m1 and an access policy (M,ρ) with the following constraint. We let V denote the subset of attributes controlled by corrupt AAs. For each identityGID, VGID denotes the subset of attributes atti which A has queried. For eachGID, we require that V∪VGID cannot satisfy (M,ρ). B randomly chooses β∈{0,1} and encrypts mβ under (M,ρ). It sends the ciphertext to A.Key Query Phase 2. A continually queries B as in phase 1 in the same constraint.Guess. A outputs a guess β′ for β.The adversary’s advantage is defined to be|Pr⁡[β′=β]-1/2|.Definition 4.
A multiauthority CP-ABE scheme is secure if, for all PPT adversaries, the advantage is negligible in the above security game.


## 3.2.1. Definition

In this paper, we used the definition of multiauthority CP-ABE and security model presented in [11]. We let Ui denote the attribute set managed by AAi and U=⋃‍Ui denote the universe of attributes. For i≠j, we assume that Ui∩Uj=Φ. A multiauthority CP-ABE system consists of the following five algorithms:GlobalSetup
(
1
λ
)
→
G
P. This algorithm takes as input a security parameter λ and outputs the global public parametersGP.Authority Setup
G
P
→
A
P
K
i
,
A
S
K
i. This algorithm is run by attribute authority AAi. It takes as input global parametersGP and outputs its own public key APKi and secret key ASKi.KeyGen
(
G
P
,
G
I
D
,
A
S
K
j
,
a
t
t
i
)
→
S
K
G
I
D
,
i. This algorithm is run by AAj. It takes as inputGP, ASKj, an identityGID, and an attribute atti belonging to AAj and returns a secret key SKGID,i.Enc
(
G
P
,
(
M
,
ρ
)
,
{
A
P
K
i
}
,
m
)
→
C
T. This algorithm takes as inputGP, an access matrix (M,ρ), the set of public keys for relevant authorities, and a message m and outputs a ciphertextCT.Dec
(
C
T
,
{
S
K
G
I
D
,
i
}
,
G
P
)
→
m. This algorithm takes as inputGP, {SKGID,i}, andCT. If the collection of attributes satisfies the access policy, it outputs the message m; otherwise, it outputs ⊥.


## 3.2.2. Security Model

The security of multiauthority CP-ABE is defined by the following game run between a challengerB and an adversary A.Setup. The challenger B executesGlobalSetup andAuthority Setup algorithm. It givesGP and {APKi} to the adversary A. For corrupt authorities, B also gives the corresponding {ASKi} to A.Key Query Phase 1. In this phase, A makes key queries by submitting (GID,atti) to B, where atti belonged to uncorrupted authorities. B returns SKGID,i to A.Challenge. A submits two equal-length messages m0, m1 and an access policy (M,ρ) with the following constraint. We let V denote the subset of attributes controlled by corrupt AAs. For each identityGID, VGID denotes the subset of attributes atti which A has queried. For eachGID, we require that V∪VGID cannot satisfy (M,ρ). B randomly chooses β∈{0,1} and encrypts mβ under (M,ρ). It sends the ciphertext to A.Key Query Phase 2. A continually queries B as in phase 1 in the same constraint.Guess. A outputs a guess β′ for β.The adversary’s advantage is defined to be|Pr⁡[β′=β]-1/2|.Definition 4.
A multiauthority CP-ABE scheme is secure if, for all PPT adversaries, the advantage is negligible in the above security game.


## 4. Extended Dual System Groups

(i)
SampP
(
1
λ
,
1
n
): output:
(a)
Public parameter,pp, contains group description(G,H,GT), a nondegenerate bilinear map e:G×H→GT, a linear map μ defined on H, and some additional parameters forSampG andSampH.
(b)
Secret parameter,sp, contains h^∗,h~∗∈H (where h^∗,h~∗≠1), and some parameters for SampG^, SampH^, SampG~, and SampH~.
(ii)
SampGT: Im(μ) →GT.
(iii)
SampG
(
p
p
): output g→=g0,g1,…,gn∈Gn+1.
(iv)
SampH
(
p
p
): output h→=(h0,h1,…,hn)∈Hn+1.
(v)
S
a
m
p
G
^
(
p
p
,
s
p
): output g→^=(g^0,g^1,…,g^n)∈Gn+1.
(vi)
S
a
m
p
H
^
(
p
p
,
s
p
): output h→^=(h^0,h^1,…,h^n)∈Hn+1.
(vii)
S
a
m
p
G
~
(
p
p
,
s
p
): output g→~=(g~0,g~1,…,g~n)∈Gn+1.
(viii)
S
a
m
p
H
~
(
p
p
,
s
p
): output h→~=(h~0,h~1,…,h~n)∈Hn+1.The first four algorithms are used for normal ciphertexts and secret keys in the real system, while the remaining are only used for semifunctional ones in the security proof. We use SampG0 to indicate the first element of g→, that is, g0.Correctness. It needs to meet the following conditions.(Projective). For h∈H and a random variable s, SampGT(μ(h);s)=e(SampG0(pp;s),h).(Associative). For all g→←SampG(pp) and h→←SampH(pp), (6)eg0,hi=egi,h0,i=1,…,n.Security. It needs to meet the following conditions.(Orthogonality)
(i)
μ
(
h
^
∗
)
=
μ
(
h
~
∗
)
=
1.
(ii)
e
(
g
^
0
,
h
~
∗
)
=
1.
(iii)
e
(
g
~
0
,
h
^
∗
)
=
1.(Nondegeneracy). For all g^0←SampG^0(pp,sp) and g~0←SampG~0(pp,sp), e(g^0,h^∗) and e(g~0,h~∗) are distributed uniformly over GT.(
H
-
S
u
b
g
r
o
u
p
). The output of SampH(pp) is distributed uniformly over a subgroup of Hn+1.(Left Subgroup Indistinguishability). For any PPT adversary A, the advantage of A is negligible in λ: (7)AdvALSλ≔Pr⁡App,g→=1-Pr⁡App,g→·g→^·g→~=1,where (8)pp,sp⟵SampP1λ,1n;g→⟵SampPpp;g→^⟵SampG^pp,sp;g→~⟵SampG~pp,sp.(Right Subgroup Indistinguishability 1). For any PPT adversary A, the advantage of A is negligible in λ: (9)AdvARS1λ≔Pr⁡App,g→·g→^,g→~,h→=1-Pr⁡App,g→·g→^,g→~,h→·h→^=1,where (10)pp,sp⟵SampP1λ,1n;g→⟵SampPpp;g→^⟵SampG^pp,sp;g→~⟵SampG~pp,sp;h→⟵SampHpp;h→^⟵SampH^pp,sp.(Right Subgroup Indistinguishability 2). For any PPT adversary A, the advantage of A is negligible in λ: (11)AdvARS2λ≔Pr⁡App,g→,g→^·g→~,h→·h→^=1-Pr⁡App,g→,g→^·g→~,h→·h→~=1,where (12)pp,sp⟵SampP1λ,1n;g→⟵SampPpp;g→^⟵SampG^pp,sp;g→~⟵SampG~pp,sp;h→⟵SampHpp;h→^⟵SampH^pp,sp;h→~⟵SampH~pp,sp.(Parameter Hiding). The following two distributions are identical: (13)pp,g→^·g→~,h→^·h→~,pp,g→^·g→^′·g→~·g→~′,h→^·h→^′·h→~·h→~′,where (14)pp,sp⟵SampP1λ,1n+l;g→^=g^0,…⟵SampG^pp,sp;h→^=h^0,…⟵SampH^pp,sp;g→~=g~0,…⟵SampG~pp,sp;h→~=h~0,…⟵SampH~pp,sp;g→^′=1,g^0u^1,…,g^0u^n;h→^′=1,h^0u^1,…,h^0u^n,u^1,…,u^n⟵RZp;g→~′=1,g~0u~1,…,g~0u~n;h→~′=1,h~0u~1,…,h~0u~n,u~1,…,u~n⟵RZp.


## 5. Instantiating EDSG

We letπL(·),πM(·) and πR(·) be functions mapping from a 3k×3k matrix to its left-most k columns, the middle k columns, and the right-most k columns, respectively.SampP
(
1
λ
,
1
n
)
(i)
Run(p,G1,G2,GT,g1,g2,e)←G(1λ).
(ii)
Define(G,H,GT,e)≔(G13k,G23k,GT,e).
(iii)
SampleB←RGL3k(Zp), and set B∗≔(B-1)⊤, Y1,…,Yn←RZp3k×3k; R is a random full-rank diagonal matrix in Zp3k whose bottom-right entry is a 2k-dimensional unit matrix; define (15)D≔πLB,Di≔Yi⊤πLB,E≔πMB,Ei≔Yi⊤πMB,F≔πRB,Fi≔Yi⊤πRB,D∗≔πLB∗R,Di∗≔YiπLB∗R,E∗≔πMB∗R,Ei∗≔YiπMB∗R,F∗≔πRB∗R,Fi∗≔YiπRB∗R.
(iv)
defineμ([k→]2)=[D⊤k→]T for all k→∈Zp3k.Output
(16)
p
p
≔
p
,
G
,
H
,
G
T
,
e
,
D
1
,
Y
1
⊤
D
1
,
…
,
Y
n
⊤
D
1
D
∗
2
,
Y
1
D
∗
2
,
…
,
Y
n
D
∗
2
.SampGT
(
[
p
→
]
T
). Pick s→←Zpk and output [s→⊤p→]T∈GT.SampG
(
p
p
). Pick s→←Zpk and output (17)Ds→1,Y1⊤Ds→1,…,Yn⊤Ds→1∈G13kn+1.SampH
(
p
p
). Pick r→←Zpk and output (18)D∗r→2,Y1D∗r→2,…,YnD∗r→2∈G23kn+1.S
a
m
p
G
^
(
p
p
,
s
p
). Pick s→^←Zpk and output (19)Es→^1,Y1⊤Es→^1,…,Yn⊤Es→^1∈G13kn+1.S
a
m
p
H
^
(
p
p
,
s
p
). Pick r→^←Zpk and output (20)E∗r→^2,Y1E∗r→^2,…,YnE∗r→^2∈G23kn+1.S
a
m
p
G
~
(
p
p
,
s
p
). Pick s→~←Zpk and output (21)Fs→~1,Y1⊤Fs→~1,…,Yn⊤Fs→~1∈G13kn+1.S
a
m
p
H
~
(
p
p
,
s
p
). Pick r→~←Zpk and output (22)F∗r→~2,Y1F∗r→~2,…,YnF∗r→~2∈G23kn+1.Set h^∗≔[E∗r→^]2, h~∗≔[F∗r→^]2.Correctness. We check correctness properties as follows.(Projective). For all k→∈Zp3k, s→∈Zpk: (23)SampGTμk→2;s→=s→⊤D⊤k→T=Ds→⊤k→T=eSampG0pp;s→,k→2.(Associative). For all s→∈Zpk, r→∈Zpk, Wi∈Zp3k×3k: (24)eg0,hi=Ds→⊤YiD∗r→=Yi⊤Ds→⊤D∗r→=egi,h0,i=1,…,n.Security. We check the following security properties.(Orthogonality)
(i)
μ
(
h
^
∗
)
=
μ
(
h
~
∗
)
=
(
1
,
…
,
1
)
⊤
∈
G
T
k.
(ii)
e
(
[
E
s
→
^
]
1
,
[
F
∗
r
→
~
]
2
)
=
1
G
T.
(iii)
e
(
[
F
s
→
~
]
1
,
[
E
∗
r
→
^
]
2
)
=
1
G
T.(Nondegeneracy)
(i)
e
(
[
E
s
→
^
]
1
,
[
E
∗
r
→
^
]
2
)
=
e
(
g
1
,
g
2
)
s
→
^
⊤
r
→
^.
(ii)
e
(
[
F
s
→
~
]
1
,
[
F
∗
r
→
~
]
2
)
=
e
(
g
1
,
g
2
)
s
→
~
⊤
r
→
~.With overwhelming probability, the inner product s→^⊤r→^ is distributed uniformly over Zp and therefore e([Es→^]1,[E∗r→^]2) is distributed uniformly over GT, and the same is true for e([Fs→~]1,[F∗r→~]2).(
H
-
S
u
b
g
r
o
u
p
). This follows from the fact that Zp3k is an additive group.Lemma 5 (left subgroup indistinguishability).
For any PPT adversaryA, there exists an adversary B such that (25)AdvALSλ⩽AdvBk,2k-LLin.We may rewrite the LS advantage function as follows:(26)AdvALSλ≔Pr⁡App,g→=1-Pr⁡App,g→·g→^·g→~=1,where (27)pp,sp⟵SampP1λ,1n;s→,s→^,s→~⟵RZpk;g→≔Bs→0→0→1,Y1⊤Bs→0→0→1,…,Yn⊤Bs→0→0→1;g→·g→^·g→~≔Bs→s→^s→~1,Y1⊤Bs→s→^s→~1,…,Yn⊤Bs→s→^s→~1.Proof.
Given an instance of (k,2k)-LLin problem (i.e., l=2k), (28)g1,g2,g1a1,…,g1ak,g1bi,ji∈2k,j∈k,g1a1s1,…,gkaksk,g1bi,1s1+⋯+bi,ksk+sk+ii∈2kas input, where all sk+i are either 0 or uniformly chosen from Zp∗. B implicitly sets (29)s→=s1,…,sk⊤,s→^=sk+1,…,s2k⊤,s→~=s2k+1,…,s3k⊤.Define W∈Zp3k×3k as (30)W≔a1⋱akb1,1⋯b1,k1⋮⋮⋱bk,1⋯bk,k1bk+1,1⋯bk+1,k1⋮⋮⋱b2k,1⋯b2k,k1,W∗≔W-1⊤≔a1-1-a1-1b1,1⋯-a1-1bk,1-a1-1bk+1,1⋯-a1-1b2k,1⋱⋮⋮⋮⋮ak-1-ak-1b1,k⋯-ak-1bk,k-ak-1bk+1,k⋯-ak-1b2k,k1⋱11⋱1.Sample B-←GL3k(Zp), Y1,…,Yn←Zp3k×3k, r-1,…,r-k←Zp∗, set B-∗≔(B--1)⊤, and implicitly set (31)B,B∗≔B-W,B-∗W∗R≔a1r-1⋱akr-k1⋱11⋱1.Then we can compute (32)πLW∗R≔r-1⋱r-k0→2k×k.
Simulating
pp
(33)
π
L
B
1
=
B
-
π
L
W
1
,
Y
i
⊤
π
L
B
1
=
Y
i
⊤
B
-
π
L
W
1
,
π
L
B
∗
R
2
=
B
-
∗
π
L
W
∗
R
2
,
Y
i
π
L
B
∗
R
2
=
Y
i
B
-
∗
π
L
W
∗
R
2
.
Simulating the Challenge. B simulates the challenge as (34)Bs→s→^s→~1=B-Ws→s→^s→~1,Yi⊤Bs→s→^s→~1=Yi⊤B-Ws→s→^s→~1,Ws→s→^s→~=a1s1⋮akskb1,1s1+⋯+b1,ksk+sk+1⋮b2k,1s1+⋯+b2k,ksk+s3k.If sk+i=0, i=1,…,2k, that is, s→^=s→~=0→, the output is g→; otherwise, the output is g→·g→^·g→~.Lemma 6 (right subgroup indistinguishability 1).
For any PPT adversaryA, there exists an adversary B such that (35)AdvARS1λ⩽AdvBk,k-LLin.We may rewrite the RS1 advantage function as follows:(36)AdvARS1λ≔Pr⁡App,g→·g→^,g→~,h→=1-Pr⁡App,g→·g→^,g→~,h→·h→^=1,where (37)pp,sp⟵SampP1λ,1n;s→,s→^,s→~,r→,r→^⟵RZpk;g→·g→^≔Bs→s→^0→1,Y1⊤Bs→s→^0→1,…,Yn⊤Bs→s→^0→1;g→~≔B0→0→s→~1,Y1⊤B0→0→s→~1,…,Yn⊤B0→0→s→~1;h→≔B∗Rr→0→0→2,Y1B∗Rr→0→0→2,…,YnB∗Rr→0→0→2;h→·h→^≔B∗Rr→r→^0→2,Y1B∗Rr→r→^0→2,…,YnB∗Rr→r→^0→2.Proof.
Given an instance of (k,k)-LLin problem (i.e., l=k) (38)g1,g2,g2a1,…,g2ak,g2bi,ji,j∈k,g2a1r1,…,g2akrk,g2bi,1r1+⋯+bi,krk+sk+ii∈kas input, where all sk+i are either 0 or uniformly chosen from Zp∗. B samples r-1,…,r-k←Zp∗ and implicitly sets (39)r→=r-1-1r1,…,r-k-1rk⊤,r→^=rk+1,…,r2k⊤.Define W∗∈Zp3k×3k as (40)W∗≔1⋱1a1-1b1,1⋯ak-1b1,k1⋮⋮⋱a1-1bk,1⋯ak-1bk,k11⋱1,W-1≔1a1-1b1,1⋯a1-1bk,1⋱⋮⋮1ak-1b1,k⋯ak-1bk,k1⋱11⋱1,W≔1-a1-1b1,1⋯-a1-1bk,1⋱⋮⋮1-ak-1b1,k⋯-ak-1bk,k1⋱11⋱1.Sample B-←GL3k(Zp), Y1,…,Yn←Zp3k×3k, set B-∗≔(B--1)⊤, and implicitly set (41)B,B∗≔B-W,B-∗W∗,R≔a1r-1⋱akr-k1⋱11⋱1.Then we can compute (42)W∗R≔a1r-1⋱akr-kb1,1r-1⋯b1,kr-k1⋮⋮⋱bk,1r-1⋯bk,kr-k11⋱1.
Simulating
pp
(43)
π
L
B
1
=
B
-
π
L
W
1
,
Y
i
⊤
π
L
B
1
=
Y
i
⊤
B
-
π
L
W
1
,
π
L
B
∗
R
2
=
B
-
∗
π
L
W
∗
R
2
,
Y
i
π
L
B
∗
R
2
=
Y
i
B
-
∗
π
L
W
∗
R
2
,
π
R
B
∗
R
2
=
B
-
∗
π
R
W
∗
R
2
,
Y
i
π
R
B
∗
R
2
=
Y
i
B
-
∗
π
R
W
∗
R
2
.
Simulating
g
→
·
g
→
^
,
g
→
~. Sample s→′,s→^′,s→~′←ZpK and implicitly set (44)s→s→^0→=W-1s→′s→^′0→,0→0→s→~=W-10→0→s→~′.Then we can compute (45)Bs→s→^0→1=B-s→′s→^′0→1,YiBs→s→^0→1=YiB-s→′s→^′0→1,B-0→0→s→~1=B-0→0→s→~′1,YiB0→0→s→~1=YiB-0→0→s→~′1.
Simulating the Challenge. B simulates the challenge as (46)B∗Rr→r→^0→1=B-∗W∗Rr→r→^0→2,YiB∗r→r→^0→1=YiB-∗W∗Rr→r→^0→2,W∗Rr→r→^0→=a1r1⋮akrkb1,1r1+⋯+b1,krk+rk+1⋮bk,1r1+⋯+bk,krk+r2k0→.If rk+i=0, i=1,…,2k, that is, r→^=0→, the output is h→; otherwise, the output is h→·h→^.Lemma 7 (right subgroup indistinguishability 2′).
For any PPT adversaryA, there exists an adversary B such that (47)AdvARS2′λ⩽AdvBk,k-LLin.The RS2′ advantage function:(48)AdvARS2′λ≔Pr⁡App,g→,g→^·g→~,h→·h→^=1-Pr⁡App,g→,g→^·g→~,h→·h→^·h→~=1,where (49)pp,sp⟵SampP1λ,1n;s→,s→^,s→~,r→,r→^,r→~⟵RZpk;g→≔Bs→0→0→1,Y1⊤Bs→0→0→1,…,Yn⊤Bs→0→0→1;g→^·g→~≔B0→s→^s→~1,Y1⊤B0→s→^s→~1,…,Yn⊤B0→s→^s→~1;h→·h→^≔B∗Rr→r→^0→2,Y1B∗Rr→r→^0→2,…,Yn⊤B∗Rr→r→^0→2;h→·h→^·h→~≔B∗Rr→r→^r→~2,Y1B∗Rr→r→^r→~2,…,YnB∗Rr→r→^r→~2.Proof.
Given an instance of (k,k)-LLin problem (i.e., l=k) (50)g1,g2,g2a1,…,g2ak,g2bi,ji,j∈k,g2a1r1,…,g2akrk,g2bi,1r1+⋯+bi,krk+rk+ii∈kas input, where all sk+i are either 0 or uniformly chosen from Zp∗. B samples r1′,…,rk′←Zp∗ and implicitly sets (51)r→=r1′,…,rk′⊤,r→^=r1,…,rk⊤,r→~=rk+1,…,r2k⊤.Define W∗∈Zp3k×3k as (52)W∗≔1⋱1a1⋱akb1,1⋯b1,k1⋮⋮⋱bk,1⋯bk,k1,W-1≔1⋱1a1b1,1⋯bk,1⋱⋮⋮akb1,k⋯bk,k1⋱1,W≔1⋱1a1-1-a1-1b1,1⋯-a1-1bk,1⋱⋮⋮ak-1-ak-1b1,k⋯-ak-1bk,k1⋱1.Sample B-←GL3k(Zp), Y1,…,Yn←Zp3k×3k, set B-∗≔(B--1)⊤, and implicitly set (53)B,B∗≔B-W,B-∗W∗,R≔r11⋱rkk1⋱11⋱1.Then we can compute (54)W∗R≔r11⋱rkka1⋱akb1,1⋯b1,k1⋮⋮⋱bk,1⋯bk,k1.
Simulating
pp
(55)
π
L
B
1
=
B
-
π
L
W
1
,
Y
i
⊤
π
L
B
1
=
Y
i
⊤
B
-
π
L
W
1
,
(56)
π
L
B
∗
R
2
=
B
-
∗
π
L
W
∗
R
2
,
Y
i
π
L
B
∗
R
2
=
Y
i
B
-
∗
π
L
W
∗
R
2
,
(57)
π
R
B
∗
R
2
=
B
-
∗
π
R
W
∗
R
2
,
Y
i
π
R
B
∗
R
2
=
Y
i
B
-
∗
π
R
W
∗
R
2
.
Simulating
g
→
,
g
→
^
·
g
→
~
. Sample s→′,s→^′,s→~′←ZpK and implicitly set (58)s→0→0→=W-1s→′0→0→,0→s→^s→~=W-10→s→^′s→~′.Then we can compute (59)Bs→0→0→1=B-s→′0→0→1,YiBs→0→0→1=YiB-s→′0→0→1,B-0→s→^s→~1=B-0→s→^′s→~′1,YiB0→s→^s→~1=YiB-0→s→^′s→~′1.
Simulating the Challenge. B simulates the challenge as (60)B∗Rr→r→^r→~1=B-∗W∗Rr→r→^r→~2,YiB∗r→r→^r→~1=YiB-∗W∗Rr→r→^r→~2,W∗Rr→r→^r→~=r11r1′⋮rk,krk′a1r1⋮akrkb1,1r1+⋯+b1,krk+rk+1⋮bk,1r1+⋯+bk,krk+r2k.If rk+i=0, i=1,…,2k, that is, r→~=0→, the output is h→·h→^; otherwise, the output is h→·h→^·h→~.Similarly, we can proof(61)Pr⁡App,g→,g→^·g→~,h→·h→~=1-Pr⁡App,g→,g→^·g→~,h→·h→^·h→~=1⩽AdvBk,k-LLin.Hence, right subgroup indistinguishability 2 is true.Lemma 8 (parameter hiding).
The following are identically distributed:(62)pp,πMBs→^+πRBs→~1,Yi⊤πMBs→^+πRBs→~1πMB∗Rr→^+πRB∗Rr→~2,YiπMB∗Rr→^+πRB∗Rr→~2i∈n,pp,πMBs→^+πRBs→~1,Yi⊤πMB+u^iπMBs→^+Yi⊤πRB+u~iπRBs→~1πMB∗Rr→^+πRB∗Rr→~2,YiπMB∗R+u^iπMB∗Rr→^+YiπRB∗R+u~iπRB∗Rr→~2i∈n,where s→^,s→~,r→^,r→~←RZpk and u^i,u~i←RZp.Proof.
SampleB←RGL3k(Zp), and set B∗≔(B-1)⊤, Y1,…,Yn←RZp3k×3k; R is a random full-rank diagonal matrix in Zp3k whose bottom-right entry is a 2k-dimensional unit matrix: (63)D≔πLB,Di≔Yi⊤πLB,E≔πMB,Ei≔Yi⊤πMB,F≔πRB,Fi≔Yi⊤πRB,D∗≔πLB∗R,Di∗≔YiπLB∗R,E∗≔πMB∗R,Ei∗≔YiπMB∗R,F∗≔πRB∗R,Fi∗≔YiπRB∗R.Define V1=πM(B∗)πM(B)⊤, V2=πR(B∗)πR(B)⊤, and Yi′=Yi+u^iV1+u~iV2. Then (64)Yi′⊤B=Yi⊤B+u^iV1⊤B+u~iV2⊤B,Yi′B∗R=YiB∗R+u^iV1B∗R+u~iV2B∗R.Observe that (65)V1⊤B=πMBπMB∗⊤B=πMB0⋯010⋯0⋮⋮⋱⋮⋮0⋯010⋯0=0→3k×k∥πMB∥0→3k×k,(66)V2⊤B=πRBπRB∗⊤B=0→3k×k∥0→3k×k∥πRB,V1B∗R=πMB∗πMB⊤B∗R=0→3k×k∥πMB∗∥0→3k×k,V2B∗R=πRB∗πRB⊤B∗R=0→3k×k∥0→3k×k∥πRB∗.Hence, (67)Yi′⊤B=Di∥Ei+u^iE∥Fi+u~iF,Yi′B∗R=Di∗∥Ei∗+u^iE∗∥Fi∗+u~iF∗.(i)
Ifu^i=u~i=0, then we obtain the first distribution.(ii)
Ifu^i,u~i←Zp, then we obtain the second distribution.


## 6. Our Scheme

This section presents our decentralized CP-ABE system. Recall thatπL(·), πM(·), and πR(·) are functions mapping from a 3k×3k matrix to its left k columns, middle k columns, and right k columns, respectively. We use the left k-dimension subspaces to generate the normal ciphertexts and secret keys. The next two ones are only used in the security proof. The hash function H maps global identities to random elements in H, which is used as a random oracle in the security proof.


### 6.1. Construction

GlobalSetup
1
λ
. Sample B←GL3k(Zp) and set B∗=(B-1)⊤. Output (68)GP=p,G13k,G23k,GT,e;πLB1,H.Authority Setup
(
G
P
). For each attribute atti belonging to the authority, the authority samples k→i←Zp3k, Yi←Zp3k×3k and outputs (69)APK≔πLB1,Yi⊤πLB1,eπLB1,k→i2,ASK≔k→i,Yi.Enc
(
{
A
P
K
}
,
G
P
,
(
M
,
ρ
)
,
m
). Input a message m, a matrix M∈Zpl×l′ with ρ (in our system, we restrict the fact that ρ is injective) mapping its rows to attributes, the global parameters, and the public keys of the relevant authorities. Pick U2,…,Ul′←RZp3k×3k, s→←RZpk, v→=(s0,v2,…,vl′)←RZpl′. We let Mx denote row x of M, and λx=Mx·v→. The ciphertext is (70)C=m·eg1,g2s0,C0=πLBs→1,C1,x=eg1,g2λxeg1,g2kρx⊤πLBs→,C2,x=0→∥U2⊤πLBs→∥⋯∥Ul′⊤πLBs→Mx⊤+Yρx⊤πLBs→1.KeyGen
(
G
P
,
G
I
D
,
A
S
K
j
,
a
t
t
i
). Compute a key forGID for attribute atti belonging to authority AAj as follows: (71)SKGID,i=g2k→iHGIDYi.Dec
(
G
P
,
S
K
G
I
D
,
i
,
C
T
). The secret keys {SKGID,i} correspond to a subset of rows Mx of M. If (1,0,…,0) is in the span of Mx, then ω1,…,ωl∈Zp is computed such that(72)∑xωxMx=1,0,…,0.Then, compute (73)∏xC1,x·eHGID,C2,xeSKGID,ρx,C0ωx=∏xC1,xωx·eHGID,∏xC2,xωxe∏xSKGID,ρxωx,C0=eg1,g2∑xωxMxv→eg1,g2r→⊤0→=eg1,g2s0,m=Ceg1,g2s0.


### 6.2. Security Proof

We define the semifunctional ciphertext and secret key as follows.Semifunctional Ciphertext. We let C′, C0′, C1,x′, C2,x′ denote the normal ciphertext. The semifunctional ciphertext takes the following form: (74)C=C′,C0=C0′·πMBs→^+πRBs→~1,C1,x=C1,x′·eg1,g2kρx⊤πMBs→^+πRBs→~,C2,x=C2,x′·s^πMBs→^∥U2⊤πMBs→^∥⋯∥Ul′⊤πMBs→^Mx⊤+Yρx⊤πMBs→^1·s~πRBs→~∥U2⊤πRBs→~∥⋯∥Ul′⊤πRBs→~Mx⊤+Yρx⊤πRBs→~1,where s→^,s→~←RZpk, U2,…,Ul′←RZp3k×3k.Semifunctional Secret Key. There are two types of semifunctional keys. Type 1 semifunctional key takes the following form: (75)HGID=πLB∗Rr→+πMB∗Rr→^2,SKGID,i=g2k→iHGIDYi=k→i+YiπLB∗Rr→+πMB∗Rr→^2.Type 2 semifunctional key takes the following form: (76)HGID=πLB∗Rr→+πRB∗Rr→~2,SKGID,i=g2k→iHGIDYi=k→i+YiπLB∗Rr→+πRB∗Rr→~2.When a semifunctional key is used to decrypt a semifunctional ciphertext, the additional terms (i)
type 1 semifunctional key:e(g1,g2)s^r→^⊤πM(B∗R)⊤πM(B)s→^,(ii)
type 2 semifunctional key:e(g1,g2)s~r→~⊤πR(B∗R)⊤πR(B)s→~prevent decryption.Game Sequence. We let AdvAGameX denote the advantage of A in GameX.(i)
Game0: it is the real security game.(ii)
Game1: there is no difference with Game0 except that challenge ciphertext becomes semifunctional.(iii)
Game2,j,1 for j=1,…,q: there is no difference with Game1 except that the first j-1 keys revealed to A become semifunctional of type 2, and the j′th key becomes semifunctional of type 1.(iv)
Game2,j,2 for j=1,…,q: there is no difference with Game1 except that the first j keys revealed to A become semifunctional of type 2. We let Game2,0,2 denote Game1.(v)
Game3: there is no difference with Game2,q,2 except that we generate a semifunctional ciphertext of a random message m′∈GT as the challenge ciphertext.Lemma 9 (fromGame0 to Game1).
For any PPT adversaryA, there exists an adversary B such that AdvAGame0(λ)-AdvAGame1(λ)⩽AdvBLS(λ).Proof.
The adversaryB gets input (77)pp,t→,where t→ is g→ or g→·g→^·g→~.
Setup. Pick k→i and output (78)APK≔pp,eπLB1,k→i2.
Key Queries. When A queries the random oracle for H(GID), B chooses r→←Zpk, sets H(GID)=[πL(B∗R)r→]2, and stores this value. B creates secret keys as follows: (79)SKGID,i=k→i+YiπLB∗Rr→2.
Challenge. Upon receiving (M,ρ), m0, and m1, B can compute the ciphertext by using t→. We note that the ciphertext is properly distributed except C2,x, which take the following forms: (80)C2,x=0→∥U2⊤πLBs→∥⋯∥Ul′⊤πLBs→Mx⊤+Yi⊤πLBs→1·0→∥U2⊤πMBs→^∥⋯∥Ul′⊤πMBs→^Mx⊤+Yi⊤πMBs→^1·0→∥U2⊤πRBs→~∥⋯∥Ul′⊤πRBs→~Mx⊤+Yi⊤πRBs→~1,where s→,s→^,s→~←RZpk, U2,…,Ul′←RZp3k×3k. We must argue that there is no difference in A’s view.
By parameter hiding, it suffices to show that(81)0→∥⋯Mx⊤+u^iπMBs→^1·0→∥⋯Mx⊤+u~iπRBs→~1,s^πMBs→^∥⋯Mx⊤+u^iπMBs→^1·s~πMBs→~∥⋯Mx⊤+u~iπRBs→~1are identically distributed. This follows readily from the fact that (i)
the space spanned by rows ofM whose corresponding attributes belong to corrupt authorities cannot include the vector (1,0,…,0); it reveals no information about s^πM(B)s→^ and s~πR(B)s→~;(ii)
rows ofM whose corresponding attributes belong to good authorities are masked by u^iπM(B)s→^ and u~iπR(B)s→~, respectively.If t→=g→, B properly simulates Game0; if t→=g→·g→^·g→~, B properly simulates Game1. Hence, B can determine the distribution of t→ by using adversary A.Lemma 10 (fromGame2,j-1,2 to Game2,j,1).
For any PPT adversaryA, there exists an adversary B such that AdvAGame2,j-1,2(λ)-AdvAGame2,j,1(λ)⩽AdvBRS1(λ).Proof.
The adversaryB gets input (82)pp,g→·g→^,g→~,t→,where t→ is h→ or h→·h→^.
Setup. Pick k→i and output (83)APK≔pp,eπLB1,k→i2.
Key Queries. We let GIDk denote the kth identity queried by A. (i)
k<j: B chooses r→←Zpk and sets H(GIDk)=[(πL(B∗R)+πR(B∗R))r→]2.(ii)
k>j: B chooses r→←Zpk and sets H(GIDk)=[πL(B∗R)r→]2.(iii)
k=j: H(GID)=t→0, where t→0 is the first element in t→.B creates secret keys as follows: (84)SKGID,i=g2k→iHGIDYi.
Challenge. Upon receiving (M,ρ), m0, and m1, B computes the ciphertext by using g→·g→^, g→~ as follows: (85)C′=m·eg1,g2s0,C0=πLBs→+πMBs→^+πRBs→~1,C1,x=eg1,g2λxeg1,g2k→x⊤πLBs→+πMBs→^+πRBs→~,C2,x=0→∥U2⊤πLBs→∥⋯∥Ul′⊤πLBs→Mx⊤+Yi⊤πLBs→1·0→∥U2⊤πMBs→^∥⋯∥Ul′⊤πMBs→^Mx⊤+Yi⊤πMBs→^1·s~πRBs→~∥U2⊤πRBs→~∥⋯∥Ul′⊤πRBs→~Mx⊤+Yi⊤πRBs→~1,where s→^,s→~←RZpk, U2,…,Ul′←RZp3k×3k. The ciphertext is properly distributed except that the second components of C2,x are shares of 0. We must argue that there is no difference in A’s view.
By parameter hiding, it suffices to show that(86)0→∥⋯Mx⊤+u^iπMBs→^1,s^πMBs→^∥⋯Mx⊤+u^iπMBs→^1are identically distributed. This follows readily from the fact that (i)
fork>j and k<j, H(GIDk) have nothing to do with πM(B)s→^;(ii)
the space spanned by rows ofM whose corresponding attributes belong to corrupted authorities or queried with GIDj cannot include the vector (1,0,…,0); it reveals no information about s^πM(B)s→^;(iii)
the remaining rows ofM are masked by u^iπM(B)s→^.If t→=h→, B properly simulates Game2,j-1,2; if t→=h→·h→^, B properly simulates Game2,j,1. Hence, B can determine the distribution of t→ by using adversary A.Lemma 11 (fromGame2,j,1 to Game2,j,2).
For any PPT adversaryA, there exists an adversary B such that AdvAGame2,j,1(λ)-AdvAGame2,j,2(λ)⩽AdvBRS2(λ).Proof.
The adversaryB gets input (87)pp,g→,g→^·g→~,t→,where t→ is h→·h→^ or h→·h→~.
Setup. Pick k→i and output (88)PK≔pp,eπLB1,k→i2.
Key Queries. We let GIDk denote the kth identity queried by A. (i)
k<j: B chooses r→←Zpk and sets H(GIDk)=[(πL(B∗R)+πR(B∗R))r→]2.(ii)
k>j: B chooses r→←Zpk and sets H(GIDk)=[πL(B∗R)r→]2.(iii)
k=j: H(GID)=t→0, where t→0 is the first element in t→.B creates secret keys as follows: (89)KGID,i=g2k→iHGIDYi.
Challenge. Upon receiving (M,ρ), m0, and m1, B computes the ciphertext as follows: (90)C′=m·eg1,g2s0,C0=πLBs→+πMBs→^+πRBs→~1,C1,x=eg1,g2λxeg1,g2k→x⊤πLBs→+πMBs→^+πRBs→~,C2,x=0→∥U2⊤πLBs→∥⋯∥Ul′⊤πLBs→Mx⊤+Yi⊤πLBs→1·s^πMBs→^∥U2⊤πMBs→^∥⋯∥Ul′⊤πMBs→^Mx⊤+Yi⊤πMBs→^1·s~πRBs→~∥U2⊤πRBs→~∥⋯∥Ul′⊤πRBs→~Mx⊤+Yi⊤πRBs→~1,where s→^,s→~←RZpk, U2,…,Ul′←RZp3k×3k, s^,s~←RZp, and we implicitly set s^=s~.
Ift→=h→·h→~, B properly simulates Game2,j,1; if t→=h→·h→^, B properly simulates Game2,j,2. Hence, B can determine the distribution of t→ by using adversary A.Lemma 12 (fromGame2,q,2 to Game3).
For any PPT adversaryA, there exists an adversary B such that (91)AdvAGame2,q,2λ-AdvAGame3λ=0.Proof.
Setup. B samples B←GL3k(Zp) and sets B∗=(B-1)⊤. Output (92)GP=p,G13k,G23k,GT,e;πLB1,H.B also samples k→i←Zp3k, Yi←Zp3k×3k for each attribute and sets (93)APK≔πLB1,Yi⊤πLB1,eπLB1,k→i2,ASK≔k→i,Yi.
Key Queries. In both games, the secret keys take the following form: (94)SKGID,i=k→i+YiπLB∗Rr→+πRB∗Rr→2,which means they leak no information whatsoever about πM(B).
Challenge. Upon receiving (M,ρ), m0, and m1, B computes the semifunctional ciphertext of m0 or m1. Observe that (95)C1,x=eg1,g2λxeg1,g2k→x⊤πLBs→+πRBs→~eg1,g2k→x⊤πMBs→^,and the quantity e(g1,g2)k→x⊤πM(B)s→^ is uniformly distributed over GT. This implies the challenge ciphertext is identically distributed to a semifunctional encryption of a random message in GT, as in Game3.


### 6.3. Performance Discussions

In this section, we provided analysis regarding the space and computation cost of the proposed scheme by comparing it with existing decentralized ABE schemes.As shown in Table1, [11] is built on composite-order groups. We recall that composite-order elements are 12 times larger than prime-order ones and pairing is 250 times slower in composite-order groups than in prime-order ones [12]. Though [29] is efficient, the scheme can be only proved static security under a q-type assumption. Both [13] and ours are based on prime-order groups; the secret key size and the ciphertext size in ours are reduced by about 40% compared with [13] under the same assumption (DLIN). We will see further improvement if we instantiate our construction under the SXDH assumption. In addition, the ciphertexts in our setting can be decrypted with a constant number of pairings at the cost of increasing some exponentiations. We believe that this is a good deal since pairing is about 5 times slower than group exponentiation according to [29]. The advantage of decryption performance in our scheme will become more and more obvious as the number of attributes used for decryption increases.Table 1
Comparing among existing decentralized CP-ABE schemes.|APK|, |SK|, and |CT| represent the size of authority’s public keys, user’s secret keys, and ciphertexts. n is the number of attributes present in authority or secret keys. l is number of rows in the access matrix. TDec represents decryption cost, “Pair” and “Exp” represent the number of pairings and exponentiations in groups. l′ is the number of attributes used during decryption. |G| indicates the group order, “P” is for prime, and “C” is for composite order, respectively. “Assu.” and “Secu.” are abbreviation of assumption and security, respectively.
Ref.
|
A
P
K
|
|
S
K
|
|
C
T
|
T
D
e
c
Assu.
|
G
|
Secu.
G
1
G
T
G
1
/
G
2
G
1
G
T
Pair
Exp
[11]
n
n
n
2
l
l
+
1
l
′
+
1
3
l
′
Static
C
Full
[29]
1
1
2
n
3
l
l
+
1
2
l
′
+
1
4
l
′
q-type
P
Static
[13]
55
n
1
11
n
11
l
1
11
l
′
l
′
DLIN
P
Full
Ours
3
k
2
(
n
+
1
)
k
n
3
k
n
3
k
(
l
+
1
)
l
+
1
6
k
6
k
l
′
+
l
′
k-Lin
P
Full
3
(
n
+
1
)
n
3
n
3
(
l
+
1
)
l
+
1
6
7
l
′
SXDH
12
(
n
+
1
)
2
n
6
n
6
(
l
+
1
)
l
+
1
12
13
l
′
DLIN


## 6.1. Construction

GlobalSetup
1
λ
. Sample B←GL3k(Zp) and set B∗=(B-1)⊤. Output (68)GP=p,G13k,G23k,GT,e;πLB1,H.Authority Setup
(
G
P
). For each attribute atti belonging to the authority, the authority samples k→i←Zp3k, Yi←Zp3k×3k and outputs (69)APK≔πLB1,Yi⊤πLB1,eπLB1,k→i2,ASK≔k→i,Yi.Enc
(
{
A
P
K
}
,
G
P
,
(
M
,
ρ
)
,
m
). Input a message m, a matrix M∈Zpl×l′ with ρ (in our system, we restrict the fact that ρ is injective) mapping its rows to attributes, the global parameters, and the public keys of the relevant authorities. Pick U2,…,Ul′←RZp3k×3k, s→←RZpk, v→=(s0,v2,…,vl′)←RZpl′. We let Mx denote row x of M, and λx=Mx·v→. The ciphertext is (70)C=m·eg1,g2s0,C0=πLBs→1,C1,x=eg1,g2λxeg1,g2kρx⊤πLBs→,C2,x=0→∥U2⊤πLBs→∥⋯∥Ul′⊤πLBs→Mx⊤+Yρx⊤πLBs→1.KeyGen
(
G
P
,
G
I
D
,
A
S
K
j
,
a
t
t
i
). Compute a key forGID for attribute atti belonging to authority AAj as follows: (71)SKGID,i=g2k→iHGIDYi.Dec
(
G
P
,
S
K
G
I
D
,
i
,
C
T
). The secret keys {SKGID,i} correspond to a subset of rows Mx of M. If (1,0,…,0) is in the span of Mx, then ω1,…,ωl∈Zp is computed such that(72)∑xωxMx=1,0,…,0.Then, compute (73)∏xC1,x·eHGID,C2,xeSKGID,ρx,C0ωx=∏xC1,xωx·eHGID,∏xC2,xωxe∏xSKGID,ρxωx,C0=eg1,g2∑xωxMxv→eg1,g2r→⊤0→=eg1,g2s0,m=Ceg1,g2s0.


## 6.2. Security Proof

We define the semifunctional ciphertext and secret key as follows.Semifunctional Ciphertext. We let C′, C0′, C1,x′, C2,x′ denote the normal ciphertext. The semifunctional ciphertext takes the following form: (74)C=C′,C0=C0′·πMBs→^+πRBs→~1,C1,x=C1,x′·eg1,g2kρx⊤πMBs→^+πRBs→~,C2,x=C2,x′·s^πMBs→^∥U2⊤πMBs→^∥⋯∥Ul′⊤πMBs→^Mx⊤+Yρx⊤πMBs→^1·s~πRBs→~∥U2⊤πRBs→~∥⋯∥Ul′⊤πRBs→~Mx⊤+Yρx⊤πRBs→~1,where s→^,s→~←RZpk, U2,…,Ul′←RZp3k×3k.Semifunctional Secret Key. There are two types of semifunctional keys. Type 1 semifunctional key takes the following form: (75)HGID=πLB∗Rr→+πMB∗Rr→^2,SKGID,i=g2k→iHGIDYi=k→i+YiπLB∗Rr→+πMB∗Rr→^2.Type 2 semifunctional key takes the following form: (76)HGID=πLB∗Rr→+πRB∗Rr→~2,SKGID,i=g2k→iHGIDYi=k→i+YiπLB∗Rr→+πRB∗Rr→~2.When a semifunctional key is used to decrypt a semifunctional ciphertext, the additional terms (i)
type 1 semifunctional key:e(g1,g2)s^r→^⊤πM(B∗R)⊤πM(B)s→^,(ii)
type 2 semifunctional key:e(g1,g2)s~r→~⊤πR(B∗R)⊤πR(B)s→~prevent decryption.Game Sequence. We let AdvAGameX denote the advantage of A in GameX.(i)
Game0: it is the real security game.(ii)
Game1: there is no difference with Game0 except that challenge ciphertext becomes semifunctional.(iii)
Game2,j,1 for j=1,…,q: there is no difference with Game1 except that the first j-1 keys revealed to A become semifunctional of type 2, and the j′th key becomes semifunctional of type 1.(iv)
Game2,j,2 for j=1,…,q: there is no difference with Game1 except that the first j keys revealed to A become semifunctional of type 2. We let Game2,0,2 denote Game1.(v)
Game3: there is no difference with Game2,q,2 except that we generate a semifunctional ciphertext of a random message m′∈GT as the challenge ciphertext.Lemma 9 (fromGame0 to Game1).
For any PPT adversaryA, there exists an adversary B such that AdvAGame0(λ)-AdvAGame1(λ)⩽AdvBLS(λ).Proof.
The adversaryB gets input (77)pp,t→,where t→ is g→ or g→·g→^·g→~.
Setup. Pick k→i and output (78)APK≔pp,eπLB1,k→i2.
Key Queries. When A queries the random oracle for H(GID), B chooses r→←Zpk, sets H(GID)=[πL(B∗R)r→]2, and stores this value. B creates secret keys as follows: (79)SKGID,i=k→i+YiπLB∗Rr→2.
Challenge. Upon receiving (M,ρ), m0, and m1, B can compute the ciphertext by using t→. We note that the ciphertext is properly distributed except C2,x, which take the following forms: (80)C2,x=0→∥U2⊤πLBs→∥⋯∥Ul′⊤πLBs→Mx⊤+Yi⊤πLBs→1·0→∥U2⊤πMBs→^∥⋯∥Ul′⊤πMBs→^Mx⊤+Yi⊤πMBs→^1·0→∥U2⊤πRBs→~∥⋯∥Ul′⊤πRBs→~Mx⊤+Yi⊤πRBs→~1,where s→,s→^,s→~←RZpk, U2,…,Ul′←RZp3k×3k. We must argue that there is no difference in A’s view.
By parameter hiding, it suffices to show that(81)0→∥⋯Mx⊤+u^iπMBs→^1·0→∥⋯Mx⊤+u~iπRBs→~1,s^πMBs→^∥⋯Mx⊤+u^iπMBs→^1·s~πMBs→~∥⋯Mx⊤+u~iπRBs→~1are identically distributed. This follows readily from the fact that (i)
the space spanned by rows ofM whose corresponding attributes belong to corrupt authorities cannot include the vector (1,0,…,0); it reveals no information about s^πM(B)s→^ and s~πR(B)s→~;(ii)
rows ofM whose corresponding attributes belong to good authorities are masked by u^iπM(B)s→^ and u~iπR(B)s→~, respectively.If t→=g→, B properly simulates Game0; if t→=g→·g→^·g→~, B properly simulates Game1. Hence, B can determine the distribution of t→ by using adversary A.Lemma 10 (fromGame2,j-1,2 to Game2,j,1).
For any PPT adversaryA, there exists an adversary B such that AdvAGame2,j-1,2(λ)-AdvAGame2,j,1(λ)⩽AdvBRS1(λ).Proof.
The adversaryB gets input (82)pp,g→·g→^,g→~,t→,where t→ is h→ or h→·h→^.
Setup. Pick k→i and output (83)APK≔pp,eπLB1,k→i2.
Key Queries. We let GIDk denote the kth identity queried by A. (i)
k<j: B chooses r→←Zpk and sets H(GIDk)=[(πL(B∗R)+πR(B∗R))r→]2.(ii)
k>j: B chooses r→←Zpk and sets H(GIDk)=[πL(B∗R)r→]2.(iii)
k=j: H(GID)=t→0, where t→0 is the first element in t→.B creates secret keys as follows: (84)SKGID,i=g2k→iHGIDYi.
Challenge. Upon receiving (M,ρ), m0, and m1, B computes the ciphertext by using g→·g→^, g→~ as follows: (85)C′=m·eg1,g2s0,C0=πLBs→+πMBs→^+πRBs→~1,C1,x=eg1,g2λxeg1,g2k→x⊤πLBs→+πMBs→^+πRBs→~,C2,x=0→∥U2⊤πLBs→∥⋯∥Ul′⊤πLBs→Mx⊤+Yi⊤πLBs→1·0→∥U2⊤πMBs→^∥⋯∥Ul′⊤πMBs→^Mx⊤+Yi⊤πMBs→^1·s~πRBs→~∥U2⊤πRBs→~∥⋯∥Ul′⊤πRBs→~Mx⊤+Yi⊤πRBs→~1,where s→^,s→~←RZpk, U2,…,Ul′←RZp3k×3k. The ciphertext is properly distributed except that the second components of C2,x are shares of 0. We must argue that there is no difference in A’s view.
By parameter hiding, it suffices to show that(86)0→∥⋯Mx⊤+u^iπMBs→^1,s^πMBs→^∥⋯Mx⊤+u^iπMBs→^1are identically distributed. This follows readily from the fact that (i)
fork>j and k<j, H(GIDk) have nothing to do with πM(B)s→^;(ii)
the space spanned by rows ofM whose corresponding attributes belong to corrupted authorities or queried with GIDj cannot include the vector (1,0,…,0); it reveals no information about s^πM(B)s→^;(iii)
the remaining rows ofM are masked by u^iπM(B)s→^.If t→=h→, B properly simulates Game2,j-1,2; if t→=h→·h→^, B properly simulates Game2,j,1. Hence, B can determine the distribution of t→ by using adversary A.Lemma 11 (fromGame2,j,1 to Game2,j,2).
For any PPT adversaryA, there exists an adversary B such that AdvAGame2,j,1(λ)-AdvAGame2,j,2(λ)⩽AdvBRS2(λ).Proof.
The adversaryB gets input (87)pp,g→,g→^·g→~,t→,where t→ is h→·h→^ or h→·h→~.
Setup. Pick k→i and output (88)PK≔pp,eπLB1,k→i2.
Key Queries. We let GIDk denote the kth identity queried by A. (i)
k<j: B chooses r→←Zpk and sets H(GIDk)=[(πL(B∗R)+πR(B∗R))r→]2.(ii)
k>j: B chooses r→←Zpk and sets H(GIDk)=[πL(B∗R)r→]2.(iii)
k=j: H(GID)=t→0, where t→0 is the first element in t→.B creates secret keys as follows: (89)KGID,i=g2k→iHGIDYi.
Challenge. Upon receiving (M,ρ), m0, and m1, B computes the ciphertext as follows: (90)C′=m·eg1,g2s0,C0=πLBs→+πMBs→^+πRBs→~1,C1,x=eg1,g2λxeg1,g2k→x⊤πLBs→+πMBs→^+πRBs→~,C2,x=0→∥U2⊤πLBs→∥⋯∥Ul′⊤πLBs→Mx⊤+Yi⊤πLBs→1·s^πMBs→^∥U2⊤πMBs→^∥⋯∥Ul′⊤πMBs→^Mx⊤+Yi⊤πMBs→^1·s~πRBs→~∥U2⊤πRBs→~∥⋯∥Ul′⊤πRBs→~Mx⊤+Yi⊤πRBs→~1,where s→^,s→~←RZpk, U2,…,Ul′←RZp3k×3k, s^,s~←RZp, and we implicitly set s^=s~.
Ift→=h→·h→~, B properly simulates Game2,j,1; if t→=h→·h→^, B properly simulates Game2,j,2. Hence, B can determine the distribution of t→ by using adversary A.Lemma 12 (fromGame2,q,2 to Game3).
For any PPT adversaryA, there exists an adversary B such that (91)AdvAGame2,q,2λ-AdvAGame3λ=0.Proof.
Setup. B samples B←GL3k(Zp) and sets B∗=(B-1)⊤. Output (92)GP=p,G13k,G23k,GT,e;πLB1,H.B also samples k→i←Zp3k, Yi←Zp3k×3k for each attribute and sets (93)APK≔πLB1,Yi⊤πLB1,eπLB1,k→i2,ASK≔k→i,Yi.
Key Queries. In both games, the secret keys take the following form: (94)SKGID,i=k→i+YiπLB∗Rr→+πRB∗Rr→2,which means they leak no information whatsoever about πM(B).
Challenge. Upon receiving (M,ρ), m0, and m1, B computes the semifunctional ciphertext of m0 or m1. Observe that (95)C1,x=eg1,g2λxeg1,g2k→x⊤πLBs→+πRBs→~eg1,g2k→x⊤πMBs→^,and the quantity e(g1,g2)k→x⊤πM(B)s→^ is uniformly distributed over GT. This implies the challenge ciphertext is identically distributed to a semifunctional encryption of a random message in GT, as in Game3.


## 6.3. Performance Discussions

In this section, we provided analysis regarding the space and computation cost of the proposed scheme by comparing it with existing decentralized ABE schemes.As shown in Table1, [11] is built on composite-order groups. We recall that composite-order elements are 12 times larger than prime-order ones and pairing is 250 times slower in composite-order groups than in prime-order ones [12]. Though [29] is efficient, the scheme can be only proved static security under a q-type assumption. Both [13] and ours are based on prime-order groups; the secret key size and the ciphertext size in ours are reduced by about 40% compared with [13] under the same assumption (DLIN). We will see further improvement if we instantiate our construction under the SXDH assumption. In addition, the ciphertexts in our setting can be decrypted with a constant number of pairings at the cost of increasing some exponentiations. We believe that this is a good deal since pairing is about 5 times slower than group exponentiation according to [29]. The advantage of decryption performance in our scheme will become more and more obvious as the number of attributes used for decryption increases.Table 1
Comparing among existing decentralized CP-ABE schemes.|APK|, |SK|, and |CT| represent the size of authority’s public keys, user’s secret keys, and ciphertexts. n is the number of attributes present in authority or secret keys. l is number of rows in the access matrix. TDec represents decryption cost, “Pair” and “Exp” represent the number of pairings and exponentiations in groups. l′ is the number of attributes used during decryption. |G| indicates the group order, “P” is for prime, and “C” is for composite order, respectively. “Assu.” and “Secu.” are abbreviation of assumption and security, respectively.
Ref.
|
A
P
K
|
|
S
K
|
|
C
T
|
T
D
e
c
Assu.
|
G
|
Secu.
G
1
G
T
G
1
/
G
2
G
1
G
T
Pair
Exp
[11]
n
n
n
2
l
l
+
1
l
′
+
1
3
l
′
Static
C
Full
[29]
1
1
2
n
3
l
l
+
1
2
l
′
+
1
4
l
′
q-type
P
Static
[13]
55
n
1
11
n
11
l
1
11
l
′
l
′
DLIN
P
Full
Ours
3
k
2
(
n
+
1
)
k
n
3
k
n
3
k
(
l
+
1
)
l
+
1
6
k
6
k
l
′
+
l
′
k-Lin
P
Full
3
(
n
+
1
)
n
3
n
3
(
l
+
1
)
l
+
1
6
7
l
′
SXDH
12
(
n
+
1
)
2
n
6
n
6
(
l
+
1
)
l
+
1
12
13
l
′
DLIN


## 7. Conclusions

In this paper, we presented a fully secure decentralized CP-ABE scheme under the standardk-Lin assumptions in prime-order groups. To prove the security of our scheme, we extended the basis of dual system groups from 2k×2k matrix to 3k×3k matrix and realized some assumptions to mimic the effect of the subgroup decision assumption in composite-order groups. Our scheme achieved lower computational cost thanks to decryption which only needs constant number of pairing operations. We discussed the performance of our scheme from the theoretical points of view. Compared with other existing decentralized CP-ABE schemes, our scheme is more compact to implement and can provide better efficiency in terms of the communication and computation cost.



---

*Source: 7323158-2017-10-18.xml*