# A CP-ABE Scheme Supporting Arithmetic Span Programs

Authors: Chao Ma; Haiying Gao; Duo Wei
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Attribute-based encryption achieves fine-grained access control, especially in a cloud computing environment. In a ciphertext-policy attribute-based encryption (CP-ABE) scheme, the ciphertexts are associated with the access policies, while the secret keys are determined by the attributes. In recent years, people have tried to find more effective access structures to improve the efficiency of encryption systems. This paper presents a ciphertext-policy attribute-based encryption scheme that supports arithmetic span programs. On the composite-order bilinear group, the security of the scheme is proven by experimental sequence based on the combination of composite-order bilinear entropy expansion lemma and subgroup decision (SD) assumption. And, it is an adaptively secure scheme with constant-size public parameters.


---

## Body

## 1. Introduction

In the cloud computing environment, the traditional public key encryption system cannot meet the realistic needs due to the feature that it only achieves one-to-one encrypted data sharing. In 2006, Goyal et al. [1] proposed attribute-based encryption (ABE), which can achieve one-to-many encryption, making the sharing of encrypted data more convenient. Besides, the encrypter does no need to know the specific identifying information of the visitors but only needs to use the access structure to complete the access control of the user’s identity on the fine-grained level, which provides a new idea for data sharing. ABE is divided into two types based on ciphertexts or keys being marked as attributes. For example, in a CP-ABE scheme, keys are marked as attributes and the ciphertexts are linked with access policies. Conversely, the key-policy ABE (KP-ABE) means that keys are linked with access policies and the ciphertexts are marked as a series of attributes.In 2006, Goyal et al. [1] came up with a KP-ABE scheme that supports an access tree. The size of the public parameters is linearly related to the size of the attributes, that is, the size is not constant. In 2008, Katz et al. [2] put forward the first KP-ABE scheme based on the inner product on the composite-order bilinear group. It is a selectively secure scheme, and the length of the ciphertext increases linearly with the vector’s dimension. In 2010, Herranz et al. [3] proposed a CP-ABE scheme with a constant-size ciphertext, but it only supports the threshold access control. In 2011, based on dual pairing vector space, Okamoto and Takashima [4] presented a zero-inner product encryption scheme and a nonzero inner product encryption scheme which are fully secure under the standard model, in which the ciphertext’s length or the key’s length can reach a constant. In 2011, Attrapadung et al. [5] first proposed a KP-ABE scheme that supports the nonmonotonic access control. The scheme has a constant-size ciphertext, but it can only be proved under the selective model. In 2013, Chen et al. [6] gave a general construction method from inner product encryption to ABE and presented an ABE scheme supporting threshold access control based on inner product encryption. This scheme achieves adaptive security with constant-size ciphertext. In 2014, Wee [7] first proposed an ABE scheme supporting the arithmetic span programs [8], but did not give a specific scheme (just a framework). In 2015, Attrapadung et al. [9] proposed a general conversion between the ABE scheme supporting the arithmetic span programs and the KP-ABE scheme when we do not limit the size of the span programs, but the size of the attributes is limited. This scheme achieves adaptive security with a constant-size ciphertext, but the length of the public parameters is still not constant. In 2017, Chen et al. [10] first proposed a KP-ABE scheme supporting arithmetic span programs via bilinear entropy expansion, and the scheme is adaptive security with constant-size parameters. In particular, Table 1 illustrates the development of ABE about the access structure. Besides, the existing ABE scheme can be converted into a scheme supporting the arithmetic span program. Compared with the ABE scheme achieved by the Boolean circuit, the computational complexity and parameter size of the scheme supporting the arithmetic span program are relatively small. Therefore, based on the fact that the composite-order bilinear group has fewer algorithm components and the algorithm represents simple and clear advantages, we naturally think of the following question about ABE:“Can we design a CP-ABE scheme that supports arithmetic span program on a bilinear group?”Table 1
Development of ABE about access structure.
Scheme
Access policy
Access structure
Parameter
Security
[1]
KP
AND and OR gates
Not constant
Selective
[2]
KP
Inner product
Not constant
Selective
[3]
CP
Threshold
Constant
①
[4]
KP
Inner product
Constant
Adaptive
[5]
KP
Nonmonotonic
Constant
Selective
[6]
Both
Threshold
Constant
Adaptive
[7]
②
Arithmetic span programs
[10]
KP
Arithmetic span programs
Constant
Adaptive
Our
CP
Arithmetic span programs
Constant
Adaptive
①: the security of the scheme against selectively chosen plaintext attacks can be proven in the standard model; ②: this paper did not give a specific scheme (just a framework).


### 1.1. Our Contribution

Although CP-ABE and KP-ABE have many similarities in structure, even a dual relationship, the application scenarios are very different. In the CP-ABE scheme, because the policy is embedded in ciphertext, the data owner can set policies to determine which properties can access the ciphertext. That is, encrypted access control for this data can be refined to the attribute level. The application scenario of CP-ABE is usually data encryption storage and fine-grained sharing on the public cloud, while the application scenario of KP-ABE is more inclined to pay video websites, log encryption management, and so on. Inspired by [10], we consider designing an adaptively secure CP-ABE scheme. There are some schemes supporting arithmetic span programs [10, 11], where [10, 11] are KP-ABE schemes. However, considering that the composite-order group has fewer algorithm components and the algorithm represents simple and clear advantages, it is meaningful to construct a CP-ABE scheme on composite-order groups. Specifically, to reduce the parameter size, we first give the composite-order bilinear entropy expansion lemma, which contains the specific form of public parameters, ciphertext, and the key. In the setup, we use some random numbers as the master secret key and use the master secret key to calculate the master public key. In the Enc, we subtly embed the strategy into certain components of the ciphertext in combination with the public parameters and the bilinear entropy extension vector. In the KeyGen, we combine the attribute vector, the public parameter, and the bilinear entropy extension vector to generate the secret key. In the Dec, the arithmetic span program is used as a standard for decryption and the user can decrypt normally. Finally, based on SD assumption and composite-order bilinear entropy expansion lemma, the scheme is proved to have adaptive security.


### 1.2. Organization

We first list some relevant knowledge in Section2. Then, we present the formal definition of our scheme in Section 3.1 and propose the adaptive security model in Section 3.2. Specifically, we present our scheme in Section 3.3 and verify its correctness in Section 3.4. Finally, we prove its adaptive security by a series of experiments in Section 3.5.


## 1.1. Our Contribution

Although CP-ABE and KP-ABE have many similarities in structure, even a dual relationship, the application scenarios are very different. In the CP-ABE scheme, because the policy is embedded in ciphertext, the data owner can set policies to determine which properties can access the ciphertext. That is, encrypted access control for this data can be refined to the attribute level. The application scenario of CP-ABE is usually data encryption storage and fine-grained sharing on the public cloud, while the application scenario of KP-ABE is more inclined to pay video websites, log encryption management, and so on. Inspired by [10], we consider designing an adaptively secure CP-ABE scheme. There are some schemes supporting arithmetic span programs [10, 11], where [10, 11] are KP-ABE schemes. However, considering that the composite-order group has fewer algorithm components and the algorithm represents simple and clear advantages, it is meaningful to construct a CP-ABE scheme on composite-order groups. Specifically, to reduce the parameter size, we first give the composite-order bilinear entropy expansion lemma, which contains the specific form of public parameters, ciphertext, and the key. In the setup, we use some random numbers as the master secret key and use the master secret key to calculate the master public key. In the Enc, we subtly embed the strategy into certain components of the ciphertext in combination with the public parameters and the bilinear entropy extension vector. In the KeyGen, we combine the attribute vector, the public parameter, and the bilinear entropy extension vector to generate the secret key. In the Dec, the arithmetic span program is used as a standard for decryption and the user can decrypt normally. Finally, based on SD assumption and composite-order bilinear entropy expansion lemma, the scheme is proved to have adaptive security.


## 1.2. Organization

We first list some relevant knowledge in Section2. Then, we present the formal definition of our scheme in Section 3.1 and propose the adaptive security model in Section 3.2. Specifically, we present our scheme in Section 3.3 and verify its correctness in Section 3.4. Finally, we prove its adaptive security by a series of experiments in Section 3.5.


## 2. Preliminaries

Notation. We letZp denote a ring of algebraic integers modules a prime number p and Zpn denote an m-dimension vector in Zp. GN and e represent a group of order N and a bilinear map, respectively. We denote n as the set 1,2,…,n and n-dimensional vector as the bold letter x=x1,x2,…,xn.


### 2.1. Bilinear Maps

Definition 1 (see [12, 13] bilinear maps).
LetGN, HN, and GT be bilinear groups of order N=p1p2p3, where p1,p2,andp3 are primes. Let g be the generator of GN and g1,g2,andg3 the generators of gp1,gp2,andgp3, respectively. Let h be the generator of HN, and h1,h2,andh3 are the generators of Hp1,Hp2,andHp3, respectively.
e
:
G
N
,
H
N
⟶
G
T is a bilinear map, if it satisfies the following three properties:(1)
Bilinearity:eg0a,h0a=eg0,h0ab for all a,b∈Zp,g0∈GN,h0HN.(2)
Nondegeneracy: there existsg0∈GN,h0HN, such that the order of eg0,h0 is N.(3)
Computability: for allg0∈GN,h0HN, there is an efficient algorithm to compute eg0,h0.
Also, the composite-order bilinear map satisfies the orthogonalityegi,hj=1, for all i,j∈1,2,3,i≠j.


### 2.2. Arithmetic Span Program

Definition 2 (arithmetic span program [8]).
An arithmetic span programυ,ρ is a map ρ:l⟶n, and a collection of row vectors υ=yj,zj:j∈l,yj,zj∈Zpl′, for x=x1,x2,…,xn∈0,1n, x∈Zpn satisfies υ,ρ iff there exists constants ω1,…,ω1∈Zp, such that(1)∑j=1lωjyj+xρjzj=1,where 1≔1,0,…,∈Zpl′.
Like in paper [9], we limit ρ to be an identity map and l=n.


### 2.3. Computational Assumptions

Assumption 1 (SDp2⟶p2p3HN [12, 13]).
We define the subgroup decision assumption (denoted bySDp2⟶p2p3HN) holds if for all probability polynomial time (PPT) adversaries A, and the following advantage function is negligible in λ:(2)AdvASDp2⟶p2p3HNλ≔PrAG,D,T0=1−PrAG,D,T1=1,where(3)D≔h1,h2,h3,g1,g2,g23,g12⟵Gp2p3R,T0⟵Hp2R,T1⟵Hp2p3R.Assumption 2.
(DDHp2GN)The p2-DDH assumption (denoted by DDHp2GN), holds if for all probability polynomial time (PPT) adversaries A, and the following advantage function is negligible in λ:(4)AdvADDHp2GNλ=PrAG,D,T0=1−PrAG,D,T1=1,where(5)D=h1,h2,h3,g1,g2,g3,T0=g2x,g2y,g2xy,T1=g2x,g2y,g2z,x,y,z⟵ZNR.


### 2.4. Bilinear Entropy Expansion Lemma

