# An Efficient Key-Policy Attribute-Based Encryption Scheme with Constant Ciphertext Length

Authors: Changji Wang; Jianfa Luo
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

There is an acceleration of adoption of cloud computing among enterprises. However, moving the infrastructure and sensitive data from trusted domain of the data owner to public cloud will pose severe security and privacy risks. Attribute-based encryption (ABE) is a new cryptographic primitive which provides a promising tool for addressing the problem of secure and fine-grained data sharing and decentralized access control. Key-policy attribute-based encryption (KP-ABE) is an important type of ABE, which enables senders to encrypt messages under a set of attributes and private keys are associated with access structures
that specify which ciphertexts the key holder will be allowed to decrypt. In most existing KP-ABE scheme, the ciphertext size grows linearly with the number of attributes embedded in ciphertext. In this paper, we propose a new KP-ABE construction with constant ciphertext size. In our construction, the access policy can be expressed as any monotone access structure. Meanwhile, the ciphertext size is independent of the number of ciphertext attributes, and the number of bilinear pairing evaluations is reduced to a constant. We prove that our scheme is semantically secure in the selective-set model based on the general Diffie-Hellman exponent assumption.


---

## Body

## 1. Introduction

Cloud computing is a model for enabling ubiquitous, convenient, and on-demand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications, and services) that can be rapidly provisioned and released with minimal management effort or service provider interaction [1]. There are two main categories of cloud infrastructure: public cloud and private cloud. To take advantage of public clouds, data owners must upload their data to commercial cloud service providers which are usually considered to be semitrusted, that is, honest but curious [2]. That means the cloud service providers will try to find out as much secret information in the users’ outsourced data as possible, but they will honestly follow the protocol in general.Traditional access control techniques are based on the assumption that the server is in the trusted domain of the data owner, and therefore an omniscient reference monitor can be used to enforce access policies against authenticated users. However, in the cloud computing paradigm this assumption usually does not hold, and therefore these solutions are not applicable. There is a need for a decentralized, scalable, and flexible way to control access to cloud data without fully relying on the cloud service providers.Data encryption is the most effective in regard to preventing sensitive data from unauthorized access. In traditional public key encryption or identity-based encryption systems, encrypted data is targeted for decryption by a single known user. Unfortunately, this functionality lacks the expressiveness needed for more advanced data sharing. To address these emerging needs, Sahai and Waters [3] introduced the concept of attribute-based encryption (ABE). Instead of encrypting to individual users, in ABE system, one can embed an access policy into the ciphertext or decryption key. Thus, data access is self-enforcing from the cryptography, requiring no trusted mediator.ABE can be viewed as an extension of the notion of identity-based encryption in which user identity is generalized to a set of descriptive attributes instead of a single string specifying the user identity. Compared with identity-based encryption [4], ABE has significant advantage as it achieves flexible one-to-many encryption instead of one-to-one; it is envisioned as a promising tool for addressing the problem of secure and fine-grained data sharing and decentralized access control.There are two types of ABE depending on which of private keys or ciphertexts that access policies are associated with.In a key-policy attribute-based encryption (KP-ABE) system, ciphertexts are labeled by the sender with a set of descriptive attributes, while user's private key is issued by the trusted attribute authority captures an policy (also called the access structure) that specifies which type of ciphertexts the key can decrypt. KP-ABE schemes are suitable for structured organizations with rules about who may read particular documents. Typical applications of KP-ABE include secure forensic analysis and target broadcast [5]. For example, in a secure forensic analysis system, audit log entries could be annotated with attributes such as the name of the user, the date and time of the user action, and the type of data modified or accessed by the user action. While a forensic analyst charged with some investigation would be issued a private key that associated with a particular access structure. The private key would only open audit log records whose attributes satisfied the access policy associated with the private key. The first KP-ABE construction was provided by Goyal et al. [5], which was very expressive in that it allowed the access policies to be expressed by any monotonic formula over encrypted data. The system was proved selectively secure under the Bilinear Diffie-Hellman assumption. Later, Ostrovsky et al. [6] proposed a KP-ABE scheme where private keys can represent any access formula over attributes, including nonmonotone ones, by integrating revocation schemes into the Goyal et al. KP-ABE scheme.In a ciphertext-policy attribute-based encryption (CP-ABE) system, when a sender encrypts a message, they specify a specific access policy in terms of access structure over attributes in the ciphertext, stating what kind of receivers will be able to decrypt the ciphertext. Users possess sets of attributes and obtain corresponding secret attribute keys from the attribute authority. Such a user can decrypt a ciphertext if his/her attributes satisfy the access policy associated with the ciphertext. Thus, CP-ABE mechanism is conceptually closer to traditional role-based access control method. The first CP-ABE scheme was proposed by Bethencourt et al. in [7], but its security was proved in the generic group model. Cheung and Newport [8] gave a CP-ABE construction under the Bilinear Diffie-Hellman assumption, but policies are restricted to a single AND gate. Later, Goyal et al. proposed a generic transformational approach to transform a KP-ABE scheme into a CP-ABE scheme using universal access tree in [9]. Their construction can support access structures which can be represented by a bounded size access tree with threshold gates as its nodes, and its security proof is based on the standard Decisional Bilinear Diffie-Hellman assumption. Unfortunately, in general this methodology would yield a ciphertext blowup of O(n3.42) group elements for a Boolean formula of size n, which limits its usefulness in practice. The most efficient CP-ABE schemes in terms of ciphertext size and expressivity were proposed by Waters in [10], the size of a ciphertext depending linearly on the number of attributes involved in the specific policy for that ciphertext.ABE has drawn extensive attention from both academia and industry, many ABE schemes have been proposed, and several cloud-based secure systems using ABE schemes have been developed [11, 12]. Most research work on ABE has focused on the design of expressive schemes, where access structures can implement as complex Boolean formulas as possible. Almost all existing ABE schemes that admit reasonably expressive decryption policies produce ciphertexts whose size depends at least linearly on the number of attributes involved in the policy. Emura et al. [13] proposed the first CP-ABE scheme with constant-size ciphertext, but policies are restricted to a single AND gate. Later, Herranz et al. [14] proposed the first CP-ABE scheme supporting threshold access structure with constant-size ciphertext. Recently, Attrapadung et al. [15] proposed a CP-ABE scheme with constant-size ciphertext for threshold access policies and where private keys remain as short as in previous systems. They also showed that a class of identity-based broadcast encryption schemes with linearity property generically yields monotonic KP-ABE systems in the selective-set model, at the expense of longer private keys of size O(t×n) elements, where n denotes the maximal number of attributes embedded in the ciphertext and t is the number of attributes in the access structure. Thus, this transformation provides us with monotonic KP-ABE schemes with constant-size ciphertexts by using identity-based broadcast encryption schemes with linearity property and constant ciphertext size. However, we notice that most of existing identity-based broadcast encryption schemes with constant-size ciphertext do not satisfy the linearity property, and it is not a necessary condition for constructing a KP-ABE schemes with constant-size ciphertext. In this paper, we propose a new KP-ABE construction with constant ciphertext size by adopting the idea of the Delerablee identity-based broadcast encryption scheme [16]. In our construction, the access policy can be expressed as any monotone access structure. Meanwhile, the ciphertext size is independent of the number of ciphertext attributes, and the number of bilinear pairing evaluations is reduced to a constant. We prove that our scheme is semantically secure in the selective-set model based on the general Diffie-Hellman exponent assumption.The rest of this paper is organized as follows. Some necessary background knowledge about bilinear pairings, access structure and linear secret sharing scheme, and Delerablee identity-based broadcast encryption scheme are introduced in Section2. The syntax and security notions of KP-ABE are given in Section 3. A concrete KP-ABE construction with constant-size ciphertext and its security argument will be presented in Section 4. We conclude our work and present our future work in Section 5.


