AttributeBased Encryption for FineGrained Access Control of Encrypted Data
Vipul Goyal Omkant Pandey Amit Sahai Brent WatersAbstract
As more sensitive data is shared and stored by thirdparty sites on the Internet, there will be a need to encrypt data stored at these sites. One drawback of encrypting data, is that it can be selectively shared only at a coarsegrained level i.e., giving another party your private key. We develop a new cryptosystem for finegrained sharing of encrypted data that we call KeyPolicy AttributeBased Encryption KPABE. In our cryptosystem, ciphertexts are labeled with sets of attributes and private keys are associated with access structures that control which ciphertexts a user is able to decrypt. We demonstrate the applicability of our construction to sharing of auditlog information and broadcast encryption. Our construction supports delegation of private keys which subsumes Hierarchical IdentityBased Encryption HIBE.
1 Introduction
There is a trend for sensitive user data to be stored by third parties on the Internet. For example, personal email, data, and personal preferences are stored on web portal sites such as Google and Yahoo. The attack correlation center, dshield.org, presents aggregated views of attacks on the Internet, but stores intrusion reports individually submitted by users. Given the variety, amount, and importance of information stored at these sites, there is cause for concern that personal data will be compromised. This worry is escalated by the surge in recent attacks and legal pressure faced by such services.
One method for alleviating some of these problems is to store data in encrypted form. Thus, if the storage is compromised the amount of information loss will be limited. One disadvantage of encrypting data is that it severely limits the ability of users to selectively share their encrypted data at a finegrained level. Suppose a particular user wants to grant decryption access to a party to all of its Internet traffic logs for all entries on a particular range of dates that had a source IP address from a particular subnet. The user either needs
This research was supported in part by NSF ITRCybertrust grants 0456717 and 0627781.
This research was supported in part by NSF ITRCybertrust grants 0456717 and 0627781.
This research was supported in part by an Alfred P. Sloan Foundation Research Fellowship, an Intel
equipment grant, and NSF ITRCybertrust grants 0205594, 0456717 and 0627781.
This research was supported in part by NSF, the US Army Research Office Grant No. W911NF06 10316, and the Department of Homeland Security DHS and the Department of Interior DOI under Contract No. NBCHF040146. Any opinions, finding and conclusions or recommendations expressed in this
material are those of the authors and do not necessarily reflect the views of the funding agencies.
1
to act as an intermediary and decrypt all relevant entries for the party or must give the party its private decryption key, and thus let it have access to all entries. Neither one of these options is particularly appealing. An important setting where these issues give rise to serious problems is audit logs discussed in more detail in Section 7.
Sahai and Waters 34 made some initial steps to solving this problem by introducing the concept of AttributedBased Encryption ABE. In an ABE system, a users keys and ciphertexts are labeled with sets of descriptive attributes and a particular key can decrypt a particular ciphertext only if there is a match between the attributes of the ciphertext and the users key. The cryptosystem of Sahai and Waters allowed for decryption when at least k attributes overlapped between a ciphertext and a private key. While this primitive was shown to be useful for errortolerant encryption with biometrics, the lack of expressibility seems to limit its applicability to larger systems.
Our Contribution. We develop a much richer type of attributebased encryption cryp tosystem and demonstrate its applications. In our system each ciphertext is labeled by the encryptor with a set of descriptive attributes. Each private key is associated with an access structure that specifies which type of ciphertexts the key can decrypt. We call such a scheme a KeyPolicy AttributeBased Encryption KPABE, since the access structure is specified in the private key, while the ciphertexts are simply labeled with a set of descriptive attributes.1
We note that this setting is reminiscent of secret sharing schemes see, e.g., 4. Using known techniques one can build a secretsharing scheme that specifies that a set of parties must cooperate in order to reconstruct a secret. For example, one can specify a tree access structure where the interior nodes consist of AND and OR gates and the leaves consist of different parties. Any set of parties that satisfy the tree can reconstruct the secret.
In our construction each users key is associated with a treeaccess structure where the leavesareassociatedwithattributes.2 Auserisabletodecryptaciphertextiftheattributes associated with a ciphertext satisfy the keys access structure. The primary difference between our setting and secretsharing schemes is that while secretsharing schemes allow for cooperation between different parties, in our setting, this is expressly forbidden. For instance, if Alice has the key associated with the access structure X AND Y, and Bob has the key associated with the access structure Y AND Z, we would not want them to be able to decrypt a ciphertext whose only attribute is Y by colluding. To do this, we adapt and generalize the techniques introduced by 34 to deal with more complex settings. We will show that this cryptosystem gives us a powerful tool for encryption with finegrained access control for applications such as sharing audit log information.
In addition, we provide a delegation mechanism for our construction. Roughly, this allows any user that has a key for access structure X to derive a key for access structure Y, if and only if Y is more restrictive than X. Somewhat surprisingly, we observe that our construction with the delegation property subsumes Hierarchical IdentityBased Encryption
1This contrasts with what we call CiphertextPolicy AttributeBased Encryption CPABE, where an access structure i.e. policy would be associated to each ciphertext, while a users private key would be associated with a set of attributes. KPABE and CPABE systems are useful in different contexts.
2In fact, we can extend our scheme to work for any access structure for which a Linear Secret Sharing Scheme exists see appendix A.
2
24, 21 and its derivatives 1.
1.1 Organization
We begin with a discussion of related work in Section 2. Next, we give necessary back ground information and our definitions of security in Section 3. We then present our first construction and a proof of security in Section 4 and later generalize it to work for any LSSS realizable access structure in Appendix A. We give a construction for the large universe case in Section 5. We then show how to add the delegation property in Section 6. We follow with a discussion of how our system applies to audit logs in Section 7. We discuss the application of our construction to broadcast encryption in Section 8. Finally, we discuss some interesting extensions and open problems in Section 9.
2 Related Work
Finegrained Access Control. Finegrained access control systems facilitate granting differential access rights to a set of users and allow flexibility in specifying the access rights of individual users. Several techniques are known for implementing fine grained access control.
Common to the existing techniques see, e.g., 26, 20, 38, 28, 23, 29 and the references therein is the fact that they employ a trusted server that stores the data in clear. Access control relies on software checks to ensure that a user can access a piece of data only if he is authorized to do so. This situation is not particularly appealing from a security standpoint. In the event of server compromise, for example, as a result of a software vulnerability exploit, the potential for information theft is immense. Furthermore, there is always a danger of insider attacks wherein a person having access to the server steals and leaks the information, for example, for economic gains. Some techniques see, e.g., 2 create user hierarchies and require the users to share a common secret key if they are in a common set in the hierarchy. The data is then classified according to the hierarchy and encrypted under the public key of the set it is meant for. Clearly, such methods have several limitations. If a third party must access the data for a set, a user of that set either needs to act as an intermediary and decrypt all relevant entries for the party or must give the party its private decryption key, and thus let it have access to all entries. In many cases, by using the user hierarchies it is not even possible to realize an access control equivalent to monotone access trees.
In this paper, we introduce new techniques to implement fine grained access control. In our techniques, the data is stored on the server in an encrypted form while different users are still allowed to decrypt different pieces of data per the security policy. This effectively eliminates the need to rely on the storage server for preventing unauthorized data access.
SecretSharing Schemes. Secretsharing schemes SSS are used to divide a secret among a number of parties. The information given to a party is called the share of the secret for that party. Every SSS realizes some access structure that defines the sets of parties who should be able to reconstruct the secret by using their shares.
3
Shamir 35 and Blakley 7 were the first to propose a construction for secretsharing schemes where the access structure is a threshold gate. That is, if any t or more parties come together, they can reconstruct the secret by using their shares; however, any lesser number of parties do not get any information about the secret. Benaloh 6 extended Shamirs idea to realize any access structure that can be represented as a tree consisting of threshold gates. Other notable secretsharing schemes are 25, 15.
In SSS, one can specify a treeaccess structure where the interior nodes consist of AND and OR gates and the leaves consist of different parties. Any set of parties that satisfy the tree can come together and reconstruct the secret. Therefore in SSS, collusion among different users or parties is not only allowed but required.
In our construction each users key is associated with a treeaccess structure where the leaves are associated with attributes. A user is able to decrypt a ciphertext if the attributes associated with a ciphertext satisfy the keys access structure. In our scheme, contrary to SSS, users should be unable to collude in any meaningful way.
IdentityBased Encryption and Extensions. The concept of AttributeBased Encryp tion was introduced by Sahai and Waters 34, who also presented a particular scheme that they called Fuzzy IdentityBased Encryption FIBE. The FuzzyIBE scheme builds upon several ideas from IdentityBased Encryption 10, 36, 18. In FIBE, an identity is viewed as a set of attributes. FIBE allows for a private key for an identity, , to decrypt to a ciphertext encrypted with an identity, , if and only if the identitiesandare close to each other as measured by the set overlap distance metric. In other words, if the message is encrypted with a set of attributes , a private key for a set of attributesenables decrypting that message, if and only if d, where d is fixed during the setup time. Thus, FIBE achieves error tolerance making it suitable for use with biomet ric identities. However, it has limited applicability to access control of data, our primary motivation for this work. Since the main goal in FIBE is error tolerance, the only access structure supported is a threshold gate whose threshold is fixed at the setup time.
We develop a much richer type of attributebased encryption. The private keys of different users might be associated with different access structures. Our constructions support a wide variety of access structures indeed, in its most general form, every LSSS realizable access structure, including a tree of threshold gates.
Yao et. al. 19 show how an IBE system that encrypts to multiple hierarchical identities in a collusionresistant manner implies a forward secure Hierarchical IBE scheme. They also note how their techniques for resisting collusion attacks are useful in attributebased encryption. However, the cost of their scheme in terms of computation, private key size, and ciphertext size increases exponentially with the number of attributes. We also note that there has been other work that applied IBE techniques to access control, but did not address our central concern of resisting attacks from colluding users 37, 14.
3 Background
We first give formal definitions for the security of KeyPolicy Attribute Based Encryp tion KPABE. Then we give background information on bilinear maps and our crypto graphic assumption. Finally, we give some background on linear secretsharing schemes
4
and monotone span programs.
3.1 Definitions
Definition 1 Access Structure 4 Let P1,P2,,Pn be a set of parties. A collec tion A2P1,P2,,Pn is monotone if B,C : if BA and BC then CA. An access structure respectively, monotone access structure is a collection respectively, monotone collection A of nonempty subsets of P1, P2, . . . , Pn, i.e., A2P1,P2,,Pn. The sets in A are called the authorized sets, and the sets not in A are called the unauthorized sets.
In our context, the role of the parties is taken by the attributes. Thus, the access structure A will contain the authorized sets of attributes. We restrict our attention to monotone access structures. However, it is also possible to inefficiently realize general access structures using our techniques by having the not of an attribute as a separate at tribute altogether. Thus, the number of attributes in the system will be doubled. From now on, unless stated otherwise, by an access structure we mean a monotone access structure.
An KeyPolicy Attribute Based Encryption scheme consists of four algorithms.
Setup This is a randomized algorithm that takes no input other than the implicit security parameter. It outputs the public parameters PK and a master key MK.
Encryption This is a randomized algorithm that takes as input a message m, a set of attributes , and the public parameters PK. It outputs the ciphertext E.
Key Generation This is a randomized algorithm that takes as inputan access structure A, the master key MK and the public parameters PK. It outputs a decryption key D.
Decryption This algorithm takes as inputthe ciphertext E that was encrypted under the setof attributes, the decryption key D for access control structure A and the public parameters PK. It outputs the message M if A.
We now discuss the security of an ABE scheme. We define a selectiveset model for proving the security of the attribute based under chosen plaintext attack. This model can be seen as analogous to the selectiveID model 16, 17, 8 used in identitybased encryption IBE schemes 36, 10, 18.
SelectiveSet Model for ABE
Init The adversary declares the set of attributes, , that he wishes to be challenged upon. Setup The challenger runs the Setup algorithm of ABE and gives the public parameters to the adversary.
Phase 1 The adversary is allowed to issue queries for private keys for many access structures Aj, where Aj for all j.
Challenge The adversary submits two equal length messages M0 and M1. The challenger flips a random coin b, and encrypts Mb with . The ciphertext is passed to the adversary.
5
Phase 2 Phase 1 is repeated.
Guess The adversary outputs a guess b of b.
The advantage of an adversary A in this game is defined as Prbb1 . 2
We note that the model can easily be extended to handle chosenciphertext attacks by allowing for decryption queries in Phase 1 and Phase 2.
Definition 2 An attributebased encryption scheme is secure in the SelectiveSet model of security if all polynomial time adversaries have at most a negligible advantage in the SelectiveSet game.
3.2 Bilinear Maps
We present a few facts related to groups with efficiently computable bilinear maps.
Let G1 and G2 be two multiplicative cyclic groups of prime order p. Let g be a generator of G1 and e be a bilinear map, e : G1 G1G2. The bilinear map e has the following
properties:
1. Bilinearity: for all u, vG1 and a, bZp, we have eua, vbeu, vab.
2. Nondegeneracy: eg, g1.
We say that G1 is a bilinear group if the group operation in G1 and the bilinear map e : G1G1G2 are both efficiently computable. Notice that the map e is symmetric since ega, gbeg, gabegb, ga.
3.3 The Decisional Bilinear DiffieHellman BDH Assumption
Let a, b, c, zZp be chosen at random and g be a generator of G1. The decisional BDH assumption 8, 34 is that no probabilistic polynomialtime algorithm B can distinguish the tuple Aga,Bgb,Cgc,eg,gabc from the tuple Aga,Bgb,Cgc,eg,gz with more than a negligible advantage. The advantage of B is
abc z PrBA,B,C,eg,g 0PrBA,B,C,eg,g 0
where the probability is taken over the random choice of the generator g, the random choice of a, b, c, z in Zp, and the random bits consumed by B.
3.4 LSSS and Monotone Span Programs
In a linear secretsharing scheme 4, realizing an access structure A, a third party called the dealer holds a secret y and distributes the shares of y to parties such that y can be reconstructed by a linear combination of the shares of any authorized set. Further, an unauthorized set has no information about the secret y.
There is a close relation between LSSS and a linear algebraic model of computation called monotone span programs MSP 27. It has been shown that the existence of an efficient LSSS for some access structure is equivalent to the existence of a small monotone span program for the characteristic function of that access structure 27, 4. The following definition of MSP is a slightly altered version of the one presented in 4.
6
Definition 3 Monotone Span Program Let K be a field and x1,,xn be a set of variables. A monotone span program over K is labeled matrix MM, where M is a matrix over K, andis a labeling of the rows of M by literals from x1, . . . , xn every row is labeled by one literal.
A monotone span program accepts or rejects an input by the following criterion. For every input setof literals, define the submatrix M of M consisting of those rows whose labels are in , i.e., rows labeled by some xi such that xi. The monotone span program M acceptsif and only if 1spanM, i.e., some linear combination of the rows of M gives the allone vector 1. The MSP M computes a Boolean function fM if it accepts exactly those inputswhere fM1. The size of M is the number of rows in M.
Again, since the role of parties will be assumed by attributes in our context, each row of the matrix M will be labeled by an attribute.
4 Construction for Access Trees
In the accesstree construction, ciphertexts are labeled with a set of descriptive attributes. Private keys are identified by a treeaccess structure in which each interior node of the tree is a threshold gate and the leaves are associated with attributes. We note that this setting is very expressive. For example, we can represent a tree with AND and OR gates by using respectively 2 of 2 and 1 of 2 threshold gates. A user will be able to decrypt a ciphertext with a given key if and only if there is an assignment of attributes from the ciphertexts to nodes of the tree such that the tree is satisfied.
4.1 Access Trees
Access tree T . Let T be a tree representing an access structure. Each nonleaf node of the tree represents a threshold gate, described by its children and a threshold value. If numx is the number of children of a node x and kx is its threshold value, then 0kxnumx. When kx1, the threshold gate is an OR gate and when kxnumx, it is an AND gate. Each leaf node x of the tree is described by an attribute and a threshold value kx1.
To facilitate working with the access trees, we define a few functions. We denote the parent of the node x in the tree by parentx. The function attx is defined only if x is a leaf node and denotes the attribute associated with the leaf node x in the tree. The access tree T also defines an ordering between the children of every node, that is, the children of a node are numbered from 1 to num. The function indexx returns such a number associated with the node x. Where the index values are uniquely assigned to nodes in the access structure for a given key in an arbitrary manner.
Satisfying an access tree. Let T be an access tree with root r. Denote by Tx the subtree of T rooted at the node x. Hence T is the same as Tr. If a set of attributessatisfies the access tree Tx, we denote it as Tx1. We compute Tx recursively as follows. If x is a nonleaf node, evaluate Txfor all children x of node x. Tx returns 1 if and only if at least kx children return 1. If x is a leaf node, then Tx returns 1 if and only if attx.
7
4.2 Our Construction
Let G1 be a bilinear group of prime order p, and let g be a generator of G1. In addition, let e : G1G1G2 denote the bilinear map. A security parameter, , will determine the size of the groups. We also define the Lagrange coefficient i,S for iZp and a set, S, of elements in Zp: i,Sx xj . We will associate each attribute with a unique element in Zp. jS,ji ij
Our construction follows.
Setup Define the universe of attributes U1, 2, . . . , n. Now, for each attribute iU , choose a number ti uniformly at random from Zp. Finally, choose y uniformly at random in Zp. The published public parameters PK are
secret value to the user:
qx 0
Dx g ti whereiattx.
T1gt1,,TUgtU,Yeg,gy . t1,,tU,y .
The master key MK is:
Encryption M,,PK To encrypt a message MG2 under a set of attributes ,
choose a random value sZp and publish the ciphertext as: E,E MYs,EiTisi.
Key Generation T , MK The algorithm outputs a key that enables the user to decrypt a message encrypted under a set of attributesif and only if T 1. The algorithm proceeds as follows. First choose a polynomial qx for each node x including the leaves in the tree T . These polynomials are chosen in the following way in a topdown manner, starting from the root node r.
For each node x in the tree, set the degree dx of the polynomial qx to be one less than the threshold value kx of that node, that is, dxkx1. Now, for the root node r, set qr0y and dr other points of the polynomial qr randomly to define it completely. For any other node x, set qx0qparentxindexx and choose dx other points randomly to completely define qx.
Once the polynomials have been decided, for each leaf node x, we give the following
The set of above secret values is the decryption key D.
Decryption E, D We specify our decryption procedure as a recursive algorithm . For ease of exposition we present the simplest form of the decryption algorithm and discuss potential performance improvements in the next subsection.
We first define a recursive algorithm DecryptNodeE,D,x that takes as input the ciphertext E, E, Eii , the private key D we assume the access tree T is embedded in the private key, and a node x in the tree. It outputs a group element of G2 or .
Let iattx. If the node x is a leaf node then:
otherwise 8
DecryptNodeE, D, x
qx 0 eDx,Eieg ti
,gstieg,gsqx0 if i
We now consider the recursive case when x is a nonleaf node. The algorithm DecryptNodeE, D, x then proceeds as follows: For all nodes z that are children of x, it calls DecryptNodeE, D, z
and stores the output as Fz. Let Sx be an arbitrary kxsized set of child nodes z such that
Fz. If no such set exists then the node was not satisfied and the function returns .
Otherwise, we compute:
Fx
Fi,Sx 0, whereiindexz
z Sxindexz:zSx
zSx eg,gsqz0i,Sx 0
zSx
eg, gsqparentzindexzi,Sx 0
zSx
eg,gsqxii,Sx 0
by construction
zSx
eg, gsqx0 using polynomial interpolation
and return the result.
Now that we have defined our function DecryptNode, the decryption algorithm sim
ply calls the function on the root of the tree. We observe that DecryptNodeE,D,reg,gys Ys ifandonlyiftheciphertextsatisfiesthetree. Since,E MYs thedecryp tion algorithm simply divides out Y s and recovers the message M .
4.3 Efficiency
We now consider the efficiency of the scheme in terms of ciphertext size, private key size, and computation time for decryption and encryption.
The ciphertext overhead will be approximately one group element in G1 for every ele ment in . That is the number of group elements will be equal to the number of descriptive attributes in the ciphertext. Similarly, the encryption algorithm will need to perform one exponentiation for each attribute in .
The public parameters in the system will be of size linear in the number of attributes defined in the system. We will later discuss systems where the set of legal attributes is not dependent upon the public parameters and we give a so called LargeUniverse construction in Section 5. Users private keys will consist of a group element for every leaf in the keys corresponding access tree.
The decryption procedure is by far the hardest to define performance for. In our rudi mentary decryption algorithm the number of pairings to decrypt might always be as large as the number of nodes in the tree. However, this method is extremely suboptimal and we now discuss methods to improve upon it.
One important idea is for the decryption algorithm to do some type of exploration of the access tree relative to the ciphertext attributes before it makes cryptographic computations. At the very least the algorithm should first discover which nodes are not satisfied and not bother performing cryptographic operations on them.
The following observation shows how to modify our decryption method to optimize the efficiency. First we find out which leaf nodes we should use in order to minimize the number
9
of pairing computations as follows. For each node x, define a set Sx. If x is a leaf node,
then Sxx. Otherwise, let k be the threshold value of x. From among the child nodes
of x, choose k nodes x1,x2,,xk such that Sxi for i1,2,,k are first k sets of the
smallest size. Then for nonleaf node x, Sxx : xSxi,i1,2,,k. The set
Sr corresponding to the root node r denotes the set of leaf nodes that should be used in
order to minimize the number of pairing computations. Next, we notice that in the given
decryption algorithm, Lagrange coefficients i,Sxfrom various levels get multiplied in the
exponent in a certain way in Zp. Thus, instead of exponentiating at each level, for each
leaf node xSr, we can keep track of which Lagrange coefficients get multiplied with each
other. Using this we can compute the final exponent fx for each leaf node xSr by doing
multiplication in Zp. Now Fr is simplyeDx, Eattxfx . This reduces the number of xSr
pairing computations and exponentiations to Sr. Thus, decryption is dominated by Sr pairing computations.
The number of group elements that compose a users private key grows linearly with the number of leaf nodes in the access tree. The number of group elements in a ciphertext grows linearly with the size of the set we are encrypting under. Finally, the number of group elements in the public parameters grows linearly with the number of attributes in the defined universe. Later, we provide a construction for large universes where all elements in Zp can be used as attributes, yet the size of public parameters only grows linearly in a parameter n that we set to be the maximum possible size of .
4.4 Proof of Security
We prove that the security of our scheme in the attributebased SelectiveSet model reduces to the hardness of the Decisional BDH assumption.
Theorem 1 If an adversary can break our scheme in the Attributebased SelectiveSet model, then a simulator can be constructed to play the Decisional BDH game with a non negligible advantage.
Proof: Suppose there exists a polynomialtime adversary A, that can attack our scheme in the SelectiveSet model with advantage . We build a simulator B that can play the Decisional BDH game with advantage 2. The simulation proceeds as follows:
We first let the challenger set the groups G1 and G2 with an efficient bilinear map, e and generator g. The challenger flips a fair binary coin , outside of Bs view. If 0, the challenger sets A,B,C,Zga,gb,gc,eg,gabc; otherwise it sets A,B,C,Zga,gb,gc,eg,gz for random a,b,c,z. We assume the universe, U is defined.
Init The simulator B runs A. A chooses the set of attributesit wishes to be challenged upon.
Setup The simulator sets the parameter YeA,Beg,gab. For all iU, it sets Ti as follows: if i, it chooses a random riZp and sets Tigri thus, tiri; otherwise it chooses a random iZp and sets TigbiBi thus, tibi. It then gives the public parameters to A.
10
Phase 1 A adaptively makes requests for the keys corresponding to any access structures T such that the challenge setdoes not satisfy T . Suppose A makes a request for the secret key for an access structure T where T 0. To generate the secret key, B needs to assign a polynomial Qx of degree dx for every node in the access tree T .
We first define the following two procedures: PolySat and PolyUnsat.
PolySatTx,,x This procedure sets up the polynomials for the nodes of an access sub tree with satisfied root node, that is, Tx1. The procedure takes an access tree Tx with root node x as input along with a set of attributesand an integer xZp.
It first sets up a polynomial qx of degree dx for the root node x. It sets qx0x and then sets rest of the points randomly to completely fix qx. Now it sets polynomials for each child node x of x by calling the procedure PolySatTx , , qxindexx. Notice that in this way, qx 0qxindexx for each child node x of x.
PolyUnsatTx,,gx This procedure sets up the polynomials for the nodes of an access tree with unsatisfied root node, that is, Tx0. The procedure takes an access tree Tx with root node x as input along with a set of attributesand an element gxG1 where xZp.
It first defines a polynomial qx of degree dx for the root node x such that qx0x. Because Tx0, no more than dx children of x are satisfied. Let hxdx be the number of satisfied children of x. For each satisfied child x of x, the procedure chooses a random point xZp and sets qxindexxx. It then fixes the remaining dxhx points of qx randomly to completely define qx. Now the algorithm recursively defines polynomials for the rest of the nodes in the tree as follows. For each child node x of x, the algorithm calls:
PolySatTx , , qxindexx, if x is a satisfied node. Notice that qxindexx is known in this case.
PolyUnsatTx , , gqxindexx, if x is not a satisfied node. Notice that only gqxindexx can be obtained by interpolation as only gqx0 is known in this case.
Notice that in this case also, qx 0qxindexx for each child node x of x.
To give keys for access structure T , simulator first runs PolyUnsatT , , A to define a polynomial qx for each node x of T . Notice that for each leaf node x of T , we know qx completely if x is satisfied; if x is not satisfied, then at least gqx0 is known in some cases qx might be known completely. Furthermore, qr0a.
Simulator now defines the final polynomial Qxbqx for each node x of T . Notice that this sets yQr0ab. The key corresponding to each leaf node is given using its polynomial as follows. Let iattx.
Qx0 g ti
bqx0 g ri
bqx0 g bi
qx0
B ri ifattx
qx0
g i otherwise
Dx Qx0 g ti
Therefore, the simulator is able to construct a private key for the access structure T . Furthermore, the distribution of the private key for T is identical to that in the original
11
scheme.
Challenge The adversary A, will submit two challenge messages m0 and m1 to the simulator. The simulator flips a fair binary coin , and returns an encryption of m. The ciphertext is output as:
E,EmZ,EiCrii
If 0 then Zeg,gabc. If we let sc, then we have Yseg,gabceg,gabc, and EigricCri. Therefore, the ciphertext is a valid random encryption of message m.
Otherwise, if 1, then Zeg,gz. We then have Emeg,gz. Since z is random, E will be a random element of G2 from the adversaries view and the message contains no information about m.
Phase 2 The simulator acts exactly as it did in Phase 1.
Guess A will submit a guessof . Ifthe simulator will output 0 to indicate that it was given a valid BDHtuple otherwise it will output 1 to indicate it was given a random 4tuple.
As shown in the construction the simulators generation of public parameters and private keys is identical to that of the actual scheme.
In the case where 1 the adversary gains no information about . Therefore, we
have Pr11. Since the simulator guesses 1 when , we have
Pr 1 1. 2 2
If 0 then the adversary sees an encryption of m. The adversarys advantage in
this situation isby definition. Therefore, we have Pr01. Since the
simulatorguesses0when,wehavePr01. 2 21
The overall advantage of the simulator in the Decisional BDH game is 2 Pr01 Pr11111 111 .
2 2222222
ChosenCiphertext Security. Our security definitions and proofs have been in the chosenplaintext model. Similar to 34, we notice that our construction can be extended to the chosenciphertext model by applying the technique of using simulationsound NIZK proofs to achieve chosenciphertext security 33. However, in Section 9 we describe how our delegation mechanism can be used with the techniques of Cannetti, Halevi, and Katz 17 to achieve a much more efficient CCA2 system.
5 Large Universe Construction
In our previous constructions, the size of public parameters grows linearly with the number of possible attributes in the universe. Combining the tricks presented in section 4 with those in the large universe construction of Sahai and Waters 34, we construct another scheme that uses all elements of Zp as attributes, yet the public parameters grow only linearly in
12
a parameter n which we fix as the maximum size of the set we can encrypt under.3
This construction not only reduces the size of the public parameters but also allows us to apply a collision resistant hash function H : 0, 1Zp and use arbitrary strings, that were not necessarily considered during public key setup, as attributes. For example we can
add any verifiable attribute, such as Lives in Beverly Hills, to a users private key.
5.1 Description
Let G1 be a bilinear group of prime order p, and let g be a generator of G1. Additionally, let e : G1G1G2 denote the bilinear map. A security parameter, , will determine the size of the groups. Also define the Lagrange coefficient i,S for iZp and a set, S, of elements in Zp, exactly as before. The data will be encrypted under a setof n elements4 of Zp. Our construction follows.
Setup n Choose a random value yZp and let g1gy. Now choose a random element g2 of G1.
Next, choose t1,,tn1 uniformly at random from G1. Let N be the set 1,2,,n 1. Define a function T, as:
n1 TXgXn ti,NX.
2i i1
Function T can be viewed as the function gXnghX for some n degree polynomial h. The 2
public parameters PK are: g1, g2, t1, . . . , tn1 and the master key MK is: y.
Encryption m, , PK To encrypt a message mG2 under a set of attributes , choose
a random value sZp and publish the ciphertext as:
E,Emeg1,g2s,Egs,EiTisi.
Key Generation T , MK, PK The algorithm outputs a key which enables the user to decrypt a message encrypted under a set of attributes , if and only if T 1. The algorithm proceeds as follows. First choose a polynomial qx for each nonleaf node x in the tree T . These polynomials are chosen in the following way in a top down manner, starting from the root node r.
For each node x in the tree, set the degree dx of the polynomial qx to be one less than the threshold value kx of that node, that is, dxkx1. Now for the root node r, set qr0y and dr other points of the polynomial qr randomly to define it completely. For any other node x, set qx0qparentxindexx and choose dx other points randomly to completely define qx.
3If we are willing to accept random oracles 5, it is possible to overcome the sizelimitation onby replacing the function TX in our construction see Setup by a hash function see 31 for details. This also improves the efficiency of the system.
4With some minor modifications, which we omit for simplicity, we can encrypt to all sets of sizen.
13
Once the polynomials have been decided, for each leaf node x, we give the following secret values to the user:
Dxgqx0Tirx where iattx 2
Rxgrx
where rx is chosen uniformly at random from Zp for each node x. The set of above secret
pairs is the decryption key D.
Decryption E,D As for the case of small universe, we first define a recursive algorithm DecryptNodeE,D,x that takes as input the ciphertext E,E,E,Eii, the private key D we assume the access tree T is embedded in the private key, and a node x in the tree. It outputs a group element of G2 oras follows.
Let iattx. If the node x is a leaf node then:
eD ,E
egqx0Tirx,gs
2 rx s
egqx0,gseTirx,gs
x
2
rx s eg,g2sqx0 if i ,Ti
DecryptNodeE,D,xeRx,Ei eg ,Ti otherwise
eg
We now consider the recursive case when x is a nonleaf node. The algorithm DecryptNodeE, D, x then proceeds as follows: For all nodes z that are children of x, it calls DecryptNodeE, D, z
and stores the output as Fz. Let Sx be an arbitrary kxsized set of child nodes z such that
Fz. If no such set exists then the node was not satisfied and the function returns .
Otherwise, we compute:
Fx
Fi,Sx 0, whereiindexz
z Sxindexz:zSx
zSx eg,g2sqz0i,Sx 0
zSx
eg, g2sqparentzindexzi,Sx 0
zSx
eg,g2sqx0i,Sx 0
by construction
zSx
eg, g2sqx0 using polynomial interpolation
and return the result.
Now that we have defined our function DecryptNode, the decryption algorithm sim
ply calls the function on the root of the tree. We observe that DecryptNodeE,D,reg, g2yseg1, g2s if and only if the ciphertext satisfies the tree. Since, Emeg1, g2s the decryption algorithm simply divides out eg1,g2s and recovers the message m.
The security proof of this construction follows largely from the security proof in sec tion 4.4. Details are given in appendix B.
It is possible to extend the above construction to realize any LSSS realizable access structure using techniques similar to those in appendix A. A brief outline of the the construction follows.
14
Algorithms Setup and Encryption remain exactly the same as for the above construction. Key Generation takes an MSP and the master key as input. For each row i of the matrix,
it gives the following pair to the user: DigMiuTiri,Rigri; where u is chosen 2
such that 1uy master key, and ri is chosen randomly. Decryption and the security proof follow using the tricks of appendix A.
6 Delegation of Private Keys
In our large universe construction, individual users can generate new private keys using their private keys, which can then be delegated to other users. A user which has a private key corresponding to an access tree T can compute a new private key corresponding to ANY access tree Twhich is more restrictive than T i.e., T T . Thus, the users are capable to acting as a local key authority which can generate and distribute private keys to other users.
Computation of a new private key from an existing private key is done by applying a set of basic operations on the existing key. These operations are aimed at step by step conversion of the given private key for an access tree T to a private key for the targeted access tree Tgiven that T T . In the following, a t, ngate denotes a gate with threshold t and number of children n. The operations are as follows.
1 Adding a new trivial gate to T
This operation involves adding a new node y above an existing node x. The new node y
represents a 1, 1 threshold gate which after adding becomes the parent of x. The former parent of x if x is not the root node, say z, becomes the parent of y.
Since the threshold of y is 1, we are required to associate a 0 degree polynomial qy with it such that qx0qyindexx and qy0qzindexy. The second condition essentially fixes qy and the first one is automatically satisfied since z was the parent of x earlier. Hence, no changes to the private key are required for this operation.
2 Manipulating an existing t, ngate in T
This operation involves manipulating a threshold gate so as to make the access structure
more restrictive. The operation could be of the following three types.
2.1 Converting a t, ngate to a t1, ngate with t1n
Consider a node x representing a t, ngate. Clearly, the polynomial qx has the degree
t1 which has to be increased to t. Define a new polynomial qx as follows. qx XX1qxX
Now, we change the key such that qx becomes the new polynomial of the node x. This is done as follows. For every child y of x, compute the constant Cxindexy1. For every leaf node z in the subtree5 Ty, compute the new decryption key as
Dz DzCx,Rz RzCx 5Recall that Ty denotes the subtree defined by y as its root.
15
The above results in the multiplication of all the polynomials in the subtree Ty with the constant Cx. Hence, qy 0indexy1qy0 which is indeed a point on the new polynomial qx . Note that since qx 0qx0, no changes outside the subtree Tx are required.
The above procedure effectively changes x from a t, ngate to a t1, ngate and yields the corresponding new private key.
2.2 Converting a t, ngate to a t1, n1gate
This procedure involves adding a new subtree with root say z as a child of a node x
while increasing the degree of x by 1 at the same time. Let z be the vth child of x so that indexzv. We shall change the polynomial qx to the following.
qx XaX1qxX where a1 v
As in the previous operation, for every existing child y of x, the polynomials in the subtree Ty are multiplied with the appropriate constant Cxa.indexy1. This ensures that qy 0 is indeed a point on qx . Further, set qz00qx v. Given qz0, keys can be created for the subtree Tz as in the original key generation algorithm. Hence, the keys of the subtrees of all the children old as well as new of the node x have been made consistent with the new polynomial qx , thus achieving our goal.
2.3 Converting a t, ngate to a t, n1gate with tn1
This operation involves deleting a child y of a node x. This can be easily achieved just
by deleting decryption keys corresponding to all the leaves of Ty from the original decryp tion key.
3 Rerandomizing the obtained key
Once we obtain a key for the desired access structure by applying a set of operations of type 1 and 2, we apply a final rerandomization step to make it independent of the original key from which it was computed. Rerandomization of a node x with a known constant Cx is done as follows. Choose a random polynomial px of degree6 dx such that px0Cx. Define the new polynomial qx as qx XqxXpxX. We have to change the key such that qx becomes the new polynomial of node x. This is done by recursively rerandomizing every child y of x with the constant Cypxindexy. If y is a leaf node, the new decryption key corresponding to y is computed as follows.
Dy Dy.g2Cy.Tiry, Ry Ry.gry
Where iatty and ry is chosen randomly.
Now, rerandomization of the private key is done just by rerandomizing the root node r with the constant Cr0. The key obtained is the final key ready to be distributed to other users.
6Recall that dx is the degree of the polynomial qx associated with the node x
16
In the following theorem, we prove that the above set of operations is complete. That is, give a key for an access tree T , this set of operations is sufficient to compute a key for ANY access tree Twhich is more restrictive than T .
Theorem 2 Completeness Theorem The given set of operations is complete.
Proof: We can obtain a key for an access tree Tfrom a key for T using the following general technique. Add a new trivial gate x using operation 1 above the root node of T so that the new gate becomes the root node. Now we apply operation 2.2 to x to convert it from a 1, 1gate to a 2, 2gate. The new subtree added as a child of x corresponds to the access tree T . Finally, we rerandomize the key obtained operation 3. This gives us a key for the access structure T AND T . However, since Tis more restrictive than T , this access structure is equivalent to Titself. Hence, we have obtained a key for the access structure T . We point out that this is a general method for obtaining a more restrictive access structure; in practice users will likely use the delegation tools described above in a more refined manner to achieve shorter private key sizes and faster decryption times.
In the above setting, we may imagine an entity having multiple private keys procured from different entities. We note that it is possible to use these multiple keys for different access structures to compute a key for the targeted access structure. Given n keys for the access trees T1, T2, ,Tn, using an operation similar to operation 1, we can connect them to obtain a single tree with an OR gate being the root node and T1, T2, ,Tn each being a child subtree of that OR gate. Thus, we obtain a single key for the access structure TT1 OR T2 OR OR Tn. This key can then be used to generate new private keys.
7 Audit Log Application
An important application of KPABE deals with secure forensic analysis: One of the most important needs for electronic forensic analysis is an audit log containing a detailed ac count of all activity on the system or network to be protected. Such audit logs, however, raise significant security concerns: a comprehensive audit log would become a prized target for enemy capture. Merely encrypting the audit log is not sufficient, since then any party who needs to legitimately access the audit log contents for instance a forensic analyst would require the secret keythereby giving this single analyst access to essentially all secret information on the network. Such problematic security issues arise in nearly every secure system, and particularly in largescale networked systems such as the Global Infor mation Grid, where diverse secret, top secret, and highly classified information will need to appear intermingled in distributed audit logs.
Our KPABE system provides an attractive solution to the audit log problem. Audit log entries could be annotated with attributes such as, for instance, 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. Then, a forensic analyst charged with some investigation would be issued a secret key associated with a particular access structurewhich would correspond to the key allowing for a particular kind of encrypted search; such a key, for example, would only open audit log records whose attributes satisfied the condition that the user name is Bob,
17
OR the date is between October 4, 2005 and October 7, 2005 AND the data accessed pertained to naval operations off the coast of North Korea. Our system would provide the guarantee that even if multiple rogue analysts collude to try to extract unauthorized information from the audit log, they will fail.
A more concrete example auditlog application of our ABE system would be to the ArmyCERT program, which uses netflow logs 30. Basically, an entry is created for every flow e.g. TCP connection, indexed by seven attributes: source IP address, destination IP address, L3 protocol type, source port, destination port, ToS byte DSCP, and input logical interface ifIndex. These aspects of every flow are in the clear, and the payload can be encrypted using our ABE system with these fields as attributes.
Note that in our scheme, we would need to assume that the attributes associated with audit log entries would be available to all analysts.7 This may present a problem in highly secret environments where even attributes themselves would need to be kept hidden from analysts. We leave the problem of constructing KPABE systems where attributes associ ated with ciphertexts remain secret as an important open problem.
8 Application to Broadcast Encryption: Targeted Broadcast
We describe a new broadcast scenario that we call targeted broadcast. Consider the following setting.
A broadcaster broadcasts a sequence of different items, each one labeled with a set of attributes describing the item. For instance, a television broadcaster might broadcast an episode of the show 24, and label this item with attributes such as the name of the program 24, the genre drama, the season, the episode number, the year, month, and date of original broadcast, the current year, month, and date, the name of the director, and the name of the producing company.
Each user is subscribed to a different package. The user package describes an access policy, which along with the set of attributes describing any particular item being broadcast, determine whether or not the user should be able to access the item. For example, a television user may want to subscribe to a package that allows him view episodes of 24 from either the current season or Season 3. This could be encoded as policy as 24 AND Season:5 OR Season:3.
The essential idea of Targeted Broadcast is to enjoy the economiesofscale offered by a broadcast channel, while still being able to deliver programming targeted at the needs or wishes of individual users. The growing acceptability of such a model can be seen by the rising popularity of DVR systems such as TiVo, which allow users to easily record only the programming they want in order to watch it later. In the case of television, taking the approach that we envision here would allow for much more flexibility than just allowing users to select what channels they like.
Our KPABE system naturally offers a targeted broadcast system. A new symmetric key would be chosen and used to encrypt each item being broadcast, and then the KPABE
7We observe that this does not mean that the attributes need be public. Our KPABE systems ciphertexts could be reencrypted, with a key that corresponds to the general clearance level of all analysts.
18
system would be used to encrypt the symmetric key with the attributes associated with the item being broadcast. The KPABE system would precisely allow the flexibility we envision in issuing private keys for the unique needs of each user.
It is worth mentioning that handling such a situation with the best known broadcast encryption schemes 11, 22 which allow encrypting to an arbitrary subset of users is quite inefficient in comparison. The efficiency of such systems is dependent on the size of the authorized user set or the number of users in the system 11, 22, and would also require the broadcaster to refer to its database of user authorizations each time a different item is to be encrypted for broadcast. In our scheme, the encryption of an item would depend only on the properties of that item. The broadcaster could in principle even forget about the levels of access granted to each user after preparing a private key for the user.
9 Discussion and Extensions
We discuss various extensions to our scheme and open problems.
Achieving CCASecurity and HIBE from Delegation We briefly outline how we can achieve efficient CCA2 security and realize the Hierarchical IdentityBased Encryption by applying delegation techniques to the large universe construction.
To achieve CCA2 security an encyrptor will chooses a setof attributes to encrypt the message under and then generate a publicprivate key pair for a one time signature scheme. We let VK denote the bitstring represenation of the public key and letbe the set VK. The encryptor encrypts the ciphertext under the attributesand then signs the ciphertext with the private key and attaches the signature and the public key description. Suppose a user has a key for access structure X wishes to decrypt. The user first checks that the ciphertext is signed under VK and rejects the ciphertext otherwise. Then it creates an new key for the access structure of X AND CCA : VK. By similar arguments to those in Canetti, Halevi, and Katz 17 this gives chosenciphertex security. We can also use other methods 12, 13 to achieve greater efficiency.
We can realize a HIBE by simply managing the the assignment of attributes in a careful manner. For example, to encrypt to the hierarchical identity edu:ucla one can encrypt to the set of attributes1edu, 2ucla . Someone who has the toplevel key for edu will have a policy that requires the attribute 1edu to be present. To delegate a key for edu:ucla it simply creates a policy for 1eduAND 2ucla using our delegation techniques. We view the fact that a primitive HIBE follows so simply from our scheme as an attestation to the power of these techniques.
CiphertextPolicy AttributeBased Encryption. In this work, we considered the setting where ciphertexts are associated with sets of attributes, whereas user secret keys are associated with policies. As we have discussed, this setting has a number of natural applications. Another possibility is to have the reverse situation: user keys are associated with sets of attributes, whereas ciphertexts are associated with policies. We call such systems CiphertextPolicy AttributeBased Encryption CPABE systems. We note that the construction of Sahai and Waters 34 was most naturally considered in this framework.
19
CPABE systems that allow for complex policies like those considered here would have a number of applications. An important example is a kind of sophisticated Broadcast Encryption, where users are described by and therefore associated with various attributes. Then, one could create a ciphertext that can be opened only if the attributes of a user match a policy. For instance, in a military setting, one could broadcast a message that is meant to be read only by users who have a rank of Lieutenant or higher, and who were deployed in South Korea in the year 2005. We leave constructing such a system as an important open problem.
Searching on Encrypted Data. Our current constructions do not hide the set of at tributes under which the data is encrypted. However, if it were possible to hide the at tributes, then viewing attributes as keywords in such a system would lead to the first general keywordbased search on encrypted data 9. A search query could potentially be any monotone boolean formula of any number of keywords. We leave the problem of hiding the set of attributes as open.
References
1 Michel Abdalla, Dario Catalano, Alexander W. Dent, John MaloneLee, Gregory Neven, and Nigel P. Smart. Identitybased encryption gone wild. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, ICALP 2, volume 4052 of Lecture Notes in Computer Science, pages 300311. Springer, 2006.
2 S.G. Akl and P.D. Taylor. Cryptographic Solution to a Multi Level Security Problem. In Advances in CryptologyCRYPTO, 1982.
3 H. Anton and C. Rorres. Elementary Linear Algebra, 9th Edition. 2005.
4 A. Beimel. Secure Schemes for Secret Sharing and Key Distribution. PhD thesis, Israel
Institute of Technology, Technion, Haifa, Israel, 1996.
5 M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In ACM conference on Computer and Communications Security ACM CCS, pages 6273, 1993.
6 J. Benaloh and Leichter J. Generalized Secret Sharing and Monotone Functions. In Advances in CryptologyCRYPTO, volume 403 of LNCS, pages 2736. Springer, 1988.
7 G. R. Blakley. Safeguarding cryptographic keys. In National Computer Conference, pages 313317. American Federation of Information Processing Societies Proceedings, 1979.
8 D. Boneh and X. Boyen. Efficient SelectiveID Secure Identity Based Encryption Without Random Oracles. In Advances in CryptologyEurocrypt, volume 3027 of LNCS, pages 223238. Springer, 2004.
20
9 D. Boneh, G.D. Crescenzo, R. Ostrovsky, and G. Persiano. PublicKey Encryption with Keyword Search. In Advances in CryptologyEurocrypt, volume 3027 of LNCS, pages 506522. Springer, 2004.
10 D. Boneh and M. Franklin. Identity Based Encryption from the Weil Pairing. In Advances in CryptologyCRYPTO, volume 2139 of LNCS, pages 213229. Springer, 2001.
11 D. Boneh, C. Gentry, and B. Waters. Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys. In Advances in CryptologyCRYPTO, volume 3621 of LNCS, pages 258275. Springer, 2005.
12 Dan Boneh and Jonathan Katz. Improved efficiency for ccasecure cryptosystems built using identitybased encryption. In CTRSA, pages 87103, 2005.
13 Xavier Boyen, Qixiang Mei, and Brent Waters. Direct chosen ciphertext security from identitybased techniques. In ACM Conference on Computer and Communications Security, pages 320329, 2005.
14 Robert W. Bradshaw, Jason E. Holt, and Kent E. Seamons. Concealing complex poli cies with hidden credentials. In ACM Conference on Computer and Communications Security, pages 146157, 2004.
15 E. F. Brickell. Some ideal secret sharing schemes. Journal of Combinatorial Mathe matics and Combinatorial Computing, 6:105113, 1989.
16 R. Canetti, S. Halevi, and J. Katz. A ForwardSecure PublicKey Encryption Scheme. In Advances in CryptologyEurocrypt, volume 2656 of LNCS. Springer, 2003.
17 R. Canetti, S. Halevi, and J. Katz. Chosen Ciphertext Security from Identity Based Encryption. In Advances in CryptologyEurocrypt, volume 3027 of LNCS, pages 207222. Springer, 2004.
18 Clifford Cocks. An identity based encryption scheme based on quadratic residues. In IMA Int. Conf., pages 360363, 2001.
19 Y. Dodis, N. Fazio, A. Lysyanskaya, and D.F. Yao. IDBased Encryption for Complex Hierarchies with Applications to Forward Security and Broadcast Encryption. In ACM conference on Computer and Communications Security ACM CCS, pages 354363, 2004.
20 Rita Gavriloaie, Wolfgang Nejdl, Daniel Olmedilla, Kent E. Seamons, and Marianne Winslett. No registration needed: How to use declarative policies and negotiation to access sensitive resources on the semantic web. In ESWS, pages 342356, 2004.
21 Craig Gentry and Alice Silverberg. Hierarchical idbased cryptography. In ASI ACRYPT, pages 548566, 2002.
22 D. Halevy and A. Shamir. The LSD Broadcast Encryption Scheme. In Advances in CryptologyCRYPTO, volume 2442 of LNCS, pages 4760. Springer, 2002.
21
23 Hugh Harney, Andrea Colgrove, and Patrick Drew McDaniel. Principles of policy in secure groups. In NDSS, 2001.
24 Jeremy Horwitz and Ben Lynn. Toward hierarchical identitybased encryption. In Lars R. Knudsen, editor, EUROCRYPT, volume 2332 of Lecture Notes in Computer Science, pages 466481. Springer, 2002.
25 M. Ito, A. Saito, and T. Nishizeki. Secret Sharing Scheme Realizing General Access Structure. In IEEE Globecom. IEEE, 1987.
26 Myong H. Kang, Joon S. Park, and Judith N. Froscher. Access control mechanisms for interorganizational workflow. In SACMAT 01: Proceedings of the sixth ACM symposium on Access control models and technologies, pages 6674, New York, NY, USA, 2001. ACM Press.
27 M. Karchmer and A. Wigderson. On Span Programs. In The Eighth Annual Structure in Complexity Theory, pages 102111, 1993.
28 Jiangtao Li, Ninghui Li, and William H. Winsborough. Automated trust negotiation using cryptographic credentials. In ACM Conference on Computer and Communica tions Security, pages 4657, 2005.
29 Patrick Drew McDaniel and Atul Prakash. Methods and limitations of security policy reconciliation. In IEEE Symposium on Security and Privacy, pages 7387, 2002.
30 Cisco Networks. http:netflow.cesnet.czn netflow.php.
31 M. Pirretti, P. Traynor, P. McDaniel, and B. Waters. Secure AtrributeBased Systems. In ACM conference on Computer and Communications Security ACM CCS, 2006. To appear.
32 V.V. Prasolov. Problems and Theorems in Linear Algebra. American Mathematical Society, 1994.
33 A. Sahai. Nonmalleable noninteractive zero knowledge and adaptive chosen ciphertext security. In IEEE Symposium on Foundations of Computer Science, 1999.
34 A. Sahai and B. Waters. Fuzzy Identity Based Encryption. In Advances in CryptologyEurocrypt, volume 3494 of LNCS, pages 457473. Springer, 2005.
35 A. Shamir. How to share a secret. Commun. ACM, 2211:612613, 1979.
36 A. Shamir. Identity Based Cryptosystems and Signature Schemes. In Advances in
CryptologyCRYPTO, volume 196 of LNCS, pages 3753. Springer, 1984.
37 Nigel P. Smart. Access control using pairing based cryptography. In CTRSA, pages
111121, 2003.
38 Ting Yu and Marianne Winslett. A unified scheme for resource protection in automated
trust negotiation. In IEEE Symposium on Security and Privacy, pages 110122, 2003. 22
A Construction for Any LSSSrealizable Access Structure
Consider an access structure for which there exists a linear secretsharing scheme that realizes it. It is known that for every LSSS realizable access structure, there exists a monotone span program MSP that computes the corresponding boolean function and vice versa 4. Thus, such an access structure can be represented by a monotone span program.
In an attempt to accommodate more general and complex access structures, we present attribute based encryption for the class of access structures which can be represented by polynomial size monotone span programs. The access structure will be represented in the form of a monotone span program M M, . Each row of M will be labeled by an attribute from U and i will denote the label of ith row Mi.
A.1 Our Construction
The data will be encrypted under a set of attributes . The user should be able to decrypt the data if and only if he holds the keys for an MSP MM, such that fM1; here fM denotes the function that M computes.
Let G1 be a bilinear group of prime order p, and let g be a generator of G1. Additionally, let e : G1G1G2 denote the bilinear map. A security parameter, , will determine the size of the groups. Our construction follows:
Setup Define the universe of attributes U1, 2, . . . , n. Now, for each attribute iU , choose a number ti uniformly at random from Zp. Finally, choose y uniformly at random in Zp. The published public parameters PK are:
T1gt1,,TUgtU,Yeg,gy t1,,tU,y
The master key MK is:
Encryption m, , PK To encrypt a message mG2 under , choose a random value
sZp and publish the ciphertext as:
E,E mYs,EiTisi
Key Generation M,MK,PK Input to the key generation algorithm is an access structure in the form of an MSP M M, . Let the dimensions of M be dl. Choose a random vector u from Zlp such that 1uy, that is, uu1,u2,,ul such that
li1 uiy. For each row vector M i, give the following secret value to the user: M iu
Dig ti
The set of above secret values is the decryption key D.
23
Decryption E, D, PK To decrypt the ciphertext E, E, Eiiwith the decryp tion key D, proceed as follows. Since fM1, the span program M accepts . Thus, there exist coefficients iZp such that,
Now,
E
i
eDi, Eii
E
M iu
eg ti , gstii
iM i1 i
A.2 Proof of Security
i
mYseg,gsiMiu
i P
mY seg, gs i iMiu
mY seg, gs1u
meg, gsy eg, gsy
m.
We prove that the security of our scheme in the attributebased SelectiveSet model reduces to the hardness of the Decisional BDH assumption.
Theorem 3 If an adversary can break our scheme in the Attributebased SelectiveSet model, then a simulator can be constructed to play the Decisional BDH game with a non negligible advantage.
Proof: Suppose there exists a polynomialtime adversary A, that can attack our scheme in the SelectiveSet model with advantage . We build a simulator B that can play the Decisional BDH game with advantage 2. The simulation proceeds as follows:
We first let the challenger set the groups G1 and G2 with an efficient bilinear map, e and generator g. The challenger flips a fair binary coin , outside of Bs view. If 0, the challenger sets A,B,C,Zga,gb,gc,eg,gabc; otherwise it sets A,B,C,Zga,gb,gc,eg,gz for random a,b,c,z. We assume the universe, U, is defined.
Init The simulator B runs A. A chooses the set of attributesit wishes to be challenged upon.
Setup The simulator sets the parameter YeA,Beg,gab. For all iU, it sets Ti as follows: if i, it chooses a random ri and sets Tigri thus, tiri; otherwise it chooses a random i and sets TigbiBi thus, tibi.
It then gives the public parameters to A. Notice that from As view all parameters are chosen at random as in the construction.
24
Phase 1 A adaptively makes requests for several access structures represented in the form of MSP such thatis accepted by none of them.
Suppose A makes a request for the secret key for an MSP M M,such that fM 0. Let the dimensions of M be dl. Let M be the submatrix of M consisting of only those rows whose label is in . To generate the secret key, B has to fix a random vector uu1,u2,,ulsuchthat1uab. Todothat,firstdefineavectorvv1,v2,,vl such that vibi, for i chosen uniformly at random from Zp. Now, consider the following proposition 3, 32,
Proposition 1 A vectoris independent of a set of vectors represented by a matrix N if and only if there exists a vector w such that Nw0 while w0.
Since 1 is independent of M, there exists a vector w such that Mw0 and 1w0 h, say. Such a vector can be efficiently computed 3, 32. Let ww1, w2, . . . , wl. Finally define the vector u as follows:
uvw where abb lk1 k h
Notice that,
Let Mjxj1,xj2,,xjl. Give the secret key for the row Mj as follows. If j,
uiviwibiabb lk1 kwi h
then:
Note that 1 is completely known. This is a legitimate key because,
l xjij DjB1 where 1i1
Mj u Mj vw Mj vMj w Mj v0 li1xjii
tttt b r b1
rj
j j j If j, then:
j
l i1
j
Mju
i1
i1 xjii1 xjihihjhj
l x Dj A2g3 where2i1 ji,
x h l
k
ji i hj
Challenge The adversary A, will submit two challenge messages m0 and m1 to the simulator. The simulator flips a fair binary coin, , and returns an encryption of m. The
k1
l
k1 k
tj
the distribution of the private key for M is identical to that of the original scheme.
3
Note that,are completely known. This is a legitimate key because,
P bl xjiialk1k
h
hj
l l
23
a
Therefore, the simulator is able to construct a private key for the MSP M . Furthermore,
ciphertext is output as:
E,EmZ,EiCrii 25
bj
a23
If 0 then Zeg,gabc. If we let sc, then we have Yseg,gabceg,gabc, and EigricCri. Therefore, the ciphertext is a valid random encryption of message m.
Otherwise, if 1, then Zeg,gz. We then have Emeg,gz. Since z is random, E will be a random element of G2 from the adversarys view and the message contains no information about m.
Phase 2 The simulator acts exactly as it did in Phase 1.
Guess A will submit a guessof . Ifthe simulator will output 0 to indicate that it was given a valid BDHtuple otherwise it will output 1 to indicate it was given a random 4tuple.
As shown in the construction the simulators generation of public parameters and private keys is identical to that of the actual scheme.
In the case where 1 the adversary gains no information about . Therefore, we
have Pr11. Since the simulator guesses 1 when , we have
Pr 1 1. 2 2
If 0 then the adversary sees an encryption of m. The adversarys advantage in
this situation isby definition. Therefore, we have Pr01. Since the
simulatorguesses0when,wehavePr01. 2 21
The overall advantage of the simulator in the Decisional BDH game is 2 Pr01 Pr11111 111 .
2 2222222
B Proof of Large Universe Construction
We prove that the security of large universe construction in the attributebased SelectiveSet model reduces to the hardness of the Decisional BDH assumption.
Theorem 4 If an adversary can break our scheme in the Attributebased SelectiveSet model, then a simulator can be constructed to play the Decisional BDH game with a non negligible advantage.
Proof: Suppose there exists a polynomialtime adversary A, that can attack our scheme in the SelectiveSet model with advantage . We build a simulator B that can play the Decisional BDH game with advantage 2. The simulation proceeds as follows:
We first let the challenger set the groups G1 and G2 with an efficient bilinear map, e and generator g. The challenger flips a fair binary coin , outside of Bs view. If 0, the challenger sets A,B,C,Zga,gb,gc,eg,gabc; otherwise it sets A,B,C,Zga, gb, gc, eg, gz for random a, b, c, z.
Init The simulator B runs A. A chooses the challenge set, , an n element set of members of Zp.
Setup The simulator assigns the public parameters g1A and g2B. It then chooses a random n degree polynomial fX and calculates an n degree polynomial uX as follows:
26
set uXXn for all X and uXXn for some other X. Because, Xn and uX are two n degree polynomials, they will have at most n points in common or they are the same polynomial. This construction ensures that X,uXXn if and only if X.
Now, the simulator sets tiguigfi for all i1 to n1. Because fX is a random 2
n degree polynomial, all ti will be chosen independently at random as in the construction. Implicitly we have: Tiginuigfi.
Phase 1 A adaptively makes requests for several access structures such thatpasses through none of them. Suppose A makes a request for the secret key for an access structure T where T 0. To generate the secret key, B has to fix a polynomial Qx of degree dx for every nonleaf node in the access tree.
Recall the functions PolySat and PolyUnsat from the proof of small universe case. The simulator simply runs PolyUnsatT , , A on the main tree T . This defines a polynomial qx for each node x of T such that qr0a. Furthermore, for each leaf node x of T , we know the polynomial qx completely if x is satisfied, and at least gqx0 if x is not satisfied.
Simulator now defines the main polynomial Qxqx for each node x of T . Notice that this sets yQr0a. The key corresponding to each leaf node x is given using its polynomial as follows. Let iattx.
If i.
Rxgrx Where rx is chosen at random from Zp.
Ifi. Letg3 gQx0 gqx0. Dx
fi n ginui gi 32
3
uigfirx
2
DxgQx0Tirxgqx0Tirx 22
1
g i nuig r x
R xWhere rx is chosen at random from Zp.
The value inui will be nonzero for all i. This follows from our construction of
ux. Above key components are legitimate because if we set rrqx0
then,
x
x inui
fi n
ginui gi uigfirx
Dx
g inui g2
32
qx 0.f i in ui
qx 0
g2
qx0
g2
in ui gfiinui g2 gfirx
gqx0Tirx 2
gQx0Tirx 2
in ui g2
inui g2
gfirx qx 0
gfi x
inui
rqx0
27
and,
n1r qx0 Rxgi uigrx gx inui grx
3
Therefore, the simulator is able to construct a private key for the access structure T . Furthermore, the distribution of the private key for T is identical to that of the original scheme.
Challenge The adversary A, will submit two challenge messages m0 and m1 to the simulator. The simulator flips a fair binary coin , and returns an encryption of m. The ciphertext is output as:
E,EmZ,EC,EiCfii If 0 then Zeg, gabc. Then the ciphertext is:
E,Emeg,gabc,Egc,EigcfiTici
This is a valid ciphertext for the message m under the set .
Otherwise, if 1, then Zeg,gz. We then have Emeg,gz. Since z is
random, E will be a random element of G2 from the adversaries view and the message contains no information about m.
Phase 2 The simulator acts exactly as it did in Phase 1.
Guess A will submit a guessof . Ifthe simulator will output 0 to indicate that it was given a valid BDHtuple otherwise it will output 1 to indicate it was given a random 4tuple.
As shown in the construction the simulators generation of public parameters and private keys is identical to that of the actual scheme.
In the case where 1 the adversary gains no information about . Therefore, we
have Pr11. Since the simulator guesses 1 when , we have 12
Pr 12.
If 0 then the adversary sees an encryption of m. The adversarys advantage in
this situation isby definition. Therefore, we have Pr 01. Since the 12
simulatorguesses 0when,wehavePr 02.
The overall advantage of the simulator in the Decisional BDH game is 1 Pr
111111112 02 Pr12222 222 .
28
Reviews
There are no reviews yet.