For an adversaryA, the advantage of distinguishing the following two distributions in any polynomial time is negligible:(6)aux:g1,g1w,g1w0,g1w1,g1w′,g1w0′,g1w1′ct:C0=g1s,C0,j=g1sjw,C0,j′=g1sjw′,C1,j=g1sjC2,j=g1sjw0+jw1,C2,j′=g1sjw0′+jw1′j∈nsk:K1=h1r,K1,j=h1rw+rjw0+jw1,K2,j=h1rjK1,j′=h1rw′+rj′w0′+jw1′,K2,j′=h1rj′j∈n≈aux:g1,g1w,g1w0,g1w1,g1w′,g1w0′,g1w1′ct:C0=g1sg2s,C0,j=g1sjwg2sjvj,C0,j′=g1sjw′g2sjvj′,C1,j=g1sjg2sjC2,j=g1sjw0+jw1g2sjuj,C2,j′=g1sjw0′+jw1′g2sjuj′j∈nsk:K1=h1rh2r,K1,j=h1rw+rjw0+jw1h2rvj+rjuj,K2,j=h1rjh2rj,K1,j′=h1rw′+rj′w0′+jw1′h2rvj′+rjuj′,K2,j′=h1rj′h2rj′j∈n,where(7)w,w0,w1,w′,w0′,w1′⟵ZNR,vj,uj,vj′,uj′⟵ZNR,s,sj⟵ZNR,rj,rj′⟵ZNR.See Appendix for details about the proof of this lemma.


## 2.1. Bilinear Maps

Definition 1 (see [12, 13] bilinear maps).
LetGN, HN, and GT be bilinear groups of order N=p1p2p3, where p1,p2,andp3 are primes. Let g be the generator of GN and g1,g2,andg3 the generators of gp1,gp2,andgp3, respectively. Let h be the generator of HN, and h1,h2,andh3 are the generators of Hp1,Hp2,andHp3, respectively.
e
:
G
N
,
H
N
⟶
G
T is a bilinear map, if it satisfies the following three properties:(1)
Bilinearity:eg0a,h0a=eg0,h0ab for all a,b∈Zp,g0∈GN,h0HN.(2)
Nondegeneracy: there existsg0∈GN,h0HN, such that the order of eg0,h0 is N.(3)
Computability: for allg0∈GN,h0HN, there is an efficient algorithm to compute eg0,h0.
Also, the composite-order bilinear map satisfies the orthogonalityegi,hj=1, for all i,j∈1,2,3,i≠j.


## 2.2. Arithmetic Span Program

Definition 2 (arithmetic span program [8]).
An arithmetic span programυ,ρ is a map ρ:l⟶n, and a collection of row vectors υ=yj,zj:j∈l,yj,zj∈Zpl′, for x=x1,x2,…,xn∈0,1n, x∈Zpn satisfies υ,ρ iff there exists constants ω1,…,ω1∈Zp, such that(1)∑j=1lωjyj+xρjzj=1,where 1≔1,0,…,∈Zpl′.
Like in paper [9], we limit ρ to be an identity map and l=n.


## 2.3. Computational Assumptions

Assumption 1 (SDp2⟶p2p3HN [12, 13]).
We define the subgroup decision assumption (denoted bySDp2⟶p2p3HN) holds if for all probability polynomial time (PPT) adversaries A, and the following advantage function is negligible in λ:(2)AdvASDp2⟶p2p3HNλ≔PrAG,D,T0=1−PrAG,D,T1=1,where(3)D≔h1,h2,h3,g1,g2,g23,g12⟵Gp2p3R,T0⟵Hp2R,T1⟵Hp2p3R.Assumption 2.
(DDHp2GN)The p2-DDH assumption (denoted by DDHp2GN), holds if for all probability polynomial time (PPT) adversaries A, and the following advantage function is negligible in λ:(4)AdvADDHp2GNλ=PrAG,D,T0=1−PrAG,D,T1=1,where(5)D=h1,h2,h3,g1,g2,g3,T0=g2x,g2y,g2xy,T1=g2x,g2y,g2z,x,y,z⟵ZNR.


## 2.4. Bilinear Entropy Expansion Lemma

For an adversaryA, the advantage of distinguishing the following two distributions in any polynomial time is negligible:(6)aux:g1,g1w,g1w0,g1w1,g1w′,g1w0′,g1w1′ct:C0=g1s,C0,j=g1sjw,C0,j′=g1sjw′,C1,j=g1sjC2,j=g1sjw0+jw1,C2,j′=g1sjw0′+jw1′j∈nsk:K1=h1r,K1,j=h1rw+rjw0+jw1,K2,j=h1rjK1,j′=h1rw′+rj′w0′+jw1′,K2,j′=h1rj′j∈n≈aux:g1,g1w,g1w0,g1w1,g1w′,g1w0′,g1w1′ct:C0=g1sg2s,C0,j=g1sjwg2sjvj,C0,j′=g1sjw′g2sjvj′,C1,j=g1sjg2sjC2,j=g1sjw0+jw1g2sjuj,C2,j′=g1sjw0′+jw1′g2sjuj′j∈nsk:K1=h1rh2r,K1,j=h1rw+rjw0+jw1h2rvj+rjuj,K2,j=h1rjh2rj,K1,j′=h1rw′+rj′w0′+jw1′h2rvj′+rjuj′,K2,j′=h1rj′h2rj′j∈n,where(7)w,w0,w1,w′,w0′,w1′⟵ZNR,vj,uj,vj′,uj′⟵ZNR,s,sj⟵ZNR,rj,rj′⟵ZNR.See Appendix for details about the proof of this lemma.


## 3. CP-ABE Supporting Arithmetic Span Programs

### 3.1. Formal Definition of the CP-ABE Scheme Supporting Arithmetic Span Program

Setup
l
λ
,
l
n: input security parameters lλ,ln and output the master public key mpk and the master secret key msk.
Enc
mpk
,
υ
,
m: input access structure υ=yj,zj:j∈n,yj,zj∈Zpl′ and plaintext m and output ciphertext ctυ.
KeyGen
mpk
,
msk
,
x: input the vector x∈Zpn and output the secret key skx.
Dec
mpk
,
sk
x
,
ct
υ: input skx and ctυ and output m if x,υ satisfies ∑j=1lωjyj+xjzj=1.


### 3.2. Adaptively Security Model for CP-ABE Schemes Supporting Arithmetic Span Programs

We present an adaptive security model of the CP-ABE scheme that supports the arithmetic span program through the games about the challengerB and adversary A.Setup1: challenger B runs the initialization algorithm and sends mpk to adversary A.Stage1: adversary A chooses x′ to perform multiple secret key queries. Challenger B runs the KeyGen and sends the secret key to the adversary A.Challenge: adversary A sends two equal-length plaintexts (m0 and m1) and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ to challenger B (any query vector x′ and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ do not satisfy ∑j=1lωjyj+xjzj=1). Challenger B chooses b∈0,1 randomly and computes ctυ∗=Encmpk,υ∗,mb. Then, Challenger B sends the challenge ciphertext ctυ∗ to the adversary A.Stage2: same as Stage1.Guess: adversary A outputs the guess b′ about b.We say adversaryA wins this game iff b′=b, and the advantage of adversary A is AdvAλ=Prb′=b−1/2.The encryption scheme is adaptively secure if the advantages of winning the above games are negligible, for all PPT adversaries.


### 3.3. Our Construction

Setup
1
λ
,
1
n: input the number of security parameters λ and attributes n and select G≔N=p1p2p3,GN,HN,e⟵G1λ. Pick random generators g1, h1, and h123 of Gp1, Hp1, and HN, respectively. Sample w,w0,w1,w′,w0′,w1′,α,u0⟵ZNR and output the master public key
(8)
mpk
=
N
,
G
N
,
H
N
,
e
;
g
1
,
g
1
w
,
g
1
w
0
,
g
1
w
1
,
g
1
w
′
,
g
1
w
0
′
,
g
1
w
1
′
,
g
1
u
0
,
e
g
1
,
h
123
α
,
and the master secret key
(9)
msk
=
h
123
,
h
1
,
α
,
w
,
w
0
,
w
1
,
w
′
,
w
0
′
,
w
1
′
,
u
0
.
Enc
mpk
,
υ
,
m: input the access structure υ=yj,zj:j∈l,yj,zj∈ℤpl′ and the message m∈0,1λ. Select s,sj⟵ZNR,u⟵ZNl′−1R for all j∈n. Compute and output
(10)
ct
υ
=
C
0
=
g
1
s
C
0
,
j
=
g
1
s
y
j
u
0
u
+
s
j
w
,
C
0
,
j
′
=
g
1
s
z
j
u
0
u
+
s
j
w
′
C
1
,
j
=
g
1
s
j
,
C
2
,
j
=
g
1
s
j
w
0
+
j
w
1
,
C
2
,
j
′
=
g
1
s
j
w
0
′
+
j
w
1
′
j
∈
n
C
=
e
g
1
,
h
123
α
s
⋅
m
.
KeyGen
mpk
,
msk
,
x: input the master secret key msk and vector x=x1,x2,…,xn∈Zpn. Select r,rj,rj′⟵ZNR for all j∈n and output
(11)
sk
x
=
K
0
=
h
123
α
h
1
u
0
r
,
K
1
=
h
1
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
K
2
,
j
=
h
1
r
j
,
K
2
,
j
′
=
h
1
r
j
′
j
∈
n
.
Dec
mpk
,
sk
x
,
ct
υ: input secret key skx and ciphertext ctυ. If x,υ satisfies ∑j=1lωjyj+xjzj=1, then compute m=C⋅C′/eC0,K0where(12)C′=∏j=1neC0,j⋅C0,j′xj,K1⋅eC1,j,K1,j−1⋅eC2,j,K2,j⋅eC2,jxj,K2,j′ωj.


### 3.4. Correctness

For allx,υ satisfies ∑j=1lωjyj+xjzj=1, we compute(13)eC0,j⋅C0,j′xj,K1⋅eC1,j,K1,j−1⋅eC2,j,K2,j⋅eC2,jxj,K2,j′=eg1syju0u+sjw+xjszju0u+xjsjw′,h1r⋅eg1sj,h1rw+xjw′+rjw0+jw1+xjrj′w0′+jw1′−1⋅eg1sjw0+jw1,h1rj⋅eg1xjsjw0′+jw1′,h1rj′=eg1,h1rsyju0u+rsjw+rxjszu0u+rxjsjw′⋅eg1,h1−rsjw+xjw′−rjsjw0+jw1−xjrj′sjw0′+jw1′⋅eg1,h1rjsjw0+jw1⋅eg1,h1xjrj′sjw0′+jw1′=eg1,h1rsyju0u+rsjw+rxjszju0u+rxjsjw′−rsjw+xjw′−rjsjw0+jw1−xjrj′sjw0′+jw1′+rjsjw0+jw1+xjrj′sjw0′+jw1′=eg1,h1rsyju0u+xjzu0u,C′=∏j=1neC0,j⋅C0,j′xj,K1⋅eC1,j,K1,j−1⋅eC2,j,K2,j⋅eC2,jxj,K2,j′ωj=∏j=1neg1,h1rsyju0u+xjzu0uωj=eg1,h1rs∑j=1nωjyju0u+xjzu0u=eg1,h1rsu0,C⋅C′eC0,K0=eg1,h123αs⋅m⋅eg1,h1rsu0eg1s,h123α⋅h1u0r=eg1,h123αs⋅m⋅eg1,h1rsu0eg1s,h123α⋅eg1s,h1u0r=eg1,h123αs⋅eg1,h1rsu0⋅meg1,h123αs⋅eg1,h1rsu0=m.


### 3.5. Security

The proof of the security relies on a series of games that cannot be distinguished. We first define the ciphertext and secret key distributions that are needed in the process of the proof.


#### 3.5.1. Ciphertext Distributions

