Ciphertext-Policy Attribute-Based Encryption

1 Ciphertext-Policy Attribute-Based EncryptionJohn BethencourtCarnegie Mellon Sahai Waters SRI several distributed systems a user should only beable to access data if a user posses a certain set of cre-dentials or attributes. Currently, the only method forenforcing such policies is to employ a trusted server tostore the data and mediate access control. However, ifany server storing the data is compromised, then theconfidentiality of the data will be compromised. In thispaper we present a system for realizing complex accesscontrol on encrypted data that we call ciphertext -PolicyAttribute- based Encryption . By using our techniquesencrypted data can be kept confidential even if the stor-age server is untrusted; moreover, our methods aresecure against collusion attacks. Previous Attribute-Based Encryption systems used attributes to describethe encrypted data and built policies into user s keys;while in our system attributes are used to describe auser s credentials, and a party encrypting data deter-mines a policy for who can decrypt.

2 Thus, our meth-ods are conceptually closer to traditional access controlmethods such as Role- based Access Control (RBAC).In addition, we provide an implementation of our sys-tem and give performance IntroductionIn many situations, when a user encrypts sensitivedata, it is imperative that she establish a specific ac-cess control policy on who can decrypt this data. Forexample, suppose that the FBI public corruption of-fices in Knoxville and San Francisco are investigatingan allegation of bribery involving a San Francisco lob-byist and a Tennessee congressman. The head FBIagent may want to encrypt a sensitive memo so thatonly personnel that have certain credentials or at- Supported the US Army Research Office under the CyberTAGrant No. W911NF-06-1-0316. Supported by NSF CNS-0524252 and the US Army ResearchOffice under the CyberTA Grant No. can access it. For instance, the head agentmay specify the following access structure for accessingthis information:(( Public Corruption Office AND( Knoxville OR San Francisco ))OR(management-level>5)OR Name: CharlieEppes ).

3 By this, the head agent could mean that the memoshould only be seen by agents who work at the publiccorruption offices at Knoxville or San Francisco, FBIofficials very high up in the management chain, and aconsultant named Charlie illustrated by this example, it can be crucial thatthe person in possession of the secret data be able tochoose an access policy based on specific knowledge ofthe underlying data. Furthermore, this person maynot know the exact identities of all other people whoshould be able to access the data, but rather she mayonly have a way to describe them in terms of descriptiveattributes or , this type of expressive access controlis enforced by employing a trusted server to store datalocally. The server is entrusted as a reference monitorthat checks that a user presents proper certification be-fore allowing him to access records or files. However,services are increasingly storing data in a distributedfashion across many servers.

4 Replicating data acrossseveral locations has advantages in both performanceand reliability. The drawback of this trend is that it isincreasingly difficult to guarantee the security of datausing traditional methods; when data is stored at sev-eral locations, the chances that one of them has beencompromised increases dramatically. For these reasonswe would like to require that sensitive data is stored inan encrypted form so that it will remain private evenif a server is existing public key Encryption methods allowa party to encrypt data to a particular user, but areunable to efficiently handle more expressive types of en-crypted access control such as the example this work, we provide the firstconstruction of aciphertext- policy Attribute-Based en-cryption (CP-ABE)to address this problem, and givethe first construction of such a scheme. In our system,a user s private key will be associated with an arbi-trary number of attributes expressed as strings.

5 Onthe other hand, when a party encrypts a message in oursystem, they specify an associated access structure overattributes. A user will only be able to decrypt a cipher-text if that user s attributes pass through the cipher-text s access structure. At a mathematical level, ac-cess structures in our system are described by a mono-tonic access tree , where nodes of the access struc-ture are composed of threshold gates and the leavesdescribe attributes. We note thatANDgates can beconstructed asn-of-nthreshold gates andORgatesas 1-of-nthreshold gates. Furthermore, we can handlemore complex access controls such as numeric rangesby converting them to small access trees (see discussionin the implementation section for more details).Our a high level, our work is sim-ilar to the recent work of Sahai and Waters [24] andGoyal et al. [15] on key- policy attribute based encryp-tion (KP-ABE), however we require substantially newtechniques.

