06-09-2016, 03:47 PM
1453309780-AttributeBasedEncryptionforFineGrainedAccessControlofEncryptedData1.rtf (Size: 1.36 MB / Downloads: 4)
As more sensitive data is shared and stored by third-party 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 coarse-grained level (i.e., giving another party your private key). We develop a new cryptosystem for ¯ne-grained sharing of encrypted data that we call Key-Policy Attribute-Based Encryption (KP-ABE). 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 audit-log information and broadcast encryption. Our construction supports delegation of private keys which subsumes Hierarchical Identity-Based 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 ¯ne-grained level. Suppose a particular user wants to grant decryption access to a party to all of its Internet tra±c logs for all entries on a particular range of dates that had a source IP address from a particular subnet. The user 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. 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 Attributed-Based Encryption (ABE). In an ABE system, a user's 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 user's 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 error-tolerant encryption with biometrics, the lack of expressibility seems to limit its applicability to larger systems.
Our Contribution. We develop a much richer type of attribute-based 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 speci¯es which type of ciphertexts the key can decrypt. We call such a scheme a Key-Policy Attribute-Based Encryption (KP-ABE), since the access structure is speci¯ed 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 secret-sharing scheme that speci¯es 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 di®erent parties. Any set of parties that satisfy the tree can reconstruct the secret.
In our construction each user's key is associated with a tree-access structure where the leaves are associated with attributes.2 A user is able to decrypt a ciphertext if the attributes associated with a ciphertext satisfy the key's access structure. The primary di®erence between our setting and secret-sharing schemes is that while secret-sharing schemes allow for cooperation between di®erent 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 ¯ne-grained 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 Identity-Based Encryption
1.1 Organization
We begin with a discussion of related work in Section 2. Next, we give necessary back-ground information and our de¯nitions of security in Section 3. We then present our ¯rst 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
Fine-grained Access Control. Fine-grained access control systems facilitate granting di®erential access rights to a set of users and allow °exibility in specifying the access rights of individual users. Several techniques are known for implementing ¯ne 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 classi¯ed 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 ¯ne grained access control. In our techniques, the data is stored on the server in an encrypted form while di®erent users are still allowed to decrypt di®erent pieces of data per the security policy. This e®ectively eliminates the need to rely on the storage server for preventing unauthorized data access.
Secret-Sharing Schemes. Secret-sharing 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 de¯nes the sets of parties who should be able to reconstruct the secret by using their shares.
Shamir [35] and Blakley [7] were the ¯rst to propose a construction for secret-sharing 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 Shamir's idea to realize any access structure that can be represented as a tree consisting of threshold gates. Other notable secret-sharing schemes are [25, 15].
In SSS, one can specify a tree-access structure where the interior nodes consist of AND and OR gates and the leaves consist of di®erent parties. Any set of parties that satisfy the tree can come together and reconstruct the secret. Therefore in SSS, collusion among di®erent users (or parties) is not only allowed but required.
In our construction each user's key is associated with a tree-access 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 key's access structure. In our scheme, contrary to SSS, users should be unable to collude in any meaningful way.
Identity-Based Encryption and Extensions. The concept of Attribute-Based Encryp-tion was introduced by Sahai and Waters [34], who also presented a particular scheme that they called Fuzzy Identity-Based Encryption (FIBE). The Fuzzy-IBE scheme builds upon several ideas from Identity-Based 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, !0, if and only if the identities ! and !0 are 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 !0, a private key for a set of attributes ! enables decrypting that message, if and only if j! \ !0j ¸ d, where d is ¯xed 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 ¯xed at the setup time.
We develop a much richer type of attribute-based encryption. The private keys of di®erent users might be associated with di®erent 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 collusion-resistant manner implies a forward secure Hierarchical IBE scheme. They also note how their techniques for resisting collusion attacks are useful in attribute-based 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 ¯rst give formal de¯nitions for the security of Key-Policy Attribute Based Encryp-tion (KP-ABE). Then we give background information on bilinear maps and our crypto-graphic assumption. Finally, we give some background on linear secret-sharing schemes
4
and monotone span programs.
3.1 De¯nitions
De¯nition 1 (Access Structure [4]) Let fP1; P2; : : : ; Png be a set of parties. A collec-tion A µ 2fP1;P2;:::;Png is monotone if 8B; C : if B 2 A and B µ C then C 2 A. An access
structure (respectively, monotone access structure) is a collection (respectively, monotone collection) A of non-empty subsets of fP1; P2; : : : ; Png, i.e., A µ 2fP1;P2;:::;Pngnf;g. 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 (ine±ciently) 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 (Key-Policy) 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 input { an access structure A, the master key MK and the public parameters PK. It outputs a decryption key D.
Decryption This algorithm takes as input { the ciphertext E that was encrypted under the set ° of attributes, the decryption key D for access control structure A and the public parameters PK. It outputs the message M if ° 2 A.
We now discuss the security of an ABE scheme. We de¯ne a selective-set model for proving the security of the attribute based under chosen plaintext attack. This model can be seen as analogous to the selective-ID model [16, 17, 8] used in identity-based encryption (IBE) schemes [36, 10, 18].
Selective-Set 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 ° 2= Aj for all j.
Challenge The adversary submits two equal length messages M0 and M1. The challenger °ips a random coin b, and encrypts Mb with °. The ciphertext is passed to the adversary.