Standard ciphertext: generated by the encryption algorithm:
(14)
ct
υ
=
C
0
=
g
1
s
C
0
,
j
=
g
1
s
y
j
u
0
u
+
S
j
w
,
C
0
,
j
′
=
g
1
s
z
j
u
0
u
+
s
j
w
′
C
1,j
=
g
1
s
j
,
C
2
,
j
=
g
1
s
j
w
0
+
j
w
1
,
C
2
,
j
′
=
g
1
s
j
w
0
′
+
j
w
1
′
j
∈
n
C
=
e
g
1
,
h
123
α
s
⋅
m
.
Entropy expansion ciphertext: the difference between it and standard ciphertext is given as follows:w⟶vjmodp2,w′⟶vj′modp2,w0+jw1⟶ujmodp2,w0′+jw1′⟶uj′modp2∀j∈n,
(15)
ct
υ
=
C
0
=
g
1
s
g
2
s
C
0
,
j
=
g
1
s
y
j
u
0
u
+
S
j
w
g
2
s
v
j
,
C
0
,
j
′
=
g
1
s
z
j
u
0
u
+
s
j
w
′
g
2
s
v
j
′
C
1,j
=
g
1
s
j
g
2
s
j
,
C
2
,
j
=
g
1
s
j
w
0
+
j
w
1
g
2
s
j
u
j
,
C
2
,
j
′
=
g
1
s
j
w
0
′
+
j
w
1
′
g
2
s
j
u
j
′
j
∈
n
C
=
e
g
1
s
g
2
s
,
h
123
α
⋅
m
.


#### 3.5.2. Secret Key Distributions

Standard secret key: it is generated by the secret key generation algorithm:
(16)
sk
x
=
K
0
=
h
123
α
h
1
u
0
r
,
K
1
=
h
1
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
K
2
,
j
=
h
1
r
j
,
K
2
,
j
′
=
h
1
r
j
′
j
∈
n
.
Entropy expansion secret key: compared to the standard secret key, we make a copy ofh1r,h1rw+xjw′+rjw0+jw1+xjrj′w0′+jw1′,h1rj,h1rj′j∈n in Hp3:
(17)
sk
x
=
K
0
=
h
123
α
h
1
u
0
r
,
K
1
=
h
1
r
h
2
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
h
2
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
r
j
′
K
2
,
j
=
h
1
r
j
h
2
r
j
,
K
2
,
j
′
=
h
1
r
j
′
h
2
r
j
′
j
∈
n
.
Pseudostandard secret key: compared to the entropy expansion secret key, we make a copy ofh2r,h2rvj+xjvj′+rjuj+xjrj′uj′,h2rj,h2rj′j∈n in Hp3:
(18)
sk
x
=
K
0
=
h
123
α
h
1
u
0
r
,
K
1
=
h
1
r
h
2
r
h
3
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
h
2
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
u
j
′
h
3
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
u
j
′
K
2
,
j
=
h
1
r
j
h
2
r
j
h
3
r
j
,
K
2
,
j
′
=
h
1
r
j
′
h
2
r
j
′
h
3
r
j
′
j
∈
n
.
Pseudosemi-functional secret key: compared to the pseudostandard secret key, we sampleα^⟵Hp3:
(19)
sk
x
=
K
0
=
h
123
α
h
3
α
^
h
1
u
0
r
,
K
1
=
h
1
r
h
2
r
h
3
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
h
2
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
u
j
′
h
3
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
u
j
′
K
2
,
j
=
h
1
r
j
h
2
r
j
h
3
r
j
,
K
2
,
j
′
=
h
1
r
j
′
h
2
r
j
′
h
3
r
j
′
j
∈
n
.
Semifunctional secret key: compared to the pseudosemi-functional secret key, we removeh3r,h3rvj+xjvj′+rjuj+xjrj′uj′,h3rj,h3rj′j∈n:
(20)
sk
x
=
K
0
=
h
123
α
h
3
α
^
h
1
u
0
r
,
K
1
=
h
1
r
h
2
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
h
2
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
u
j
′
K
2
,
j
=
h
1
r
j
h
2
r
j
,
K
2
,
j
′
=
h
1
r
j
′
h
2
r
j
′
j
∈
n
.


#### 3.5.3. Games