## 2. Preliminary Works

We first introduce some notations. IfS is a set, then x∈RS denotes the operation of picking an element x uniformly random from S. For a set U, we define its power set as 2U={S∣S⊆U}. Let u=(u1,…,uk)∈Zpk and v=(v1,…,vk)∈Zpk be two row vectors; we denote the standard inner product by 〈u,v〉. A function f(λ) is negligible if for every c>0, there exists a λc, such that f(λ)<1/λc for all λ>λc.


### 2.1. Bilinear Pairings and the General Decisional Diffie-Hellman Exponent Assumption

LetG1, G2, and GT be three cyclic groups of prime order p. Let g a generator of G1 and h be a generator of G2. A bilinear pairing e^:G1×G2→GT satisfies the following properties.(i)
Bilinearity: forg∈RG1,  h∈RG2, and a,b∈RZp, we have e^(ga,hb)=e^(g,h)ab.(ii)
Nondegeneracy:e^(g,h)≠1, where 1 is the identity element of GT.(iii)
Computability: there is an efficient algorithm to computee^(u,v) for u∈RG1 and v∈RG2.Let (G1, G2, GT, p, e^, and g) be defined as above with G1=G2=G. Let g∈G be a generator of G, and set gt=e^(g,g)∈GT. Let s and n be positive integers; let P∈Zp*[X1,…,Xn]s and Q∈Zp*[X1,…,Xn]s be two s-tuples of n-variant polynomials over Zp*. We write P=(p1,…,ps) and Q=(q1,…,qs) and impose that p1=q1=1. For any function h:Zp*→Ω and vector (x1,…,xn)∈Zp*n, h(P(x1,…,xn)) stands for (h(p1(x1,…,xn)),…,h(ps(x1,…,xn)))∈Ωs. We use a similar notation for the s-tuple Q. Let f∈Zp*[X1,…,Xn]. It is said that f depends on (P,Q), which we denote by f∈〈P,Q〉, when there exists a linear decomposition:
(1)f=∑1≤i,j≤s‍ai,j·pi·pj+∑1≤i≤s‍bi·qi,ai,j,bi∈Zp.As in [16], we make use of the General Decisional Diffie-Hellman Exponent (GDDHE) assumption.Definition 1.
Given the tupleH(x1,…,xn)=(gP(x1,…,xn),gtQ(x1,…,xn))∈Gs×GTs as above and T∈GT, the (P,Q,f)-GDDHE problem is to decide whether T is equal to gtf(x1,…,xn) or to some random element of GT.