6 In key- policy attribute based Encryption ,ciphertexts are associated with sets of descriptive at-tributes, and users keys are associated with policies(the reverse of our situation).We stress that in key- policy ABE, the encryptor exerts no control over whohas access to the data she encrypts, except by her choiceof descriptive attributes for the , she musttrust that the key-issuer issues the appropriate keysto grant or deny access to the appropriate users. Inother words, in [24, 15], the intelligence is assumedto be with the key issuer, and not the encryptor. In oursetting, the encryptor must be able to intelligently de-cide who should or should not have access to the datathat she encrypts. As such, the techniques of [24, 15]do not apply to our setting, and we must develop a technical level, the main objective that we mustattain iscollusion-resistance: If multiple users collude,they should only be able to decrypt a ciphertext if atleast one of the users could decrypt it on their own.

7 Inparticular, referring back to the example from the be-ginning of this Introduction, suppose that an FBI agentthat works in the terrorism office in San Francisco col-ludes with a friend who works in the public corruptionoffice in New York. We do not want these colluders tobe able to decrypt the secret memo by combining theirattributes. This type of security is thesine qua nonofaccess control in our the work of [24, 15], collusion resistance is in-sured by using a secret-sharing scheme and embeddingindependently chosen secret shares into each privatekey. Because of the independence of the randomnessused in each invocation of the secret sharing scheme,collusion-resistance follows. In our scenario, users pri-vate keys are associated withsetsof attributes insteadof access structures over them, and so secret sharingschemes do not , we devise a novel private key randomizationtechnique that uses a new two-level random maskingmethodology.

8 This methodology makes use of groupswith efficiently computable bilinear maps, and it is thekey to our security proof, which we give in the genericbilinear group model [6, 28].Finally, we provide an implementation of our systemto show that our system performs well in practice. Weprovide a description of both our API and the structureof our implementation. In addition, we provide severaltechniques for optimizing decryption performance andmeasure our performance features remainder of our paper is struc-tured as follows. In Section 2 we discuss related Section 3 we our definitions and give backgroundon groups with efficiently computable bilinear then give our construction in Section 4. We thenpresent our implementation and performance measure-ments in Section 5. Finally, we conclude in Section Related WorkSahai and Waters [24] introduced attribute -basedencryption (ABE) as a new means for encrypted ac-cess control.

9 In an Attribute-Based Encryption systemciphertexts are not necessarily encrypted to one par-ticular user as in traditional public key both users private keys and ciphertexts will beassociated with a set of attributes or a policy over at-tributes. A user is able to decrypt a ciphertext if thereis a match between his private key and the cipher-text. In their original system Sahai and Waters pre-sented a Threshold ABE system in which ciphertextswere labeled with a set of attributesSand a user s pri-vate key was associated with both a threshold param-eterkand another set of attributesS . In order for auser to decrypt a ciphertext at leastkattributes mustoverlap between the ciphertext and his private of the primary original motivations for this wasto design an error-tolerant (or Fuzzy) identity-basedencryption [27, 7, 12] scheme that could use primary drawback of the Sahai-Waters [24]threshold ABE system is that the threshold semanticsare not very expressive and therefore are limiting fordesigning more general systems.

10 Goyal et al. intro-duced the idea of a more generalkey-policyattribute- based Encryption system. In their construction a ci-phertext is associated with a set of attributes and auser s key can be associated with any monotonic tree-access construction of Goyal et be viewed as an extension of the Sahai-Waters tech-niques where instead of embedding a Shamir [26] secretsharing scheme in the private key, the authority embedsa more general secret sharing scheme for monotonic ac-cess trees. Goyal et. al. also suggested the possibilityof a Ciphertext-Policy ABE scheme, but did not offerany et al. [23] gave an implementation ofthe threshold ABE Encryption system, demonstrateddifferent applications of Attribute-Based encryptionschemes and addressed several practical notions such askey-revocation. In recent work, Chase [11] gave a con-struction for a multi-authority Attribute-Based encryp-tion system, where each authority would administer adifferent domain of attributes.