Assume that an adversaryA makes at most Q secret key queries. Let the advantage of A in Gamexx be denoted by Advxxλ. In the following, we describe in detail the specific details of the games, and the comparison of Gamexx is given in Table 2.Game0: the challenge ciphertext and secret keys are generated by Enc and KeyGen, respectively.Game0′: compared to Game0, all challenge ciphertext and secret keys are entropy expansion.Gamei: compared to Game0′, the first i−1 secret keys are semifunctional and the last Q−i+1 are entropy expansion.Gamei,1: compared to Gamei, modify the i′ key to the pseudostandard key.Gamei,2: compared to Gamei,1, modify the i′ key to the pseudo-semifunctional key.Gamei,3: compared to Gamei,2, modify the i′ key to the semifunctional key.GameFinal: challenge ciphertext is the entropy expansion ciphertext about a random message, while the secret keys are semifunctional.Table 2
Games for proving the adaptive security of our scheme.
Game
CT
SK
κ
<
i
κ
=
i
κ
>
i
0
Standard entropy expansion
Standard entropy expansion
0
′
i
—
Semifunctional
Entropy expansion
Entropy expansion
i,1
—
—
Pseudostandard
—
i,2
—
—
Pseudo-semifunctional
—
i,3
—
—
Semifunctional
—
Final
Random message
SemifunctionalLemma 1 (Game0≈Gcame0′).
There exists a challengerB0 who can distinguish the left and right distributions in the bilinear entropy expansion lemma with a non-negligible advantage if Adv0λ−Adv0′λ>ε, that is, TimeB0≈TimeA.Proof.
ChallengerB0 obtains the following distribution:(21)aux:g1,g1w,g1w0,g1w1,g1w′,g1w0′,g1w1′,g1u0ct:C0,C0,j,C0,j′,C1,j,C2,j,C2,j′j∈nsk:K1,K1,j,K1,j′,K2,j,K2,j′j∈n.
B
0 needs to distinguish whether it is left distribution or right in the bilinear entropy expansion lemma.Setup: pick a random generator h123 of HN. Sample α⟵ZNR and output(22)mpk=aux,eg1,h123α.Stage1: adversary A queries the secret key corresponding to the vector x′=x1′,x2′,…,xn′. Challenger B0 simulates the secret key generation algorithm and picks r∼j⟵ZNR for all j∈n. Output(23)skx′=K0=h123αh1u0r,K1=K1r∼jK1,j=K1,jr∼j⋅K1,j′xjr∼jK2,j=K2,jr∼j,K2,j′=K2,j′r∼jj∈n.Challenge: adversary A sends two equal-length plaintexts (m0 and m1) and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ to challenger B0 (any query vector x′ in Phase1 and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ do not satisfy ∑j=1nωjyj+xj′⋅zj=1). Challenger B0 picks b∈0,1 and u⟵RZNl′−1 and outputs the challenge ciphertext:(24)ctυ∗:C0=C0C0,j=g1syju0u⋅C0,j,C0,j′=g1szju0u⋅C0,j′C1,j=C1,j,C2,j=C2,j,C2,j′=C2,j′j∈nC=eC0,h123α⋅mb.Stage2: same as Stage1.Guess: adversary A outputs the guess b′ about b.Note: the output is the standard secret key and the standard challenge ciphertext ifB0 obtains the left distribution. Conversely, the output is the entropy expansion secret key and the entropy expansion challenge ciphertext if B0 obtains the right distribution. Challenger B0 also distinguishes the left and right distributions of the entropy expansion lemma with a non-negligible advantage if Adv0λ−Adv0′λ≥ε. Game0 and Game0′ cannot be distinguished due to the indistinguishability of the left and right distributions.Lemma 2 (Game0′≡Gamei).
We know it in Table2 easily.Lemma 3 (Gamei≈Gamei,1).
There exists a challengerB1 who can solve SDp2⟶p2p3HN with a non-negligible advantage if Advλ−Advi,1λ>ε, that is, TimeB1≈TimeA.Proof.
Firstly, from theSDp2⟶p2p3HN assumption, sample r˜,r˜j,r˜j′⟵ZNR for all j∈n and we have h2r˜,h2r˜j,h2r˜j′j∈n≈ch2r˜h3r˜,h2r˜jh3r˜,h2r˜j′h3r˜j∈n given g1,g23,h1,h2,h3
ChallengerB1 samples uj,vj,uj′,vj′,andα^ for all j∈n and obtains T,Tj,Tj′ with g1,g2,andh1. Then, B1 needs to distinguish whether T,Tj,Tj′ is the left distribution or right.Setup: pick random generator h123 of HN. Sample w,w0,w1,w′,w0′,w1′,α,u0⟵ZNR and output(25)mpk≔g1,g1w,g1w0,g1w1,g1w′,g1w0′,g1w1′,g1u0,eg1,h123α.Stage1: adversary A queries the secret key corresponding to vector x′=x1′,x2′,…,xn′. Challenger B1 simulates the secret key generation algorithm and samples r˜,r˜j,r˜j′⟵ZNR for all j∈n and outputs(26)skx′=K0=h123αh3α^h1u0r,K1=h1rh2rK1,j=h1r¯w+xj′w′+r¯jw0+jw1+xjr¯j′w0′+jw1′h2r¯vj+xjvj′+r¯juj+xjr¯j′uj′K2,j=h1r¯jh2r¯j,K2,j′=h1r¯j′h2r¯j′j∈nifκ<iK0=h123αh3u0r¯,K1=h1r¯TK1,j=h1r¯w+xjw′+r¯jw0+jw1+xj′r¯j′w0′+jw1′Tvj+xj′vj′TjujTj′xj′uj′K2,j=h1r¯jTj,K2,j′=h1r¯j′Tj′j∈nifκ=iK0=h123αh1u0r¯,K1=h1r¯h2r¯K1,j=h1r¯w+xj′w′+r¯jw0+jw1+xj′r¯j′w0′+jw1′h2r¯vj+xj′vj′+r¯juj+xj′r¯j′uj′K2,j=h1r¯jh2r¯j,K2,j′=h1r¯j′h2r¯j′j∈nifκ>i.Challenge: adversary A sends two equal-length plaintexts (m0 and m1) and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ to challenger B1 (any query vector x′ in Phase1 and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ do not satisfy ∑j=1nωjyj+xj′⋅zj=1). Challenger B1 picks b∈0,1 and u⟵RZNl′−1 and outputs the challenge ciphertext:(27)ctυ∗≔C0=g1sg2sC0,j=g1syju0u+sjwg2svj,C0,j′=g1szju0u+sjw′g2svj,C1,j=g1sjg2sj,C2,j=g1sjwo+jw1g2sjuj,C2,j′=g1sjwo+jw1′g2sju1′j∈nC=eC0,h123α⋅mb.Stage2: same as Stage1.Guess: adversary A outputs the guess b′ about b.Note: the output is the entropy expansion secret key ifB1 obtains the left distribution, which is T=h2r˜,Tj=h2r˜j,Tj′=h2r˜j′ The output is the entropy pseudostandard secret key if B1 obtains the right distribution, which is T=h2r˜h3r˜,Tj=h2r˜jh3r˜j,Tj′=h2r˜j′h3r˜j′. Challenger B1 also solves SDp2⟶p2p3HN with a non-negligible advantage if Adviλ−Advi,1λ>ε. Therefore, Gamei and Gamei,1 cannot be distinguished due to SDp2⟶p2p3HN.Lemma 4 (Gamei,1≡Gamei,2).
The advantage inGamei,1 and Gamei,2 satisfies Advi,1λ−Advi,2λ>ε for any adversaries A.Proof.
ChallengerB2 samples uj,vj,uj′,vj′,andα^ for all j∈n. The difference between Gamei,1 and Gamei,2 is only the i′th secret key query. The following shows that the challenger B2 cannot distinguish these two games.Setup: pick random generator h123 of HN. Sample w,w0,w1,w′,w0′,w1′,α,u0⟵ZNR and output(28)mpk≔g1,g1w,g1w0,g1w1,g1w′,g1w0′,g1w1′,g1u0,eg1,h123α.Stage1,2: adversary A queries the secret key corresponding to vector x′=x1′,x2′,…,xn′ . Challenger B2 simulates the secret key generation algorithm and samples r˜,r˜j,r˜j′⟵ZNR for all j∈n. Gamei,1 outputs(29)skx′⟶κ=iK0=h123αh1u0r˜,K1=h1r˜h2r˜h3r˜K1,j=h1r˜w+xj′w′+r˜jw0+jw1+xj′r˜j′w0′+w1′h2r′˜vj+xj′vj′+r˜juj+xj′r˜j′uj′h3r˜vj+xj′vj′+r˜juj+xj′r˜j′uj′K2,j=h1r˜jh2r˜jh3r˜j,K2,j′=h1r˜j′h2r˜j′h3r˜j′j∈n,andGamei,2 outputs(30)skx′⟶κ=iK0=h123αh3α^h1u0r˜,K1=h1r˜h2r˜h3r˜K1,j=h1r˜w+xj′w′+r˜jw0+jw1+xj′r˜j′w0′+w1′h2r′˜vj+xj′vj′+r˜juj+xj′r˜j′uj′h3r˜vj+xj′vj′+r˜juj+xj′r˜j′uj′K2,j=h1r˜jh2r˜jh3r˜j,K2,j′=h1r˜j′h2r˜j′h3r˜j′j∈n.AdversaryA observes that the only difference between Gamei,1 and Gamei,2 is i′th secret key query in K0. Firstly, h3α^h1u0r˜ and h1u0r˜ have the same distribution due to the random number α^,r˜. Secondly, the output of the decryption algorithm in Gamei,1 and Gamei,2 is the same because eg1s,h3α^=1. Therefore, the adversary A cannot distinguish these two secret keys.Challenge:Gamei,1 and Gamei,2 have the same distribution because their outputs are entropy expansion challenge ciphertext.
Obtained from the above analysis, we haveAdvi,1λ−Advi,2λ=0.Lemma 5 (Gamei,2≈Gamei,3).
There exists a challengerB3 who can solve SDp2⟶p2p3HN with a non-negligible advantage if Advi,2λ−Advi,3λ>ε. That is, TimeB3≈TimeA.Proof.
Same as Lemma3, challenger B3 samples uj,vj,uj′,vj′,α^ for all j∈n and obtains T,Tj,Tj′ with g1,g2,andh1. Then, B3 needs to distinguish whether T,Tj,Tj′ is the left distribution or right. And challenger B3 outputs(31)skx′⟶κ=iK0=h123αh3α^h1u0r^,K1=h1r˜Tjr˜K1,j=h1r˜w+xjw′+r˜jw0+jw1+xjr˜j′w0′+jw1′Tvj+xjvj′TjujTj′xjuj′K2,j=h1r˜jTj,K2,j′=h1r˜j′Tj′j∈n.
The output is a pseudo-semifunctional secret key ifB3 obtains the left distribution, which is T=h2r˜h3r˜,Tj=h2r˜jh3r˜j,Tj′=h2r˜j′h3r˜j′. The output is an entropy semifunctional secret key if B3 obtains the right distribution, which is T=h2r˜,Tj=h2r˜j,Tj′=h2r˜j'. Challenger B3 also solves SDp2⟶p2p3HN with a non-negligible advantage if Adviλ−Advi,1λ>ε. Therefore, Gamei,2 and Gamei,3 cannot be distinguished due to SDp2⟶p2p3HN.Lemma 6 (Gamei≡Gamei−1,3).
We know it in Table2 easily (in fact, they have the same secret key and challenge ciphertext).Lemma 7.
(GameQ+1≡GameFinal)Proof.
ChallengerB4 samples uj,vj,uj′,vj′ for all j∈n. The difference between these two games is the challenge ciphertext. In GameQ+1, the challenge ciphertext is obtained by m, while the challenge ciphertext in GameFinal is obtained by a random message. Let us prove that the two games are indistinguishable. Pick random generator h123 and h3 of HN and Hp3, respectively. Select α˜,α^⟵ZNR and define h123α≔h123α˜/h3α^. We simulate GameQ+1 as follows:Setup: pick random generator h123 of HN. Sample w,w0,w1,w′,w0′,w1′,α,u0⟵ZNR and output(32)mpk≔g1,g1w,g1w0,g1w1,g1w′,g1w0′,g1w1′,g1u0,eg1,h123α˜.We can removeh3α^ because eg1,h3α˜=1.Stage1: adversary A queries the secret key corresponding to vector x′=x1′,x2′,…,xn′. Challenger B4 simulates the secret key generation algorithm and picks r,rj,rj′⟵ZNR for all j∈n. Output(33)skx′=K0=h123αh1u0r,K1=h1rh2rK1,j=h1rw+xjw′+rjw0+jw1+xjrj′w0′+jw1′h2rvj+xjvj′+rjuj+xjrj′uj′K2,j=h1rjh2rj,K2,j′=h1rj′h2rj′j∈n.Challenge: adversaryA sends two equal-length plaintexts (m0 and m1) and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ to challenger B4 (any query vector x′ in Phase1 and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ do not satisfy ∑j=1nωjyj+xj′⋅zj=1). Challenger B4 picks b∈0,1 and u⟵ZNl′−1R, and the outputs challenge the ciphertext:(34)ctυ∗≔C0=g1sg2sC0,j=g1syju0u+sjwg2svj,C0,j′=g1szju0u+sjw′g2svj′C1,j=g1sjg2sj,C2,j=g1sjw0+jw1g2sjuj,C2,j′=g1sjw0′+jw1′g2sjuj′j∈nC=eg1sg2s,h123α˜⋅eg1sg2s,h3−α^⋅mb.Guess: adversary A outputs the guess b′ about b.
We haveeg1Sg2S,h123α˜⋅eg1Sg2S,h3−α^=eg1Sg2S,h123α˜⋅eg1Sg2S,h3−α^ in the entropy expansion challenge ciphertext. The distribution of eg1Sg2S,h3−α^ in GT is a uniform distribution due to the random number α^, that is, the ciphertext which encrypted from a random number and the ciphertext which encrypted from m have the same distribution. Therefore, adversary A cannot distinguish these two entropy expansion ciphertexts.
Obtained from the above analysis, we haveAdvQ+1λ−AdvFinalλ=0.Theorem 1.
Our CP-ABE scheme supporting arithmetic span programs is adaptively secure under the entropy expansion lemma and subgroup decision assumption decision. Also,(35)maxTimeB0,TimeB1,TimeB3≈TimeA.Proof.
The advantage of adversaryA in our scheme is equivalent to the advantage in Game0 under the adaptively secure model. By Lemmas 1∼7, we obtain(36)Adv0λ=Adv0λ−Adv0′λ+Adv0′λ−Adv1λ+⋯+AdvQλ−AdvQ+1λ+AdvQ+1λ−AdvFinalλ+AdvFinalλ≤Adv0λ−Adv0′λ+Adv0′λ−Adv1λ+⋯+AdvQλ−AdvQ+1λ+AdvQ+1λ−AdvFinalλ+AdvFinalλ.
By Lemma1, we know(37)Adv0λ−Adv0′λ≤ε.
By Lemma2, we know(38)Adv0′λ−Adv1λ=0.
The indistinguishability betweenGamei and Gamei+1 is due to(39)Gamei−Gamei+1=Gamei−Gamei,1+Gamei,1−Gamei,2+Gamei,2−Gamei,3+Gamei,3−Gamei+1.
By Lemma3∼6, we know(40)Adviλ−Advi+1λ≤Adviλ−Advi+1λ+Advi,1λ−Advi,2λ+Advi,2λ−Advi,3λ+Advi,3λ−Advi+1λ≤2ε.
By Lemma7, we know(41)AdvQ+1λ−AdvFinalλ=0.
Obviously, we haveAdvFinalλ=0.
In summary, the advantage of the adversaryA in Game0 is(42)Adv0λ≤2Q+1ε.
That is, our scheme is adaptively secure under the entropy expansion lemma and subgroup decision assumption.


### 3.6. Performance Analysis

At last, we show the difference between our scheme and the existing schemes that support arithmetic span programs in Table3 (where “T” represents the operation time of the bilinear mapping). Compared with [11], the size of the public parameters of our scheme is smaller (from O (n) to O (1)) and adaptive security is achieved. Compared with [10], our scheme chooses the CP-ABE suitable for more flexible application scenarios and is based on the SD assumption to prove its adaptive security.Table 3
Comparison of schemes supporting arithmetic span program.
Scheme
Access policy
MPK
Assumption
Decryption complexity
Security
[11]
KP
O (n)
DBDH
2nT
Selective
[10]
KP
O (1)
MDDH
12nT
Adaptive
Our
CP
O (1)
SD
12nT
Adaptive


## 3.1. Formal Definition of the CP-ABE Scheme Supporting Arithmetic Span Program

Setup
l
λ
,
l
n: input security parameters lλ,ln and output the master public key mpk and the master secret key msk.
Enc
mpk
,
υ
,
m: input access structure υ=yj,zj:j∈n,yj,zj∈Zpl′ and plaintext m and output ciphertext ctυ.
KeyGen
mpk
,
msk
,
x: input the vector x∈Zpn and output the secret key skx.
Dec
mpk
,
sk
x
,
ct
υ: input skx and ctυ and output m if x,υ satisfies ∑j=1lωjyj+xjzj=1.


## 3.2. Adaptively Security Model for CP-ABE Schemes Supporting Arithmetic Span Programs

We present an adaptive security model of the CP-ABE scheme that supports the arithmetic span program through the games about the challengerB and adversary A.Setup1: challenger B runs the initialization algorithm and sends mpk to adversary A.Stage1: adversary A chooses x′ to perform multiple secret key queries. Challenger B runs the KeyGen and sends the secret key to the adversary A.Challenge: adversary A sends two equal-length plaintexts (m0 and m1) and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ to challenger B (any query vector x′ and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ do not satisfy ∑j=1lωjyj+xjzj=1). Challenger B chooses b∈0,1 randomly and computes ctυ∗=Encmpk,υ∗,mb. Then, Challenger B sends the challenge ciphertext ctυ∗ to the adversary A.Stage2: same as Stage1.Guess: adversary A outputs the guess b′ about b.We say adversaryA wins this game iff b′=b, and the advantage of adversary A is AdvAλ=Prb′=b−1/2.The encryption scheme is adaptively secure if the advantages of winning the above games are negligible, for all PPT adversaries.


## 3.3. Our Construction