### 2.2. Access Structure and Linear Secret Sharing Scheme

Definition 2.
LetP={P1,P2,…,Pn} be a set of parties. A collection 𝔸⊆2P is monotone if, for two sets B and C, B∈𝔸 and B⊆C, then C∈𝔸. An access structure (resp., monotone access structure) is a collection (resp., monotone collection) 𝔸 of nonempty subsets of P. The sets in 𝔸 are called the authorized sets, and the sets not in 𝔸 are called the unauthorized sets.Definition 3.
LetP be a set of parties, Mℓ×k an ℓ×k matrix, and ρ:{1,2,…,ℓ}→P a function that maps a row to a party for labeling. A secret sharing scheme Π for access structure 𝔸 over a set of parties P is a linear secret sharing scheme (LSSS) in Zp and is represented by (Mℓ×k,ρ) if it consists of two efficient algorithms.(i)
Share((Mℓ×k,ρ),s): the share algorithm takes as input s∈Zp which is to be shared. The dealer randomly chooses β2,…,βk∈RZp, and defines β=(s,β2,…,βk)⊺. It outputs Mℓ×k·β as the vectors of ℓ shares. The share λi=〈Mi,β⊺〉 belongs to party ρ(i), where Mi is the ith row of Mℓ×k.(ii)
Recon((Mℓ×k,ρ),S): the reconstruction algorithm takes as input an access set S∈𝔸. Let I={i∣ρ(i)∈S}. It outputs a set of constants {μi}i∈I such that ∑i∈I‍μi·λi=s.In our context, the role of the parties is taken by the attributes. Thus, the access structure will contain the authorized sets of attributes. As in most relevant literatures [5, 6, 10], we will restrict ourselves to monotone access structures. In general, access policies can be described in terms of the monotonic Boolean formulas. There are standard techniques to convert any monotonic Boolean formula into a corresponding LSSS matrix [17].


