Attribute-Based Encryption (ABE) has become a huge area of research in cryptography over the past five years. Originally conceived as a system to allow for error-tolerance in identity-based encryption (IBE) for applications, such as biometrics, ABE has grown into a giant and has become the next big thing in cryptography. Ironically, IBE has been shown to be a specialized application of ABE and thus the new technology has eclipsed the scheme that it spawned from in size, complexity and power. ABE originally started by generalizing the definition of identity from a string to a set of attributes. This allows for the creation of a threshold value such that a message is encrypted and sent to a given identity. The message is then decrypted by the owner of that identity if the public key and private key are within a certain threshold of similarity. This concept was extended to allow for Boolean policies to be used with attributes to determine the requirements for decrypting a ciphertext. Additional research has created schemes for decentralizing ABE and for using ABE to sign messages.
Section 2 of this post will cover the basis of ABE as a generalization of IBE and will explain how Boolean policies can be created to allow for certain attribute requirements to decrypt a message. Sections 3 and 4 will deal with how these policies are attached to the messages. Section 5 details how to decentralize ABE such that attributes can be assigned by many different attribute authorities, some of which may be corrupt. Finally, section 6 discusses the concept of attribute-based signatures to provide message authentication for ABE schemes.
Fuzzy Identity-Based Encryption and Attribute Based Systems
ABE was first conceived by Sahai and Waters in their paper “Fuzzy Identity-Based Encryption”  as a means of allowing for a certain amount of error tolerance in IBE. At the time, identities used for IBE were strings that were associated with a given user. For example, the string email@example.com may be associated with a Gmail user named Mike Smith. In IBE, such an identity string is expected to be publicly known and is used to derive a public key to send encrypted messages to the owner of the identity. This makes the process of obtaining a public key to send private messages to a user much more simplistic than in a typical public key infrastructure where a user’s certificate must be obtained and verified before messages can be encrypted to him or her.
While IBE is useful in many applications, certain implementations were impossible under its original construction. One such example is in the case of using biometrics to derive a user’s public key. In such a situation, it is often the case that two biometric readings of the same person will differ by a small amount. In such situations, IBE is useless. Sahai and Waters set out to change this by creating an IBE scheme that allowed for a certain amount of error tolerance in the measurements that could be used to derive a public key. Their scheme views an identity as a set of descriptive attributes, rather than as a string. The proposed scheme allows for a user with a secret key ω’ to decrypt a message encrypted using the identity ω if and only if |ω ∩ ω′| ≥ d where d is a quantitative threshold value. In addition, the scheme issues all users a random polynomial. Any time an attribute’s private key component is assigned to a user, the user’s random polynomial is used to generate the component. In this way, different users cannot combine their separate attributes to decrypt a message that none of them would be able to decrypt individually, an attack known as collusion. The Sahai-Waters construction is secure in the Fuzzy Selective-ID model of security, which reduces to the hardness of the Decisional BDH assumption. In addition, the paper specifies that the scheme can be extended to be CCA secure in a straightforward manner.
A huge advantage of ABE over other encrypted schemes is that a user may use it to store private documents addressed to groups of users that fit a specific set of requirements on a public server. This works because in ABE each user is associated with a set of attributes. A party may encrypt a message under a specific set of attributes. And can then set a threshold value for the number of attributes required to decrypt the message. For example, perhaps a user would like to encrypt a message under the attributes MIT, Harvard, with a threshold value of 1. In this case, only parties that possess the attributes MIT or Harvard or both can decrypt the message. Similarly, if the threshold value was set to 0, then only users with both the MIT and the Harvard attributes can decrypt the message.
Secure Attribute-Based Systems with Non-Monotonic Access Structures
While the Sahai-Waters construction of ABE was an excellent first step, there were several limitations in their scheme that left much room for expansion. In particular, while the Sahai-Waters construction allowed for the encryption of a message to its intended recipients by selecting attributes, and it allowed for a threshold to be set such that only k-of-n attributes were required for decryption, their scheme did not detail a way to encrypt messages under more expressive policies. Additionally, ABE requires that for a k-of-n construction, k and n must be fixed constants across all Ciphertext objects created in an attribute system. Finally, the Sahai-Waters implementation of threshold values requires a large number of computations, slowing down the encryption scheme.
These issues were addressed by Piretti, Traynor, McDaniel and Waters in the paper “Secure Attribute-Based Systems” . First, the Threshold calculation function was replaced with a random oracle. This has two main advantages. In particular, it speeds up the computation of the key generation and encryption algorithms dramatically and it allows ciphertexts to contain variable numbers of attributes. On the other hand, the random oracle model also weakens the security of the encryption scheme by making the security of the entire scheme rest solely on the security of the cryptographic hash function used. This optimization makes threshold computations in ABE significantly faster than computations for equivalent functionality in RSA.
The second and most important contribution of the paper is the creation of the idea of attribute policies. An attribute policy is a plaintext Boolean expression that defines the combination of attributes that are necessary to decrypt a given message. To get this flexibility nothing but the basic structures of ABE are used, but combined in novel and clever ways. First the paper starts by dealing with atomic policies, that is policies over subsets of the complete attribute set, A. Note that from the ABE paper we already have a k-of-n threshold function. The authors show that AND and OR gates can be constructed by creating an n-of-n threshold and a 1-of-n threshold for attributes, respectively. The authors also show that once we get past the atomic building blocks of ABE policies, we can specify more complex combinations by combining policies with AND and OR gates. To encrypt policies under an OR gate, we can simply concatenate the encryption of each object under each policy. So for example, if we want to encrypt an object under two policies we would do E(oi, P1) * E(oi, P2). In the case that a user has attributes to satisfy one of the requisite policies then the user could decrypt at least one of the encryptions of the object. Similarly, to create logical AND gates, a user can encrypt an object under the first policy, and then encrypt this object under the second policy and so on, thus nesting the encryptions. To decrypt such a message, the receiver would have to decrypt under each policy sequentially. The authors point out that this situation does allow for collusion attacks, however, since one attacker may be able to decrypt one layer of the message encrypted under one policy, and other attackers may be able to decrypt other layers of the message under other policies.
Finally, the paper shows that the flexibility of ABE can be extended to allow for ABE to support variable k and n values in a k-of-n construction. Sahai and Waters themselves proposed two possible solutions to this problem in their original paper on fuzzy IBE. Their first solution was to create an upper limit on the number of attributes in a system and then to provide “default attributes” which could be used as a placeholder when fewer than the maximum number of attributes is to be used as the threshold value. However, this scheme is not fully expressive. The other Sahai-Waters solution was to create separate cryptosystems, each with a different k value. This scheme is much more expressive, but would require a large number of cryptosystems to be feasible. The authors instead proposed a hybrid scheme that makes use of both of these previous schemes. In this new scheme, the second scheme is used to create all of the n separate cryptosystems for 1 to n where n is the maximum number of attributes in the universe. Then, the first scheme is used to allow for varying the k value for each scheme.
These optimizations to ABE allow for many interesting applications. One proposed application in the paper was a HIPAA compliant electronic medical record encryption system, where parts of medical records could each be encrypted with a different policy. For example, a patient’s family medical history could be encrypted under one policy that might allow access for just doctors that take United Healthcare, while the same patient’s current prescriptions can be encrypted under a policy that might allow access for either doctors or nurses in offices that accept United Healthcare. Another proposed application was a social networking or online dating system in which each user can specify his or her own attributes and also policies for what attributes a person must have to view their profile.
One limitation of this work is that the proposed ABE scheme was still only able to express monotonic access structures. No method existed to express the need for a lack of an attribute in a given policy. A while later Ostrovsky, Sahai and Waters proposed a modification to ABE that gave it this functionality in the paper “Attribute-Based Encryption with Non-Monotonic Access Structures” , but the details of its implementation are highly mathematical and are outside the scope of a survey paper. Suffice it to say that current ABE schemes can express any access structure, including non-monotonic ones (meaning that the lack of an attribute can be expressed within attribute policies).
Key-Policy Attribute Based-Encryption
Existing ABE schemes can be divided into two forms: Key-Policy ABE (KP-ABE) and Ciphertext-Policy ABE (CP-ABE). KP-ABE was introduced in the paper “Attribute-Based Encryption for Fine-Grained Access Control of Encrypted Data” by Goyal, Pandey, Sahai and Waters . It deviates from the original Sahai-Waters construction in that the Sahai-Waters construction originally proposed that users would have a set of attributes, and documents would be encrypted under a set of attributes. If there enough overlap between the set of user and ciphertext attributes to be within a certain acceptable threshold then the user would be able to decrypt the ciphertext. As detailed above, after more complex access structures were created using this scheme a fundamental limitation arose in that there was no way to create an AND gate not susceptible to collusion attacks. This is a critical flaw in the practicality of the scheme since collusion resistance is considered a necessary condition to ensure the security and usefulness of ABE. KP-ABE and CP-ABE are complimentary schemes that both address this limitation.
In Key-Policy ABE, data is annotated with attributes and access policies are associated with keys. This sounds a bit counterintuitive so an (admittedly contrived) example is in order. Perhaps a lieutenant wants to encrypt orders for his superior officer. In this case, the lieutenant would encrypt his message and annotate it with the attributes “captain” and “Easy Company” (the name of his company). Now, say the captain’s superior officer (a major) wants to read the message. The major’s access policy would be: (“major” OR “captain” OR “lieutenant” OR “private”) AND “Easy Company”. In this way, a major can read messages designated to his subordinates within the company. Note that this example is a form of Hierarchical IBE (HIBE), which is a well-known application of ABE that was discussed in the paper. More information on HIBE as implemented with ABE can be found in the paper “Unbounded HIBE and Attribute-Based Encryption” by Lewko and Waters .
For KP-ABE to work, private keys are actually Boolean expressions composed of attributes. When a user attempts to decrypt a message, the attributes annotating the document are matched up with the attributes in the Boolean expression. If the expression is satisfied then the user is able to decrypt the document. This is implemented as a tree-access structure in the paper. In such a tree, the exterior nodes are associated with attributes and the interior nodes are logic gates. A traversal of the tree determines whether the policy is satisfied by the attributes present in the document or not.
KP-ABE also allows for delegation of new attributes to users so long as they are more restrictive than current attributes. For example, a professor with the attribute “Professor” may use this attribute to derive an attribute for only professors in his own lab from his secret key for the professor attribute. Let’s say he calls the new attribute “Lab A Professor”. Now he can distribute this key to professors in his own lab and subsequently he can now encrypt messages to only the professors in his lab. It should be noted that because the KP-ABE paper includes a re-randomization step in the key derivation process, the derived key is completely independent of the original key and as such information about the key used to derive the new attribute key is not leaked.
Ciphertext-Policy Attribute-Based Encryption
Ciphertext-Policy Attribute-Based Encryption (CP-ABE) was first conceived by Bethencourt, Sahai and Waters in the paper “Ciphertext-Policy Attribute-Based Encryption” . It is essentially the opposite of KP-ABE. Rather than having a message be annotated with attributes, the message is encrypted with an access-structure formulated as a Boolean expression over a set of attributes. Users possess sets of attributes and if a user’s attributes satisfy the access policy of the ciphertext then the message can be decrypted and the plaintext recovered. The CP-ABE paper makes a few key contributions to ABE. In particular, the scheme is collusion-resistant and can be easily extended into a CCA-secure implementation, as described in the paper, while providing rudimentary revocation support (that is still far from optimal). Finally, the paper details the cpabe toolkit—a complete implementation of the CP-ABE scheme the authors developed.
Collusion resistance is accomplished by randomizing a user’s private key so that private keys for attributes from different users cannot be combined to create a valid decryption key for the document. Unlike in Sahai-Waters, however, the secret sharing is embedded in the ciphertext. In order to decrypt a given ciphertext, a user must possess all of the given key components to remove blinding values from decryptions of the ciphertext. If users attempt to collude, they won’t be able to compute the value needed to remove the blinding values because the different users’ private keys contain randomness that make them incompatible with each other.
The paper contains a scheme for key revocation that is accomplished by having keys expire on dates baked into the keys, but by allowing integer comparisons in the policy and by allowing the creation of numerical attributes that can be compared in the extended policy. In this way the scheme allows for the decryption of a message if the user’s current date key is more current than the date key used in encrypting the message. Calling this a valid revocation scheme is a bit of a stretch, since a user is still able to decrypt a message even after his key has expired as long as the message he is trying to decrypt was encrypted with a date key that expired before his date key did. In this sense, the scheme never allows a user to lose access to messages that they once had access to. In addition, this scheme does not allow for per-user access revocation at all.
 At the time of this writing the toolkit could be downloaded here: http://acsc.cs.utexas.edu/cpabe/