Setup
1
λ
,
1
n: input the number of security parameters λ and attributes n and select G≔N=p1p2p3,GN,HN,e⟵G1λ. Pick random generators g1, h1, and h123 of Gp1, Hp1, and HN, respectively. Sample w,w0,w1,w′,w0′,w1′,α,u0⟵ZNR and output the master public key
(8)
mpk
=
N
,
G
N
,
H
N
,
e
;
g
1
,
g
1
w
,
g
1
w
0
,
g
1
w
1
,
g
1
w
′
,
g
1
w
0
′
,
g
1
w
1
′
,
g
1
u
0
,
e
g
1
,
h
123
α
,
and the master secret key
(9)
msk
=
h
123
,
h
1
,
α
,
w
,
w
0
,
w
1
,
w
′
,
w
0
′
,
w
1
′
,
u
0
.
Enc
mpk
,
υ
,
m: input the access structure υ=yj,zj:j∈l,yj,zj∈ℤpl′ and the message m∈0,1λ. Select s,sj⟵ZNR,u⟵ZNl′−1R for all j∈n. Compute and output
(10)
ct
υ
=
C
0
=
g
1
s
C
0
,
j
=
g
1
s
y
j
u
0
u
+
s
j
w
,
C
0
,
j
′
=
g
1
s
z
j
u
0
u
+
s
j
w
′
C
1
,
j
=
g
1
s
j
,
C
2
,
j
=
g
1
s
j
w
0
+
j
w
1
,
C
2
,
j
′
=
g
1
s
j
w
0
′
+
j
w
1
′
j
∈
n
C
=
e
g
1
,
h
123
α
s
⋅
m
.
KeyGen
mpk
,
msk
,
x: input the master secret key msk and vector x=x1,x2,…,xn∈Zpn. Select r,rj,rj′⟵ZNR for all j∈n and output
(11)
sk
x
=
K
0
=
h
123
α
h
1
u
0
r
,
K
1
=
h
1
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
K
2
,
j
=
h
1
r
j
,
K
2
,
j
′
=
h
1
r
j
′
j
∈
n
.
Dec
mpk
,
sk
x
,
ct
υ: input secret key skx and ciphertext ctυ. If x,υ satisfies ∑j=1lωjyj+xjzj=1, then compute m=C⋅C′/eC0,K0where(12)C′=∏j=1neC0,j⋅C0,j′xj,K1⋅eC1,j,K1,j−1⋅eC2,j,K2,j⋅eC2,jxj,K2,j′ωj.


## 3.4. Correctness

For allx,υ satisfies ∑j=1lωjyj+xjzj=1, we compute(13)eC0,j⋅C0,j′xj,K1⋅eC1,j,K1,j−1⋅eC2,j,K2,j⋅eC2,jxj,K2,j′=eg1syju0u+sjw+xjszju0u+xjsjw′,h1r⋅eg1sj,h1rw+xjw′+rjw0+jw1+xjrj′w0′+jw1′−1⋅eg1sjw0+jw1,h1rj⋅eg1xjsjw0′+jw1′,h1rj′=eg1,h1rsyju0u+rsjw+rxjszu0u+rxjsjw′⋅eg1,h1−rsjw+xjw′−rjsjw0+jw1−xjrj′sjw0′+jw1′⋅eg1,h1rjsjw0+jw1⋅eg1,h1xjrj′sjw0′+jw1′=eg1,h1rsyju0u+rsjw+rxjszju0u+rxjsjw′−rsjw+xjw′−rjsjw0+jw1−xjrj′sjw0′+jw1′+rjsjw0+jw1+xjrj′sjw0′+jw1′=eg1,h1rsyju0u+xjzu0u,C′=∏j=1neC0,j⋅C0,j′xj,K1⋅eC1,j,K1,j−1⋅eC2,j,K2,j⋅eC2,jxj,K2,j′ωj=∏j=1neg1,h1rsyju0u+xjzu0uωj=eg1,h1rs∑j=1nωjyju0u+xjzu0u=eg1,h1rsu0,C⋅C′eC0,K0=eg1,h123αs⋅m⋅eg1,h1rsu0eg1s,h123α⋅h1u0r=eg1,h123αs⋅m⋅eg1,h1rsu0eg1s,h123α⋅eg1s,h1u0r=eg1,h123αs⋅eg1,h1rsu0⋅meg1,h123αs⋅eg1,h1rsu0=m.


## 3.5. Security

The proof of the security relies on a series of games that cannot be distinguished. We first define the ciphertext and secret key distributions that are needed in the process of the proof.


### 3.5.1. Ciphertext Distributions

Standard ciphertext: generated by the encryption algorithm:
(14)
ct
υ
=
C
0
=
g
1
s
C
0
,
j
=
g
1
s
y
j
u
0
u
+
S
j
w
,
C
0
,
j
′
=
g
1
s
z
j
u
0
u
+
s
j
w
′
C
1,j
=
g
1
s
j
,
C
2
,
j
=
g
1
s
j
w
0
+
j
w
1
,
C
2
,
j
′
=
g
1
s
j
w
0
′
+
j
w
1
′
j
∈
n
C
=
e
g
1
,
h
123
α
s
⋅
m
.
Entropy expansion ciphertext: the difference between it and standard ciphertext is given as follows:w⟶vjmodp2,w′⟶vj′modp2,w0+jw1⟶ujmodp2,w0′+jw1′⟶uj′modp2∀j∈n,
(15)
ct
υ
=
C
0
=
g
1
s
g
2
s
C
0
,
j
=
g
1
s
y
j
u
0
u
+
S
j
w
g
2
s
v
j
,
C
0
,
j
′
=
g
1
s
z
j
u
0
u
+
s
j
w
′
g
2
s
v
j
′
C
1,j
=
g
1
s
j
g
2
s
j
,
C
2
,
j
=
g
1
s
j
w
0
+
j
w
1
g
2
s
j
u
j
,
C
2
,
j
′
=
g
1
s
j
w
0
′
+
j
w
1
′
g
2
s
j
u
j
′
j
∈
n
C
=
e
g
1
s
g
2
s
,
h
123
α
⋅
m
.


### 3.5.2. Secret Key Distributions

Standard secret key: it is generated by the secret key generation algorithm:
(16)
sk
x
=
K
0
=
h
123
α
h
1
u
0
r
,
K
1
=
h
1
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
K
2
,
j
=
h
1
r
j
,
K
2
,
j
′
=
h
1
r
j
′
j
∈
n
.
Entropy expansion secret key: compared to the standard secret key, we make a copy ofh1r,h1rw+xjw′+rjw0+jw1+xjrj′w0′+jw1′,h1rj,h1rj′j∈n in Hp3:
(17)
sk
x
=
K
0
=
h
123
α
h
1
u
0
r
,
K
1
=
h
1
r
h
2
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
h
2
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
r
j
′
K
2
,
j
=
h
1
r
j
h
2
r
j
,
K
2
,
j
′
=
h
1
r
j
′
h
2
r
j
′
j
∈
n
.
Pseudostandard secret key: compared to the entropy expansion secret key, we make a copy ofh2r,h2rvj+xjvj′+rjuj+xjrj′uj′,h2rj,h2rj′j∈n in Hp3:
(18)
sk
x
=
K
0
=
h
123
α
h
1
u
0
r
,
K
1
=
h
1
r
h
2
r
h
3
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
h
2
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
u
j
′
h
3
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
u
j
′
K
2
,
j
=
h
1
r
j
h
2
r
j
h
3
r
j
,
K
2
,
j
′
=
h
1
r
j
′
h
2
r
j
′
h
3
r
j
′
j
∈
n
.
Pseudosemi-functional secret key: compared to the pseudostandard secret key, we sampleα^⟵Hp3:
(19)
sk
x
=
K
0
=
h
123
α
h
3
α
^
h
1
u
0
r
,
K
1
=
h
1
r
h
2
r
h
3
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
h
2
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
u
j
′
h
3
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
u
j
′
K
2
,
j
=
h
1
r
j
h
2
r
j
h
3
r
j
,
K
2
,
j
′
=
h
1
r
j
′
h
2
r
j
′
h
3
r
j
′
j
∈
n
.
Semifunctional secret key: compared to the pseudosemi-functional secret key, we removeh3r,h3rvj+xjvj′+rjuj+xjrj′uj′,h3rj,h3rj′j∈n:
(20)
sk
x
=
K
0
=
h
123
α
h
3
α
^
h
1
u
0
r
,
K
1
=
h
1
r
h
2
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
h
2
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
u
j
′
K
2
,
j
=
h
1
r
j
h
2
r
j
,
K
2
,
j
′
=
h
1
r
j
′
h
2
r
j
′
j
∈
n
.


### 3.5.3. Games