### 2.3. The Delerablee Identity-Based Broadcast Encryption Scheme

Delerablee proposed the first identity-based broadcast encryption scheme with constant-size ciphertexts and private keys [16], which is described as follows.(i)
Setup(1λ,m): given the security parameter λ and an integer m, the algorithm generates a bilinear map group system (G1, G2, GT, p, e^, g, and h) as above and chooses a secret value γ∈Zp* and a cryptographic hash function H:{0,1}*→Zp*. The master secret key is defined as msk=(g,γ), and the public system parameters are defined as params=(w,v,h,hγ,…,hγm), where w=gγ and v=e^(g,h).(ii)
Extract(msk,ID): given msk=(g,γ) and the identity ID, it outputs
(2)skID=g1/(γ+H(ID)).(iii)
Encrypt(S,params): assume for notational simplicity that S={IDj}i=1s, with s≤m. Given params=(w,v,h,hγ,…,hγm), the broadcaster randomly picks k∈RZp* and computes Hdr=(C1,C2) and K, where
(3)C1=w-k,C2=hk·∏i=1s(γ+H(IDi)),K=vk.(iv)
Decrypt(S,IDi,skIDi,andHdr,params): in order to retrieve the message encryption key K encapsulated in the header Hdr=(C1,C2), user with identity IDi and the corresponding private key skIDi=g1/(γ+H(IDi)) (with IDi∈S) computes
(4)K=(e^(C1,hpi,S(γ))·e^(skIDi,C2))1/∏j=1,j≠isH(IDj)with(5)pi,S(γ)=1γ·(∏j=1,j≠is‍(γ+H(IDj))-∏j=1,j≠is‍H(IDj)).Lemma 4.
The Delerablee identity-based broadcast encryption scheme is IND-sID-CPA secure under(f,g,F)-GDDHE assumption.


## 2.1. Bilinear Pairings and the General Decisional Diffie-Hellman Exponent Assumption

LetG1, G2, and GT be three cyclic groups of prime order p. Let g a generator of G1 and h be a generator of G2. A bilinear pairing e^:G1×G2→GT satisfies the following properties.(i)
Bilinearity: forg∈RG1,  h∈RG2, and a,b∈RZp, we have e^(ga,hb)=e^(g,h)ab.(ii)
Nondegeneracy:e^(g,h)≠1, where 1 is the identity element of GT.(iii)
Computability: there is an efficient algorithm to computee^(u,v) for u∈RG1 and v∈RG2.Let (G1, G2, GT, p, e^, and g) be defined as above with G1=G2=G. Let g∈G be a generator of G, and set gt=e^(g,g)∈GT. Let s and n be positive integers; let P∈Zp*[X1,…,Xn]s and Q∈Zp*[X1,…,Xn]s be two s-tuples of n-variant polynomials over Zp*. We write P=(p1,…,ps) and Q=(q1,…,qs) and impose that p1=q1=1. For any function h:Zp*→Ω and vector (x1,…,xn)∈Zp*n, h(P(x1,…,xn)) stands for (h(p1(x1,…,xn)),…,h(ps(x1,…,xn)))∈Ωs. We use a similar notation for the s-tuple Q. Let f∈Zp*[X1,…,Xn]. It is said that f depends on (P,Q), which we denote by f∈〈P,Q〉, when there exists a linear decomposition:
(1)f=∑1≤i,j≤s‍ai,j·pi·pj+∑1≤i≤s‍bi·qi,ai,j,bi∈Zp.As in [16], we make use of the General Decisional Diffie-Hellman Exponent (GDDHE) assumption.Definition 1.
Given the tupleH(x1,…,xn)=(gP(x1,…,xn),gtQ(x1,…,xn))∈Gs×GTs as above and T∈GT, the (P,Q,f)-GDDHE problem is to decide whether T is equal to gtf(x1,…,xn) or to some random element of GT.