Decentralized Attribute-Based Encryption
A common requirement in all of the systems previously described is that they require an individual, centralized authority to verify and issue keys for all attributes that a user is to possess. In certain cases this model is perfectly adequate, but in others the model does not provide enough flexibility to be used to reliably protect data and prevent collusion. Several recent papers have dealt with this issue, the first of which is “Multi-Authority Attribute Based Encryption” by Chase . Chase provides an example of needing to encrypt a message addressed to drivers in the state of Rhode Island that attend Brown University and are eligible voters. In such a case, the recipient of the message possesses three attributes, but each of these attributes is issued by a different authority (the RI RMV, Brown University, and the RI Elections Board). This poses an interesting problem for the security of ABE, as in a realistic situation, each authority would be responsible for verifying that applicants for private attribute keys actually possess the attributes in question and for issuing such keys. A realistic problem with such a scheme, however, is that it becomes difficult to prevent collusion, as different users could pool credentials obtained from separate sources.
To address this problem, Chase proposes that each user be issued a global identifier (GID) that must be presented whenever a new credential is issued. This GID makes it so that all credentials used to decrypt a message must share the same GID, but otherwise the ABE construction works the same was as Sahai-Waters. Chase further extends this scheme to allow for the case that an arbitrary number of attribute authorities may be corrupt. To allow for such a case, a central authority must be constructed that may or may not also be an attribute authority, but that also has the role of knowing enough of the state of each of the authorities that it is able to reconstruct the master secret for a given user at a given attribute authority that is then used along with the GID to derive the user’s private attribute key. This master secret can be used to derive a user’s private key component for an attribute, and can thus allow a user to decrypt a message despite the presence of corrupt authorities. In this case, only one authority needs to be trusted in order for the user to recover the message.
In the paper “Decentralizing Attribute-Based Encryption,”  Lewko and Waters significantly improved upon this idea by removing the requirements that there need be a trusted central authority. Additionally, any party can act as an authority and issue attributes to any other party in the universe. In this system, corrupt authorities will not affect any other authorities, and any user can act as an authority.
In order to do this, Lewko and Waters use a GID in the scheme in order to tie private key components together. The scheme uses the random oracle model to achieve this, thus weakening the security of the system by making it rely on the quality of the security of the hash function used. In their scheme, a user’s GID is hashed and included in each piece of the key for an attribute. In this way, an attribute issued to a user is tied to this unique user to make collusion difficult.
Another useful application of ABE is in creating attribute-based signatures (ABS). In “Attribute-Based Signatures”  Maji, Prabhakaran and Rosulek describe a system for doing exactly that. They begin their paper with an interesting use case: say a whistleblower in the financial department at a major corporation wants to leak information about an illegal scheme happening at the company to the media. The whistleblower can retain anonymity while still proving to the media outlets that she does in fact work at the company she claims in the financial department by using ABS to sign the press release.
The key feature of attribute-based signatures is that they must be unforgeable and provide verification of credentials while still retaining signer anonymity. The paper compares attribute-based signatures to group signatures, ring signatures and mesh signatures stating they are all similar in that they are unforgeable and they provide anonymity for the signer. On the other hand, the authors state that their ABS scheme is unique in that it simply proves that a single user with a specific set of attributes has signed the message. A key aspect of ABS is that it must not allow parties to collude on signatures, otherwise the guarantees that it provides will be broken. The other schemes mentioned are noted to be either more restrictive than ABS (ring, group) or vulnerable to collusion (mesh).
The paper gives a formal security definition of ABS and proposes a framework for constructing such schemes with associated proofs. The paper then goes on to extend the signature scheme to multi-authority systems. It is important to note that in this case the paper uses a centralized authority called a signature trustee to set up the parameters for the signature scheme and to provide keys to the attribute authorities, which do not have to be trusted. This creates a bottleneck in the system similar to the one in Chase’s paper. Future research will undoubtedly look at how to remove the requirement for a centralized, trusted signature trustee from the equation.
Finally, the paper discusses several applications of ABS schemes. Attribute-based messaging is a relatively obvious use of ABS in which the send of an encrypted message signs the message himself to prove to the recipients that he has a given set of credentials. In this way ABS provides authentication for message senders. A more interesting use of ABS detailed in the paper is as an authentication mechanism as part of a challenge protocol. In such a system, a client can request access to a resource on a server, and the server can send the client a random challenge string and a policy. The client would then generate a session key and send the server an ABS signature containing (challenge, sessionkey) signed under the policy it received and then encrypted and sent to the server. This scheme would be secure against man-in-the-middle attacks. The paper also extend the scheme into a trust negotiation protocol.
ABE provides a versatile encryption framework that uniquely couples policy-enforcement and access control with cryptography. This allows for fewer resources to be deployed in order to prevent unauthorized access to data. It also provides greater security than is possible with access control servers, as there is no danger of a server being compromised, thus giving an attacker to all of the data that is intended to be secret. As a result, I predict that ABE research will continue at a very fast pace and I think in the future, we will see the development of products that use ABE for various security applications. As detailed above, ABE is a particularly good fit for situations where privileged data can be kept on untrusted servers. Additionally, ABE has been shown in the papers reviewed as a part of this survey to be useful for tasks as broad as biometric IBE, social network security, HIPAA compliant healthcare security, HIBE, and as specific as leaking sensitive data and documents anonymously.
Current and Future Research Topics
The most noted missing feature of ABE is revocation support. Right now, there is no good way to revoke a user’s identity in an ABE system without revoking each of his attributes. Additionally, even attribute revocation poses problems. Proposed schemes to handle such issues have been based on having expiring attributes. These systems have many flaws as pointed out in this paper. If a way to revoke individual attributes and user identities were created on an individual level, rather than across the whole universe, ABE would likely find its way into many shipping products.
Another area of potential research is in creating a decentralized ABS scheme that does not rely on a trusted signature authority. As was the case with decentralized ABE, the requirement for a centralized, trusted entity creates a bottleneck in the system since every user must access the same entity. Similarly, if the entity ever goes offline, it would cause a disruption in the whole system since it would be a single point of failure.
 J. Bethencourt, A. Sahai, and B. Waters. Ciphertext-policy attribute-based encryption. In IEEE Symposium on Security and Privacy, pp. 321-334, 2007.
 M. Chase. Multi-Authority Attribute-Based Encryption. In proceedings of Theoretical Cryptography Conference (TCC) 2007.
 V. Goyal, O. Pandey, A. Sahai, and B. Waters. Attribute-based encryption for fine-grained access control of encrypted data. In ACM Conference on Computer and Communications Security, pp. 89-98, 2006.
 A. B. Lewko and B. Waters. Decentralizing attribute-based encryption. In EUROCRYPT, 2011.
 A. B. Lewko and B. Waters. Unbounded hibe and attribute-based encryption. In EUROCRYPT, 2011.
 A. B. Lewko, T. Okamoto, A. Sahai, K. Takashima, and B. Waters. Fully secure functional encryption: Attribute-based encryption and (hierarchical) inner product encryption. In EUROCRYPT, pp. 62-91, 2010.
 J. Li, M. H. Au, W. Susilo, D. Xie, K. Ren, “Attribute-Based Signature and Its Applications”, In ACM Symposium on Information, Computer and Communications Security (ASIACCS 2010), pages 60 – 69, ACM Press , 2010
 H. K. Maji, M. Prabhakaran, and M. Rosulek. Attribute-based signatures. In Proceedings of the 11th international conference on Topics in cryptology: CT-RSA 2011 (CT-RSA’11), Aggelos Kiayias (Ed.). Springer-Verlag, Berlin, Heidelberg, 376-392. 2011.
 R. Ostrovsky, A. Sahai, and B. Waters. Attribute-based encryption with non-monotonic access structures. In ACM Conference on Computer and Communications Security, pp. 195-203, 2007
 M. Pirretti, P. Traynor, P. McDaniel, and B. Waters. Secure attribute-based systems. In ACM Conference on Computer and Communications Security, pp. 99-112, 2006.
 A. Sahai and B. Waters. Fuzzy identity based encryption. In Eurocrypt 2005.