Assume that an adversaryA makes at most Q secret key queries. Let the advantage of A in Gamexx be denoted by Advxxλ. In the following, we describe in detail the specific details of the games, and the comparison of Gamexx is given in Table 2.Game0: the challenge ciphertext and secret keys are generated by Enc and KeyGen, respectively.Game0′: compared to Game0, all challenge ciphertext and secret keys are entropy expansion.Gamei: compared to Game0′, the first i−1 secret keys are semifunctional and the last Q−i+1 are entropy expansion.Gamei,1: compared to Gamei, modify the i′ key to the pseudostandard key.Gamei,2: compared to Gamei,1, modify the i′ key to the pseudo-semifunctional key.Gamei,3: compared to Gamei,2, modify the i′ key to the semifunctional key.GameFinal: challenge ciphertext is the entropy expansion ciphertext about a random message, while the secret keys are semifunctional.Table 2
Games for proving the adaptive security of our scheme.
Game
CT
SK
κ
<
i
κ
=
i
κ
>
i
0
Standard entropy expansion
Standard entropy expansion
0
′
i
—
Semifunctional
Entropy expansion
Entropy expansion
i,1
—
—
Pseudostandard
—
i,2
—
—
Pseudo-semifunctional
—
i,3
—
—
Semifunctional
—
Final
Random message
SemifunctionalLemma 1 (Game0≈Gcame0′).
There exists a challengerB0 who can distinguish the left and right distributions in the bilinear entropy expansion lemma with a non-negligible advantage if Adv0λ−Adv0′λ>ε, that is, TimeB0≈TimeA.Proof.
ChallengerB0 obtains the following distribution:(21)aux:g1,g1w,g1w0,g1w1,g1w′,g1w0′,g1w1′,g1u0ct:C0,C0,j,C0,j′,C1,j,C2,j,C2,j′j∈nsk:K1,K1,j,K1,j′,K2,j,K2,j′j∈n.
B
0 needs to distinguish whether it is left distribution or right in the bilinear entropy expansion lemma.Setup: pick a random generator h123 of HN. Sample α⟵ZNR and output(22)mpk=aux,eg1,h123α.Stage1: adversary A queries the secret key corresponding to the vector x′=x1′,x2′,…,xn′. Challenger B0 simulates the secret key generation algorithm and picks r∼j⟵ZNR for all j∈n. Output(23)skx′=K0=h123αh1u0r,K1=K1r∼jK1,j=K1,jr∼j⋅K1,j′xjr∼jK2,j=K2,jr∼j,K2,j′=K2,j′r∼jj∈n.Challenge: adversary A sends two equal-length plaintexts (m0 and m1) and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ to challenger B0 (any query vector x′ in Phase1 and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ do not satisfy ∑j=1nωjyj+xj′⋅zj=1). Challenger B0 picks b∈0,1 and u⟵RZNl′−1 and outputs the challenge ciphertext:(24)ctυ∗:C0=C0C0,j=g1syju0u⋅C0,j,C0,j′=g1szju0u⋅C0,j′C1,j=C1,j,C2,j=C2,j,C2,j′=C2,j′j∈nC=eC0,h123α⋅mb.Stage2: same as Stage1.Guess: adversary A outputs the guess b′ about b.Note: the output is the standard secret key and the standard challenge ciphertext ifB0 obtains the left distribution. Conversely, the output is the entropy expansion secret key and the entropy expansion challenge ciphertext if B0 obtains the right distribution. Challenger B0 also distinguishes the left and right distributions of the entropy expansion lemma with a non-negligible advantage if Adv0λ−Adv0′λ≥ε. Game0 and Game0′ cannot be distinguished due to the indistinguishability of the left and right distributions.Lemma 2 (Game0′≡Gamei).
We know it in Table2 easily.Lemma 3 (Gamei≈Gamei,1).
There exists a challengerB1 who can solve SDp2⟶p2p3HN with a non-negligible advantage if Advλ−Advi,1λ>ε, that is, TimeB1≈TimeA.Proof.
Firstly, from theSDp2⟶p2p3HN assumption, sample r˜,r˜j,r˜j′⟵ZNR for all j∈n and we have h2r˜,h2r˜j,h2r˜j′j∈n≈ch2r˜h3r˜,h2r˜jh3r˜,h2r˜j′h3r˜j∈n given g1,g23,h1,h2,h3
ChallengerB1 samples uj,vj,uj′,vj′,andα^ for all j∈n and obtains T,Tj,Tj′ with g1,g2,andh1. Then, B1 needs to distinguish whether T,Tj,Tj′ is the left distribution or right.Setup: pick random generator h123 of HN. Sample w,w0,w1,w′,w0′,w1′,α,u0⟵ZNR and output(25)mpk≔g1,g1w,g1w0,g1w1,g1w′,g1w0′,g1w1′,g1u0,eg1,h123α.Stage1: adversary A queries the secret key corresponding to vector x′=x1′,x2′,…,xn′. Challenger B1 simulates the secret key generation algorithm and samples r˜,r˜j,r˜j′⟵ZNR for all j∈n and outputs(26)skx′=K0=h123αh3α^h1u0r,K1=h1rh2rK1,j=h1r¯w+xj′w′+r¯jw0+jw1+xjr¯j′w0′+jw1′h2r¯vj+xjvj′+r¯juj+xjr¯j′uj′K2,j=h1r¯jh2r¯j,K2,j′=h1r¯j′h2r¯j′j∈nifκ<iK0=h123αh3u0r¯,K1=h1r¯TK1,j=h1r¯w+xjw′+r¯jw0+jw1+xj′r¯j′w0′+jw1′Tvj+xj′vj′TjujTj′xj′uj′K2,j=h1r¯jTj,K2,j′=h1r¯j′Tj′j∈nifκ=iK0=h123αh1u0r¯,K1=h1r¯h2r¯K1,j=h1r¯w+xj′w′+r¯jw0+jw1+xj′r¯j′w0′+jw1′h2r¯vj+xj′vj′+r¯juj+xj′r¯j′uj′K2,j=h1r¯jh2r¯j,K2,j′=h1r¯j′h2r¯j′j∈nifκ>i.Challenge: adversary A sends two equal-length plaintexts (m0 and m1) and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ to challenger B1 (any query vector x′ in Phase1 and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ do not satisfy ∑j=1nωjyj+xj′⋅zj=1). Challenger B1 picks b∈0,1 and u⟵RZNl′−1 and outputs the challenge ciphertext:(27)ctυ∗≔C0=g1sg2sC0,j=g1syju0u+sjwg2svj,C0,j′=g1szju0u+sjw′g2svj,C1,j=g1sjg2sj,C2,j=g1sjwo+jw1g2sjuj,C2,j′=g1sjwo+jw1′g2sju1′j∈nC=eC0,h123α⋅mb.Stage2: same as Stage1.Guess: adversary A outputs the guess b′ about b.Note: the output is the entropy expansion secret key ifB1 obtains the left distribution, which is T=h2r˜,Tj=h2r˜j,Tj′=h2r˜j′ The output is the entropy pseudostandard secret key if B1 obtains the right distribution, which is T=h2r˜h3r˜,Tj=h2r˜jh3r˜j,Tj′=h2r˜j′h3r˜j′. Challenger B1 also solves SDp2⟶p2p3HN with a non-negligible advantage if Adviλ−Advi,1λ>ε. Therefore, Gamei and Gamei,1 cannot be distinguished due to SDp2⟶p2p3HN.Lemma 4 (Gamei,1≡Gamei,2).
The advantage inGamei,1 and Gamei,2 satisfies Advi,1λ−Advi,2λ>ε for any adversaries A.Proof.
ChallengerB2 samples uj,vj,uj′,vj′,andα^ for all j∈n. The difference between Gamei,1 and Gamei,2 is only the i′th secret key query. The following shows that the challenger B2 cannot distinguish these two games.Setup: pick random generator h123 of HN. Sample w,w0,w1,w′,w0′,w1′,α,u0⟵ZNR and output(28)mpk≔g1,g1w,g1w0,g1w1,g1w′,g1w0′,g1w1′,g1u0,eg1,h123α.Stage1,2: adversary A queries the secret key corresponding to vector x′=x1′,x2′,…,xn′ . Challenger B2 simulates the secret key generation algorithm and samples r˜,r˜j,r˜j′⟵ZNR for all j∈n. Gamei,1 outputs(29)skx′⟶κ=iK0=h123αh1u0r˜,K1=h1r˜h2r˜h3r˜K1,j=h1r˜w+xj′w′+r˜jw0+jw1+xj′r˜j′w0′+w1′h2r′˜vj+xj′vj′+r˜juj+xj′r˜j′uj′h3r˜vj+xj′vj′+r˜juj+xj′r˜j′uj′K2,j=h1r˜jh2r˜jh3r˜j,K2,j′=h1r˜j′h2r˜j′h3r˜j′j∈n,andGamei,2 outputs(30)skx′⟶κ=iK0=h123αh3α^h1u0r˜,K1=h1r˜h2r˜h3r˜K1,j=h1r˜w+xj′w′+r˜jw0+jw1+xj′r˜j′w0′+w1′h2r′˜vj+xj′vj′+r˜juj+xj′r˜j′uj′h3r˜vj+xj′vj′+r˜juj+xj′r˜j′uj′K2,j=h1r˜jh2r˜jh3r˜j,K2,j′=h1r˜j′h2r˜j′h3r˜j′j∈n.AdversaryA observes that the only difference between Gamei,1 and Gamei,2 is i′th secret key query in K0. Firstly, h3α^h1u0r˜ and h1u0r˜ have the same distribution due to the random number α^,r˜. Secondly, the output of the decryption algorithm in Gamei,1 and Gamei,2 is the same because eg1s,h3α^=1. Therefore, the adversary A cannot distinguish these two secret keys.Challenge:Gamei,1 and Gamei,2 have the same distribution because their outputs are entropy expansion challenge ciphertext.
Obtained from the above analysis, we haveAdvi,1λ−Advi,2λ=0.Lemma 5 (Gamei,2≈Gamei,3).
There exists a challengerB3 who can solve SDp2⟶p2p3HN with a non-negligible advantage if Advi,2λ−Advi,3λ>ε. That is, TimeB3≈TimeA.Proof.
Same as Lemma3, challenger B3 samples uj,vj,uj′,vj′,α^ for all j∈n and obtains T,Tj,Tj′ with g1,g2,andh1. Then, B3 needs to distinguish whether T,Tj,Tj′ is the left distribution or right. And challenger B3 outputs(31)skx′⟶κ=iK0=h123αh3α^h1u0r^,K1=h1r˜Tjr˜K1,j=h1r˜w+xjw′+r˜jw0+jw1+xjr˜j′w0′+jw1′Tvj+xjvj′TjujTj′xjuj′K2,j=h1r˜jTj,K2,j′=h1r˜j′Tj′j∈n.
The output is a pseudo-semifunctional secret key ifB3 obtains the left distribution, which is T=h2r˜h3r˜,Tj=h2r˜jh3r˜j,Tj′=h2r˜j′h3r˜j′. The output is an entropy semifunctional secret key if B3 obtains the right distribution, which is T=h2r˜,Tj=h2r˜j,Tj′=h2r˜j'. Challenger B3 also solves SDp2⟶p2p3HN with a non-negligible advantage if Adviλ−Advi,1λ>ε. Therefore, Gamei,2 and Gamei,3 cannot be distinguished due to SDp2⟶p2p3HN.Lemma 6 (Gamei≡Gamei−1,3).
We know it in Table2 easily (in fact, they have the same secret key and challenge ciphertext).Lemma 7.
(GameQ+1≡GameFinal)Proof.
ChallengerB4 samples uj,vj,uj′,vj′ for all j∈n. The difference between these two games is the challenge ciphertext. In GameQ+1, the challenge ciphertext is obtained by m, while the challenge ciphertext in GameFinal is obtained by a random message. Let us prove that the two games are indistinguishable. Pick random generator h123 and h3 of HN and Hp3, respectively. Select α˜,α^⟵ZNR and define h123α≔h123α˜/h3α^. We simulate GameQ+1 as follows:Setup: pick random generator h123 of HN. Sample w,w0,w1,w′,w0′,w1′,α,u0⟵ZNR and output(32)mpk≔g1,g1w,g1w0,g1w1,g1w′,g1w0′,g1w1′,g1u0,eg1,h123α˜.We can removeh3α^ because eg1,h3α˜=1.Stage1: adversary A queries the secret key corresponding to vector x′=x1′,x2′,…,xn′. Challenger B4 simulates the secret key generation algorithm and picks r,rj,rj′⟵ZNR for all j∈n. Output(33)skx′=K0=h123αh1u0r,K1=h1rh2rK1,j=h1rw+xjw′+rjw0+jw1+xjrj′w0′+jw1′h2rvj+xjvj′+rjuj+xjrj′uj′K2,j=h1rjh2rj,K2,j′=h1rj′h2rj′j∈n.Challenge: adversaryA sends two equal-length plaintexts (m0 and m1) and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ to challenger B4 (any query vector x′ in Phase1 and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ do not satisfy ∑j=1nωjyj+xj′⋅zj=1). Challenger B4 picks b∈0,1 and u⟵ZNl′−1R, and the outputs challenge the ciphertext:(34)ctυ∗≔C0=g1sg2sC0,j=g1syju0u+sjwg2svj,C0,j′=g1szju0u+sjw′g2svj′C1,j=g1sjg2sj,C2,j=g1sjw0+jw1g2sjuj,C2,j′=g1sjw0′+jw1′g2sjuj′j∈nC=eg1sg2s,h123α˜⋅eg1sg2s,h3−α^⋅mb.Guess: adversary A outputs the guess b′ about b.
We haveeg1Sg2S,h123α˜⋅eg1Sg2S,h3−α^=eg1Sg2S,h123α˜⋅eg1Sg2S,h3−α^ in the entropy expansion challenge ciphertext. The distribution of eg1Sg2S,h3−α^ in GT is a uniform distribution due to the random number α^, that is, the ciphertext which encrypted from a random number and the ciphertext which encrypted from m have the same distribution. Therefore, adversary A cannot distinguish these two entropy expansion ciphertexts.
Obtained from the above analysis, we haveAdvQ+1λ−AdvFinalλ=0.Theorem 1.
Our CP-ABE scheme supporting arithmetic span programs is adaptively secure under the entropy expansion lemma and subgroup decision assumption decision. Also,(35)maxTimeB0,TimeB1,TimeB3≈TimeA.Proof.
The advantage of adversaryA in our scheme is equivalent to the advantage in Game0 under the adaptively secure model. By Lemmas 1∼7, we obtain(36)Adv0λ=Adv0λ−Adv0′λ+Adv0′λ−Adv1λ+⋯+AdvQλ−AdvQ+1λ+AdvQ+1λ−AdvFinalλ+AdvFinalλ≤Adv0λ−Adv0′λ+Adv0′λ−Adv1λ+⋯+AdvQλ−AdvQ+1λ+AdvQ+1λ−AdvFinalλ+AdvFinalλ.
By Lemma1, we know(37)Adv0λ−Adv0′λ≤ε.
By Lemma2, we know(38)Adv0′λ−Adv1λ=0.
The indistinguishability betweenGamei and Gamei+1 is due to(39)Gamei−Gamei+1=Gamei−Gamei,1+Gamei,1−Gamei,2+Gamei,2−Gamei,3+Gamei,3−Gamei+1.
By Lemma3∼6, we know(40)Adviλ−Advi+1λ≤Adviλ−Advi+1λ+Advi,1λ−Advi,2λ+Advi,2λ−Advi,3λ+Advi,3λ−Advi+1λ≤2ε.
By Lemma7, we know(41)AdvQ+1λ−AdvFinalλ=0.
Obviously, we haveAdvFinalλ=0.
In summary, the advantage of the adversaryA in Game0 is(42)Adv0λ≤2Q+1ε.
That is, our scheme is adaptively secure under the entropy expansion lemma and subgroup decision assumption.