## 2.2. Access Structure and Linear Secret Sharing Scheme

Definition 2.
LetP={P1,P2,…,Pn} be a set of parties. A collection 𝔸⊆2P is monotone if, for two sets B and C, B∈𝔸 and B⊆C, then C∈𝔸. An access structure (resp., monotone access structure) is a collection (resp., monotone collection) 𝔸 of nonempty subsets of P. The sets in 𝔸 are called the authorized sets, and the sets not in 𝔸 are called the unauthorized sets.Definition 3.
LetP be a set of parties, Mℓ×k an ℓ×k matrix, and ρ:{1,2,…,ℓ}→P a function that maps a row to a party for labeling. A secret sharing scheme Π for access structure 𝔸 over a set of parties P is a linear secret sharing scheme (LSSS) in Zp and is represented by (Mℓ×k,ρ) if it consists of two efficient algorithms.(i)
Share((Mℓ×k,ρ),s): the share algorithm takes as input s∈Zp which is to be shared. The dealer randomly chooses β2,…,βk∈RZp, and defines β=(s,β2,…,βk)⊺. It outputs Mℓ×k·β as the vectors of ℓ shares. The share λi=〈Mi,β⊺〉 belongs to party ρ(i), where Mi is the ith row of Mℓ×k.(ii)
Recon((Mℓ×k,ρ),S): the reconstruction algorithm takes as input an access set S∈𝔸. Let I={i∣ρ(i)∈S}. It outputs a set of constants {μi}i∈I such that ∑i∈I‍μi·λi=s.In our context, the role of the parties is taken by the attributes. Thus, the access structure will contain the authorized sets of attributes. As in most relevant literatures [5, 6, 10], we will restrict ourselves to monotone access structures. In general, access policies can be described in terms of the monotonic Boolean formulas. There are standard techniques to convert any monotonic Boolean formula into a corresponding LSSS matrix [17].


## 2.3. The Delerablee Identity-Based Broadcast Encryption Scheme

Delerablee proposed the first identity-based broadcast encryption scheme with constant-size ciphertexts and private keys [16], which is described as follows.(i)
Setup(1λ,m): given the security parameter λ and an integer m, the algorithm generates a bilinear map group system (G1, G2, GT, p, e^, g, and h) as above and chooses a secret value γ∈Zp* and a cryptographic hash function H:{0,1}*→Zp*. The master secret key is defined as msk=(g,γ), and the public system parameters are defined as params=(w,v,h,hγ,…,hγm), where w=gγ and v=e^(g,h).(ii)
Extract(msk,ID): given msk=(g,γ) and the identity ID, it outputs
(2)skID=g1/(γ+H(ID)).(iii)
Encrypt(S,params): assume for notational simplicity that S={IDj}i=1s, with s≤m. Given params=(w,v,h,hγ,…,hγm), the broadcaster randomly picks k∈RZp* and computes Hdr=(C1,C2) and K, where
(3)C1=w-k,C2=hk·∏i=1s(γ+H(IDi)),K=vk.(iv)
Decrypt(S,IDi,skIDi,andHdr,params): in order to retrieve the message encryption key K encapsulated in the header Hdr=(C1,C2), user with identity IDi and the corresponding private key skIDi=g1/(γ+H(IDi)) (with IDi∈S) computes
(4)K=(e^(C1,hpi,S(γ))·e^(skIDi,C2))1/∏j=1,j≠isH(IDj)with(5)pi,S(γ)=1γ·(∏j=1,j≠is‍(γ+H(IDj))-∏j=1,j≠is‍H(IDj)).Lemma 4.
The Delerablee identity-based broadcast encryption scheme is IND-sID-CPA secure under(f,g,F)-GDDHE assumption.


## 3. Syntax and Security Notions for KP-ABE Scheme