## 3.5.1. Ciphertext Distributions

Standard ciphertext: generated by the encryption algorithm:
(14)
ct
υ
=
C
0
=
g
1
s
C
0
,
j
=
g
1
s
y
j
u
0
u
+
S
j
w
,
C
0
,
j
′
=
g
1
s
z
j
u
0
u
+
s
j
w
′
C
1,j
=
g
1
s
j
,
C
2
,
j
=
g
1
s
j
w
0
+
j
w
1
,
C
2
,
j
′
=
g
1
s
j
w
0
′
+
j
w
1
′
j
∈
n
C
=
e
g
1
,
h
123
α
s
⋅
m
.
Entropy expansion ciphertext: the difference between it and standard ciphertext is given as follows:w⟶vjmodp2,w′⟶vj′modp2,w0+jw1⟶ujmodp2,w0′+jw1′⟶uj′modp2∀j∈n,
(15)
ct
υ
=
C
0
=
g
1
s
g
2
s
C
0
,
j
=
g
1
s
y
j
u
0
u
+
S
j
w
g
2
s
v
j
,
C
0
,
j
′
=
g
1
s
z
j
u
0
u
+
s
j
w
′
g
2
s
v
j
′
C
1,j
=
g
1
s
j
g
2
s
j
,
C
2
,
j
=
g
1
s
j
w
0
+
j
w
1
g
2
s
j
u
j
,
C
2
,
j
′
=
g
1
s
j
w
0
′
+
j
w
1
′
g
2
s
j
u
j
′
j
∈
n
C
=
e
g
1
s
g
2
s
,
h
123
α
⋅
m
.


## 3.5.2. Secret Key Distributions

Standard secret key: it is generated by the secret key generation algorithm:
(16)
sk
x
=
K
0
=
h
123
α
h
1
u
0
r
,
K
1
=
h
1
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
K
2
,
j
=
h
1
r
j
,
K
2
,
j
′
=
h
1
r
j
′
j
∈
n
.
Entropy expansion secret key: compared to the standard secret key, we make a copy ofh1r,h1rw+xjw′+rjw0+jw1+xjrj′w0′+jw1′,h1rj,h1rj′j∈n in Hp3:
(17)
sk
x
=
K
0
=
h
123
α
h
1
u
0
r
,
K
1
=
h
1
r
h
2
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
h
2
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
r
j
′
K
2
,
j
=
h
1
r
j
h
2
r
j
,
K
2
,
j
′
=
h
1
r
j
′
h
2
r
j
′
j
∈
n
.
Pseudostandard secret key: compared to the entropy expansion secret key, we make a copy ofh2r,h2rvj+xjvj′+rjuj+xjrj′uj′,h2rj,h2rj′j∈n in Hp3:
(18)
sk
x
=
K
0
=
h
123
α
h
1
u
0
r
,
K
1
=
h
1
r
h
2
r
h
3
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
h
2
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
u
j
′
h
3
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
u
j
′
K
2
,
j
=
h
1
r
j
h
2
r
j
h
3
r
j
,
K
2
,
j
′
=
h
1
r
j
′
h
2
r
j
′
h
3
r
j
′
j
∈
n
.
Pseudosemi-functional secret key: compared to the pseudostandard secret key, we sampleα^⟵Hp3:
(19)
sk
x
=
K
0
=
h
123
α
h
3
α
^
h
1
u
0
r
,
K
1
=
h
1
r
h
2
r
h
3
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
h
2
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
u
j
′
h
3
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
u
j
′
K
2
,
j
=
h
1
r
j
h
2
r
j
h
3
r
j
,
K
2
,
j
′
=
h
1
r
j
′
h
2
r
j
′
h
3
r
j
′
j
∈
n
.
Semifunctional secret key: compared to the pseudosemi-functional secret key, we removeh3r,h3rvj+xjvj′+rjuj+xjrj′uj′,h3rj,h3rj′j∈n:
(20)
sk
x
=
K
0
=
h
123
α
h
3
α
^
h
1
u
0
r
,
K
1
=
h
1
r
h
2
r
K
1
,
j
=
h
1
r
w
+
x
j
w
′
+
r
j
w
0
+
j
w
1
+
x
j
r
j
′
w
0
′
+
j
w
1
′
h
2
r
v
j
+
x
j
v
j
′
+
r
j
u
j
+
x
j
r
j
′
u
j
′
K
2
,
j
=
h
1
r
j
h
2
r
j
,
K
2
,
j
′
=
h
1
r
j
′
h
2
r
j
′
j
∈
n
.


## 3.5.3. Games