LetU={attr1,…,attrn} be the universe of possible attributes, where each attri denotes an attribute and n is the total number of attributes. A KP-ABE scheme is parameterized by a universe of possible attributes U and consists of the following four polynomial-time algorithms.(i)
Setup(1λ,U): this probabilistic algorithm is run by the trusted attribute authority, which takes as input the security parameter λ and the attribute universe U. It outputs some public parameters params and the master secret key msk. The trusted attribute authority publishes params and keeps msk secret.(ii)
KeyGen(params,msk,and𝔸): this probabilistic algorithm is run by the trusted attribute authority, which takes as input the public parameters params, the master secret key msk, and an access structure 𝔸 which is assigned by the trusted attribute authority to the user. It outputs a decryption key SK𝔸.(iii)
Encrypt(params,W,andm): this probabilistic algorithm is run by the sender, which takes as input the public parameters params, a set of descriptive attributes W, and a message m∈{0,1}*. It outputs the ciphertext c.(iv)
Decrypt(params,c,andSK𝔸): this deterministic algorithm is run by the recipient, which takes as input the public parameters params, the ciphertext c that was encrypted under the set of attributes W, and the decryption key SK𝔸 for access structure 𝔸. It outputs the message m if W∈𝔸.Definition 5.
A KP-ABE scheme is correct if, for any(params,msk)←Setup(1λ,U), any sets of attributes W⊆U, any message m∈{0,1}*, and any SK𝔸←KeyGen(params,msk,and𝔸) with W∈𝔸, one has
(6)Decrypt(params,Encrypt(params,W,andm),SK𝔸)=m
with probability 1 over the randomness of all the algorithms.The property of indistinguishability for KP-ABE scheme under chosen plaintext and attribute-set attack is called selective-set model [5], which is defined in the following game between a challenger and an adversary.(i)
Initialization: the adversary declares the set of attributesW that he wishes to be challenged on.(ii)
Setup: the challenger runs the Setup algorithm of KP-ABE scheme and gives the public parameters to the adversary.(iii)
Phase 1: the adversary is allowed to issue queries for private keys with access structure𝔸j at most qλ times with the restriction that W∉𝔸j for all j.(iv)
Challenge: the adversary submits two messagesm0 and m1 with equal length. The challenger flips a random coin b and encrypts message mb with W. The ciphertext is then sent to the adversary.(v)
Phase 2: the same as Phase 1.(vi)
Guess: the adversary outputs his guessb′ of b. The advantage of an adversary in the above game is defined as |Pr[b′=b]-1/2|.Definition 6.
A KP-ABE scheme is secure in the selective-set model if all polynomial-time adversaries have at most a negligible advantage in the selective-set game.The model can easily be extended to handle chosen ciphertext attacks by allowing for decryption queries in Phase 1 and Phase 2.


## 4. Our Construction