Assume that an adversaryA makes at most Q secret key queries. Let the advantage of A in Gamexx be denoted by Advxxλ. In the following, we describe in detail the specific details of the games, and the comparison of Gamexx is given in Table 2.Game0: the challenge ciphertext and secret keys are generated by Enc and KeyGen, respectively.Game0′: compared to Game0, all challenge ciphertext and secret keys are entropy expansion.Gamei: compared to Game0′, the first i−1 secret keys are semifunctional and the last Q−i+1 are entropy expansion.Gamei,1: compared to Gamei, modify the i′ key to the pseudostandard key.Gamei,2: compared to Gamei,1, modify the i′ key to the pseudo-semifunctional key.Gamei,3: compared to Gamei,2, modify the i′ key to the semifunctional key.GameFinal: challenge ciphertext is the entropy expansion ciphertext about a random message, while the secret keys are semifunctional.Table 2
Games for proving the adaptive security of our scheme.
Game
CT
SK
κ
<
i
κ
=
i
κ
>
i
0
Standard entropy expansion
Standard entropy expansion
0
′
i
—
Semifunctional
Entropy expansion
Entropy expansion
i,1
—
—
Pseudostandard
—
i,2
—
—
Pseudo-semifunctional
—
i,3
—
—
Semifunctional
—
Final
Random message
SemifunctionalLemma 1 (Game0≈Gcame0′).
There exists a challengerB0 who can distinguish the left and right distributions in the bilinear entropy expansion lemma with a non-negligible advantage if Adv0λ−Adv0′λ>ε, that is, TimeB0≈TimeA.Proof.
ChallengerB0 obtains the following distribution:(21)aux:g1,g1w,g1w0,g1w1,g1w′,g1w0′,g1w1′,g1u0ct:C0,C0,j,C0,j′,C1,j,C2,j,C2,j′j∈nsk:K1,K1,j,K1,j′,K2,j,K2,j′j∈n.
B
0 needs to distinguish whether it is left distribution or right in the bilinear entropy expansion lemma.Setup: pick a random generator h123 of HN. Sample α⟵ZNR and output(22)mpk=aux,eg1,h123α.Stage1: adversary A queries the secret key corresponding to the vector x′=x1′,x2′,…,xn′. Challenger B0 simulates the secret key generation algorithm and picks r∼j⟵ZNR for all j∈n. Output(23)skx′=K0=h123αh1u0r,K1=K1r∼jK1,j=K1,jr∼j⋅K1,j′xjr∼jK2,j=K2,jr∼j,K2,j′=K2,j′r∼jj∈n.Challenge: adversary A sends two equal-length plaintexts (m0 and m1) and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ to challenger B0 (any query vector x′ in Phase1 and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ do not satisfy ∑j=1nωjyj+xj′⋅zj=1). Challenger B0 picks b∈0,1 and u⟵RZNl′−1 and outputs the challenge ciphertext:(24)ctυ∗:C0=C0C0,j=g1syju0u⋅C0,j,C0,j′=g1szju0u⋅C0,j′C1,j=C1,j,C2,j=C2,j,C2,j′=C2,j′j∈nC=eC0,h123α⋅mb.Stage2: same as Stage1.Guess: adversary A outputs the guess b′ about b.Note: the output is the standard secret key and the standard challenge ciphertext ifB0 obtains the left distribution. Conversely, the output is the entropy expansion secret key and the entropy expansion challenge ciphertext if B0 obtains the right distribution. Challenger B0 also distinguishes the left and right distributions of the entropy expansion lemma with a non-negligible advantage if Adv0λ−Adv0′λ≥ε. Game0 and Game0′ cannot be distinguished due to the indistinguishability of the left and right distributions.Lemma 2 (Game0′≡Gamei).
We know it in Table2 easily.Lemma 3 (Gamei≈Gamei,1).
There exists a challengerB1 who can solve SDp2⟶p2p3HN with a non-negligible advantage if Advλ−Advi,1λ>ε, that is, TimeB1≈TimeA.Proof.
Firstly, from theSDp2⟶p2p3HN assumption, sample r˜,r˜j,r˜j′⟵ZNR for all j∈n and we have h2r˜,h2r˜j,h2r˜j′j∈n≈ch2r˜h3r˜,h2r˜jh3r˜,h2r˜j′h3r˜j∈n given g1,g23,h1,h2,h3
ChallengerB1 samples uj,vj,uj′,vj′,andα^ for all j∈n and obtains T,Tj,Tj′ with g1,g2,andh1. Then, B1 needs to distinguish whether T,Tj,Tj′ is the left distribution or right.Setup: pick random generator h123 of HN. Sample w,w0,w1,w′,w0′,w1′,α,u0⟵ZNR and output(25)mpk≔g1,g1w,g1w0,g1w1,g1w′,g1w0′,g1w1′,g1u0,eg1,h123α.Stage1: adversary A queries the secret key corresponding to vector x′=x1′,x2′,…,xn′. Challenger B1 simulates the secret key generation algorithm and samples r˜,r˜j,r˜j′⟵ZNR for all j∈n and outputs(26)skx′=K0=h123αh3α^h1u0r,K1=h1rh2rK1,j=h1r¯w+xj′w′+r¯jw0+jw1+xjr¯j′w0′+jw1′h2r¯vj+xjvj′+r¯juj+xjr¯j′uj′K2,j=h1r¯jh2r¯j,K2,j′=h1r¯j′h2r¯j′j∈nifκ<iK0=h123αh3u0r¯,K1=h1r¯TK1,j=h1r¯w+xjw′+r¯jw0+jw1+xj′r¯j′w0′+jw1′Tvj+xj′vj′TjujTj′xj′uj′K2,j=h1r¯jTj,K2,j′=h1r¯j′Tj′j∈nifκ=iK0=h123αh1u0r¯,K1=h1r¯h2r¯K1,j=h1r¯w+xj′w′+r¯jw0+jw1+xj′r¯j′w0′+jw1′h2r¯vj+xj′vj′+r¯juj+xj′r¯j′uj′K2,j=h1r¯jh2r¯j,K2,j′=h1r¯j′h2r¯j′j∈nifκ>i.Challenge: adversary A sends two equal-length plaintexts (m0 and m1) and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ to challenger B1 (any query vector x′ in Phase1 and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ do not satisfy ∑j=1nωjyj+xj′⋅zj=1). Challenger B1 picks b∈0,1 and u⟵RZNl′−1 and outputs the challenge ciphertext:(27)ctυ∗≔C0=g1sg2sC0,j=g1syju0u+sjwg2svj,C0,j′=g1szju0u+sjw′g2svj,C1,j=g1sjg2sj,C2,j=g1sjwo+jw1g2sjuj,C2,j′=g1sjwo+jw1′g2sju1′j∈nC=eC0,h123α⋅mb.Stage2: same as Stage1.Guess: adversary A outputs the guess b′ about b.Note: the output is the entropy expansion secret key ifB1 obtains the left distribution, which is T=h2r˜,Tj=h2r˜j,Tj′=h2r˜j′ The output is the entropy pseudostandard secret key if B1 obtains the right distribution, which is T=h2r˜h3r˜,Tj=h2r˜jh3r˜j,Tj′=h2r˜j′h3r˜j′. Challenger B1 also solves SDp2⟶p2p3HN with a non-negligible advantage if Adviλ−Advi,1λ>ε. Therefore, Gamei and Gamei,1 cannot be distinguished due to SDp2⟶p2p3HN.Lemma 4 (Gamei,1≡Gamei,2).
The advantage inGamei,1 and Gamei,2 satisfies Advi,1λ−Advi,2λ>ε for any adversaries A.Proof.
ChallengerB2 samples uj,vj,uj′,vj′,andα^ for all j∈n. The difference between Gamei,1 and Gamei,2 is only the i′th secret key query. The following shows that the challenger B2 cannot distinguish these two games.Setup: pick random generator h123 of HN. Sample w,w0,w1,w′,w0′,w1′,α,u0⟵ZNR and output(28)mpk≔g1,g1w,g1w0,g1w1,g1w′,g1w0′,g1w1′,g1u0,eg1,h123α.Stage1,2: adversary A queries the secret key corresponding to vector x′=x1′,x2′,…,xn′ . Challenger B2 simulates the secret key generation algorithm and samples r˜,r˜j,r˜j′⟵ZNR for all j∈n. Gamei,1 outputs(29)skx′⟶κ=iK0=h123αh1u0r˜,K1=h1r˜h2r˜h3r˜K1,j=h1r˜w+xj′w′+r˜jw0+jw1+xj′r˜j′w0′+w1′h2r′˜vj+xj′vj′+r˜juj+xj′r˜j′uj′h3r˜vj+xj′vj′+r˜juj+xj′r˜j′uj′K2,j=h1r˜jh2r˜jh3r˜j,K2,j′=h1r˜j′h2r˜j′h3r˜j′j∈n,andGamei,2 outputs(30)skx′⟶κ=iK0=h123αh3α^h1u0r˜,K1=h1r˜h2r˜h3r˜K1,j=h1r˜w+xj′w′+r˜jw0+jw1+xj′r˜j′w0′+w1′h2r′˜vj+xj′vj′+r˜juj+xj′r˜j′uj′h3r˜vj+xj′vj′+r˜juj+xj′r˜j′uj′K2,j=h1r˜jh2r˜jh3r˜j,K2,j′=h1r˜j′h2r˜j′h3r˜j′j∈n.AdversaryA observes that the only difference between Gamei,1 and Gamei,2 is i′th secret key query in K0. Firstly, h3α^h1u0r˜ and h1u0r˜ have the same distribution due to the random number α^,r˜. Secondly, the output of the decryption algorithm in Gamei,1 and Gamei,2 is the same because eg1s,h3α^=1. Therefore, the adversary A cannot distinguish these two secret keys.Challenge:Gamei,1 and Gamei,2 have the same distribution because their outputs are entropy expansion challenge ciphertext.
Obtained from the above analysis, we haveAdvi,1λ−Advi,2λ=0.Lemma 5 (Gamei,2≈Gamei,3).
There exists a challengerB3 who can solve SDp2⟶p2p3HN with a non-negligible advantage if Advi,2λ−Advi,3λ>ε. That is, TimeB3≈TimeA.Proof.
Same as Lemma3, challenger B3 samples uj,vj,uj′,vj′,α^ for all j∈n and obtains T,Tj,Tj′ with g1,g2,andh1. Then, B3 needs to distinguish whether T,Tj,Tj′ is the left distribution or right. And challenger B3 outputs(31)skx′⟶κ=iK0=h123αh3α^h1u0r^,K1=h1r˜Tjr˜K1,j=h1r˜w+xjw′+r˜jw0+jw1+xjr˜j′w0′+jw1′Tvj+xjvj′TjujTj′xjuj′K2,j=h1r˜jTj,K2,j′=h1r˜j′Tj′j∈n.
The output is a pseudo-semifunctional secret key ifB3 obtains the left distribution, which is T=h2r˜h3r˜,Tj=h2r˜jh3r˜j,Tj′=h2r˜j′h3r˜j′. The output is an entropy semifunctional secret key if B3 obtains the right distribution, which is T=h2r˜,Tj=h2r˜j,Tj′=h2r˜j'. Challenger B3 also solves SDp2⟶p2p3HN with a non-negligible advantage if Adviλ−Advi,1λ>ε. Therefore, Gamei,2 and Gamei,3 cannot be distinguished due to SDp2⟶p2p3HN.Lemma 6 (Gamei≡Gamei−1,3).
We know it in Table2 easily (in fact, they have the same secret key and challenge ciphertext).Lemma 7.
(GameQ+1≡GameFinal)Proof.
ChallengerB4 samples uj,vj,uj′,vj′ for all j∈n. The difference between these two games is the challenge ciphertext. In GameQ+1, the challenge ciphertext is obtained by m, while the challenge ciphertext in GameFinal is obtained by a random message. Let us prove that the two games are indistinguishable. Pick random generator h123 and h3 of HN and Hp3, respectively. Select α˜,α^⟵ZNR and define h123α≔h123α˜/h3α^. We simulate GameQ+1 as follows:Setup: pick random generator h123 of HN. Sample w,w0,w1,w′,w0′,w1′,α,u0⟵ZNR and output(32)mpk≔g1,g1w,g1w0,g1w1,g1w′,g1w0′,g1w1′,g1u0,eg1,h123α˜.We can removeh3α^ because eg1,h3α˜=1.Stage1: adversary A queries the secret key corresponding to vector x′=x1′,x2′,…,xn′. Challenger B4 simulates the secret key generation algorithm and picks r,rj,rj′⟵ZNR for all j∈n. Output(33)skx′=K0=h123αh1u0r,K1=h1rh2rK1,j=h1rw+xjw′+rjw0+jw1+xjrj′w0′+jw1′h2rvj+xjvj′+rjuj+xjrj′uj′K2,j=h1rjh2rj,K2,j′=h1rj′h2rj′j∈n.Challenge: adversaryA sends two equal-length plaintexts (m0 and m1) and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ to challenger B4 (any query vector x′ in Phase1 and the challenge access structure υ∗=yj,zj:j∈n,yj,zj∈Zpl′ do not satisfy ∑j=1nωjyj+xj′⋅zj=1). Challenger B4 picks b∈0,1 and u⟵ZNl′−1R, and the outputs challenge the ciphertext:(34)ctυ∗≔C0=g1sg2sC0,j=g1syju0u+sjwg2svj,C0,j′=g1szju0u+sjw′g2svj′C1,j=g1sjg2sj,C2,j=g1sjw0+jw1g2sjuj,C2,j′=g1sjw0′+jw1′g2sjuj′j∈nC=eg1sg2s,h123α˜⋅eg1sg2s,h3−α^⋅mb.Guess: adversary A outputs the guess b′ about b.
We haveeg1Sg2S,h123α˜⋅eg1Sg2S,h3−α^=eg1Sg2S,h123α˜⋅eg1Sg2S,h3−α^ in the entropy expansion challenge ciphertext. The distribution of eg1Sg2S,h3−α^ in GT is a uniform distribution due to the random number α^, that is, the ciphertext which encrypted from a random number and the ciphertext which encrypted from m have the same distribution. Therefore, adversary A cannot distinguish these two entropy expansion ciphertexts.
Obtained from the above analysis, we haveAdvQ+1λ−AdvFinalλ=0.Theorem 1.
Our CP-ABE scheme supporting arithmetic span programs is adaptively secure under the entropy expansion lemma and subgroup decision assumption decision. Also,(35)maxTimeB0,TimeB1,TimeB3≈TimeA.Proof.
The advantage of adversaryA in our scheme is equivalent to the advantage in Game0 under the adaptively secure model. By Lemmas 1∼7, we obtain(36)Adv0λ=Adv0λ−Adv0′λ+Adv0′λ−Adv1λ+⋯+AdvQλ−AdvQ+1λ+AdvQ+1λ−AdvFinalλ+AdvFinalλ≤Adv0λ−Adv0′λ+Adv0′λ−Adv1λ+⋯+AdvQλ−AdvQ+1λ+AdvQ+1λ−AdvFinalλ+AdvFinalλ.
By Lemma1, we know(37)Adv0λ−Adv0′λ≤ε.
By Lemma2, we know(38)Adv0′λ−Adv1λ=0.
The indistinguishability betweenGamei and Gamei+1 is due to(39)Gamei−Gamei+1=Gamei−Gamei,1+Gamei,1−Gamei,2+Gamei,2−Gamei,3+Gamei,3−Gamei+1.
By Lemma3∼6, we know(40)Adviλ−Advi+1λ≤Adviλ−Advi+1λ+Advi,1λ−Advi,2λ+Advi,2λ−Advi,3λ+Advi,3λ−Advi+1λ≤2ε.
By Lemma7, we know(41)AdvQ+1λ−AdvFinalλ=0.
Obviously, we haveAdvFinalλ=0.
In summary, the advantage of the adversaryA in Game0 is(42)Adv0λ≤2Q+1ε.
That is, our scheme is adaptively secure under the entropy expansion lemma and subgroup decision assumption.


## 3.6. Performance Analysis

At last, we show the difference between our scheme and the existing schemes that support arithmetic span programs in Table3 (where “T” represents the operation time of the bilinear mapping). Compared with [11], the size of the public parameters of our scheme is smaller (from O (n) to O (1)) and adaptive security is achieved. Compared with [10], our scheme chooses the CP-ABE suitable for more flexible application scenarios and is based on the SD assumption to prove its adaptive security.Table 3
Comparison of schemes supporting arithmetic span program.
Scheme
Access policy
MPK
Assumption
Decryption complexity
Security
[11]
KP
O (n)
DBDH
2nT
Selective
[10]
KP
O (1)
MDDH
12nT
Adaptive
Our
CP
O (1)
SD
12nT
Adaptive


## 4. Conclusion

In this paper, we present a ciphertext-policy attribute-based encryption scheme that supports arithmetic span programs on composite-order bilinear groups. Firstly, we prove our entropy expansion lemma with a sequence of games and seven lemmas. Secondly, we prove that our scheme is adaptively secure under the conditions that entropy expansion lemma and subgroup decision assumption are true.



---

*Source: 3265871-2020-03-16.xml*