In this section, we present a new KP-ABE scheme with constant-size ciphertexts by adopting the idea of the Delerablee identity-based broadcast encryption scheme. The proposed KP-ABE construction is described as follows.(i)
Setup(1λ,U): given the security parameter λ, the trusted attribute authority chooses three cyclic groups G1, G2, and GT of prime order p with a bilinear pairing e^:G1×G2→GT. Then the trusted attribute authority chooses two generators g∈G1 and h∈G2 as well as a secret value α∈RZp* and a cryptographic hash function H:{0,1}*→Zp*. The security analysis will view H as a random oracle. The master secret key is defined as msk=(g,α). The public parameters are params=(w,v,h,hα,…,hαn), where w=gα and v=e^(g,h).(ii)
KeyGen(params,msk,(M,ρ)): the algorithm computes a private key for an access structure that is associated with LSSS scheme (Mℓ×k,ρ) as follows. First, it generates shares of ℓ with the LSSS (Mℓ×k,ρ). Namely, it chooses a column vector β=(β1,β2,…,βk)⊺ with β1=s=1 and β2,…,βk∈RZp. Then for each i from i=1 to i=ℓ, it calculates λi=〈Mi,β⊺〉 and sets SK(M,ρ) as follows:
(7)SK(M,ρ)={Di,(Ki,j)j=1n}i=1ℓ={gλi/(α+H(ρ(i))),(hλiαj)j=1n}i=1ℓ.(iii)
Encrypt(params,m,andW): let t be the number of attributes included in the set of attributes W, and denote W to be W={ωi}i=1t. The sender chooses s∈RZp* and computes the ciphertext c=(c0,c1,andc2), where
(8)c0=m·vs=m·e^(g,h)s,c1=w-s=g-αs,c2=hs·∏i=1t(α+H(ωi)).(iv)
Decrypt(params,c,andSK(M,ρ)): the ciphertext c labeled with the set of attributes W={ωi}i=1t is parsed as c=(c0,c1,andc2). The recipient first sets I={i∣ρ(i)∈W} and calculates the reconstruction constants {μi}i∈I=Recon((M,ρ),W). The recipient’s decryption key corresponding to the LSSS scheme (M,ρ) is parsed as SK(M,ρ)={Di,(Ki,j)j=1n}i=1ℓ. Then the recipient computes
(9)pi,W(α)=λiα(∏j=1,j≠it‍(α+H(ωj))-∏j=1,j≠it‍H(ωj)).It is obvious thatpi,W(α) is a polynomial on the variable α with degree t-2. The decrypting party can calculate hpi,W(α) according to (Ki,j)j=1n. Then the decrypting party computes
(10)Yi=(e^(c1,hpi,W(α))·e^(Di,c2))1/∏j=1,j≠itH(ωj)=e^(g,h)sλi.At last, the decrypting party calculates(11)Y=∏i∈I‍Yiμi=e^(g,h)s,m=c0Y.Theorem 7.
The proposed KP-ABE scheme is correct.Proof.
Assumec is well formed, which means c is encrypted under the set of attributes W={ωi}i=1t; thus
(12)Yi=(e^(c1,hpi,W(α))·e^(Di,c2))1/∏j=1,j≠itH(ωi)=(e^(g,h)-sα(λi/α)(∏j=1,j≠it(α+H(ωj))-∏j=1,j≠itH(ωj))·e^(g,h)sλi∏i=1t(α+H(ωj))e^(g,h)-sα(λi/α)(∏j=1,j≠it‍(α+H(ωj))-∏j=1,j≠it‍H(ωj)))1/∏j=1,j≠itH(ωi)=(e^(g,h)sλi∏i=1tH(ωj))1/∏j=1,j≠itH(ωi)=e^(g,h)sλi.
So we have(13)Y=∏i∈I‍Yiμi=∏i∈I‍e^(g,h)(sλi)μi=e^(g,h)s·∑i∈Iμi·λi=e^(g,h)s.
This ends the proof.Theorem 8.
The proposed KP-ABE scheme is secure in the selective-set model under the(f,g,F)-GDDHE assumption.Proof.
Suppose that there exists a polynomial-time adversary𝒜 that can attack the above KP-ABE scheme in the selective-set model with nonnegligible advantage. Then we can build a simulator ℬ that can attack the Delerablee identity-based broadcast encryption scheme in the selective-ID model with nonnegligible advantage. The simulation proceeds as follows.(i)
Initialization: the adversary𝒜 chooses the set of attributes W* which it wants to be challenged upon and sends W* to the simulator ℬ. Then the simulator ℬ sends this challenged attributes to the challenger 𝒞 in the selective-ID model for the Delerablee identity-based broadcast encryption scheme. They treat each attribute as an ID in the Delerablee identity-based broadcast encryption.(ii)
Setup: the challenger𝒞 generates params and msk and sends params to the simulator ℬ; then ℬ transfers them to the adversary 𝒜.(iii)
Phase 1: the adversary𝒜 adaptively makes queries for private keys for access structure (M,ρ) that cannot be satisfied by W*. The simulator ℬ picks vector β=(β1,β2,…,βk)⊺ at random and calculates λi=〈Mi,β⊺〉.
(1)
Ifρ(i)∈W*, then the simulator ℬ picks ri∈RZp* and submits the private key query ri to the challenger 𝒞. The challenger 𝒞 will computes and returns the private key skri corresponding to ri to ℬ. Finally, the simulator sets the private key part Di=(skriλi,{hλiαj}j=1,…,n).(2)
Ifρ(i)∉W*, then the simulator ℬ submits the private key query ρ(i) to the challenger 𝒞. After the simulator ℬ obtains the private key skρ(i) corresponding to ρ(i) from the challenger 𝒞, the simulator sets the private key part Di=(skρ(i)λi,{hλiαj}j=1,…,n).(3)
At last,ℬ returns sk(M,ρ)={Di}i=1,…,ℓ to the adversary 𝒜.(iv)
Challenge: the adversary𝒜 randomly chooses two messages m0 and m1 with equal length and sends them to the simulator ℬ. The simulator ℬ then sends them to the challenger 𝒞. The challenger 𝒞 randomly encrypts mb with the attributes set W* and returns cb to the simulator ℬ. Finally, the simulator ℬ sends it to the adversary 𝒜.(v)
Guess: the adversary𝒜 returns the guess b′ to the simulator ℬ, and then the simulator ℬ sends it to the challenger 𝒞.
According to the observation of the attacker𝒜, the private keys he obtained from the simulator ℬ are indistinguishable to those of obtained from the KeyGen algorithm. Thus, if the adversary 𝒜 can attack the proposed KP-ABE scheme in the selective-set model with nonnegligible advantage, then the simulator ℬ can attack the Delerablee identity-based broadcast encryption scheme in the selective-ID model with nonnegligible advantage. According to Lemma 4, we can draw the conclusion that the proposed KP-ABE scheme is secure in the selective-set model under the (f,g,F)-GDDHE assumption.
This ends the proof.Table1 compares efficiency among available ABE schemes with constant-size ciphertext. Attrapadung et al. [15] proposed a CP-ABE and KP-ABE scheme with constant-size ciphertexts, respectively; we denote them as [15]-1 scheme and [15]-2 scheme, respectively.Table 1
Comparisons among ABE schemes with constant-size ciphertexts.
Schemes
[13]
[14]
[15]-1
[15]-2
Our scheme
ABE types
CP-ABE
CP-ABE
CP-ABE
KP-ABE
KP-ABE
Access structure
AND
Threshold
Threshold
Monotone
Monotone
Private key size
2
|
G
|
w
|
G
1
|
+
n
|
G
2
|
(
n
+
w
)
|
G
|
+
|
Z
p
*
|
(
n
+
1
)
t
|
G
|
t
|
G
1
|
+
n
t
|
G
2
|
Ciphertext size
2
|
G
|
+
|
G
T
|
|
G
1
|
+
|
G
2
|
+
|
G
T
|
2
|
G
|
+
|
G
T
|
2
|
G
|
+
|
G
T
|
|
G
1
|
+
|
G
2
|
+
|
G
T
|
Encryption cost
0
0
1
p
1
p
1
p
Decryption cost
2
p
3
p
3
p
2
p
2
pComparisons are made in terms of private key size, ciphertext size, and the number of pairing evaluations upon encryption and decryption. In the table, we denote byn the number of attributes in the attributes universe, t the number of attributes in the access structure that describe the private key for KP-ABE scheme, w the number of attributes that describe the private key for CP-ABE scheme, and p the number of pairing evaluations.


## 5. Conclusion

In this paper, we have constructed a new KP-ABE scheme supporting any monotonic access structure with constant-size ciphertext and proved that the proposed scheme is semantically secure in selective-set model based on the general Diffie-Hellman exponent assumption. The downside of the proposed KP-ABE scheme is that private keys have multiple size growths in the number of attributes in the access structure. One interesting open problem would be to construct a KP-ABE scheme with constant-size ciphertexts that is secure under a more standard assumption or which achieves a stronger full security notion. Another challenging problem is to construct a KP-ABE scheme with constant ciphertext size and constant private key size.



---

*Source: 810969-2013-04-09.xml*