Introduction to Attribute Based Encryption (ABE)

Attribute based encryption is an important security concept that can be applied to almost any role based system today to provide data confidentiality and integrity. Enjoy the read.

Background: to clearly understand this article, you must have an understanding of basic security concepts and terms such as encryption, decryption, ciphertext, public key cryptography and symmetric key cryptography.

The concept of attribute-based encryption was first proposed in a landmark work by Amit Sahai and Brent Waters [1] and later by Vipul Goyal, Omkant Pandey, Amit Sahai and Brent Waters [2]. It is a type of public-key encryption in which the secret key of a user and the ciphertext are dependent upon attributes (e.g. the country he lives, or the kind of subscription he has). In such a system, the decryption of a ciphertext is possible only if the set of attributes of the user key matches the attributes of the ciphertext. A crucial security feature of Attribute-Based Encryption is collusion-resistance: An adversary that holds multiple keys should only be able to access data if at least one individual key grants access.

Problem

Here we take an in depth look at the problem that ABE tries to solve. We look at this problem from the perspective of an online social network (OSN).

A user’s data is encrypted and stored on the internet. One drawback of traditional encryption schemes is that this data can be only shared at a coarse grain level, meaning that any user with the decryption key can decrypt this data. ABE allows a user to encrypt data in such a way that the user can share it at a fine grained level. Let’s look at an example:

Suppose a user Adam has many social connections that he categorizes into one or many of the groups friends, colleagues, family and neighbors. Adam has a data X that he would like to share with his friends and colleagues. In order to share this data with his friends and colleagues, Adam has to generate an encryption and decryption key pair, encrypt the data and share the key with his friends and colleagues. Adam has another data Y he would like to share with his family and friends and family. Again, Adam needs to generate a key pair, encrypt data Y and share the decryption key with friends and family. The problem here is that for each content that Adam create, he has to generate a new key pair.

A simple solution to the above solution would be to generate a key pair for each category of social connections. So Adam would generate a key pair for friends, one for family and so on. Now to share data X, Adam encrypts this data with friends encryption key and share this ciphertext with friends and encrypts data X with colleagues encryption key and share this data with colleagues. This solution would work great and improve efficiency as well as storage used since we generate less keys and store less keys.

However, social relations are not as simple as defined above, and a single social connection of Adam may fall into more than one of the given categories. For example, a social connection can be both a friend and family or both a friend and colleague. Also, Adam may want to restrict sharing a data to a more complex set of users. Let’s assume that Adam has another data Z that he would only like to share with persons who are both his friend and colleague. With our current scheme, to do this Adam would encrypt data Z with the encryption key of friends to get a ciphertext CT, and then further encrypt this ciphertext CT with the encryption key of colleagues. Now only a person who is both a friend and a colleague can decrypt this data.

The above scheme however can be easily broken through collision. Data Z is encrypted by both the encryption keys of friend and colleague. Even though this data is meant for a person who is both a friend and a colleague, if a person who has the friend decryption key and another who has the colleague decryption key collude, they can still decrypt this data.

ABE solves the above problem. In ABE policies are described through attributes (age, relationship, trust, location, etc.). From an OSN perspective, the categories of social connections are treated as attributes. Adam is able to encrypt the data in such a way that only if the attributes match a given key then the data can be decrypted. Users colluding cannot decrypt the data.

ABE uses a tree-based access structure which must be satisfied with a given set of attributes in order to decrypt the data. The tree-based access structure allows the encryptor to specify which attributes can decrypt the data. It uses operators such as AND, OR and k-of-n. AND is usually known as’ n of n’ and OR is known as ‘1 of n’. For example, if Adam wants to encrypt a data P such that only someone with the attributes friend AND colleague or the attribute family can decrypt it, the tree-based access structure would look like Figure 1: ABE Access Structure.

ABE Access Structure

Figure 1: ABE Access Structure

In figure 1, we see that each leaf on the tree returns true or false. The tree is traversed from leaves to root. We see that from the bottom right, a user needs all two of the attributes friend and colleague to satisfy this branch. Then after this level is traversed, the second level is traversed, and here we see if a user is a family or satisfied the previous traversal, it would return true since the k of n requirements her is 1 out of 2.

There are two types of variant of Attribute based encryption, one is key-policy attribute based encryption (KP-ABE) [2] and other is cipher-policy attribute based encryption (CP-ABE) [3].


Key-policy attribute based encryption (KP-ABE)

In KP-APE, the owner of the data creates a master key. Using the master key, the owner encrypts the data such that a ciphertext is labeled with a set of attributes. The private key (decryption key) given to others to decrypt the data is associated with a tree-based access structure which specifies which ciphertext the key can decrypt. The tree-based access structure contains leaves which are associated with attributes. A user is able to decrypt a cipher text if the attributes associated with the ciphertext satisfies the user’s key access structure [2]. Below are some applications of KP-ABE taken directly from the work of Goyal et al. [2].

KP-ABE Applications

An important application of KP-ABE deals with secure forensic analysis: One of the most important needs for electronic forensic analysis is an “audit log” containing a detailed account 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 that needs to legitimately access the audit log contents (for instance a forensic analyst) would require the secret key – thereby 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 large-scale networked systems such as the Global Information Grid, where diverse secret, top secret and highly classified information will need to appear intermingled in distributed audit logs.

The KP-ABE 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 structure” – which 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, 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 [2].

Another application of KP-ABE would be 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 economies-of-scale offered by a broadcast channel, while still being able to deliver programming targeted at the needs or wishes of individual users.


Ciphertext-policy attribute based encryption (CP-ABE)

Contrary to KP-ABE, in CP-ABE system, a user’s private key is associated with a set of attributes. When a party encrypts a message in this system, they specify an associated access structure over attributes and associate this access structure with the ciphertext. A user will only be able to decrypt a ciphertext if that user’s attributes pass through the cipher text’s access structure [3].

CP-ABE is similar to the recent work of Sahai and Waters [1] and KP-ABE by Goyal et al. [2], however CP-ABE require substantially new techniques. In KP-ABE, ciphertexts are associated with sets of descriptive attributes, and users' keys are associated with policies (the reverse of CP-ABE). In KP-ABE, the encryptor exerts no control over who has access to the data she encrypts, except by her choice of descriptive attributes for the data. Rather, she must trust that the key-issuer issues the appropriate keys to grant or deny access to the appropriate users. In other words, in [1,2] the intelligence is assumed to be with the key issuer, and not the encryptor. In CP-ABE, the encryptor must be able to intelligently decide who should or should not have access to the data that she encrypts [3]. CP-ABE allows for a new type of encrypted access control where user's private keys are specified by a set of attributes and a party encrypting data can specify a policy over these attributes specifying which users are able to decrypt. CP-ABE is suitable for enforcing access control on data based on a set of attributes. Below are some applications of KP-ABE taken directly from the work of Bethencourt et al. [3].

CP-ABE Applications

In many situations, when a user encrypts sensitive data, it is imperative that she establish a specific access control policy on who can decrypt this data. For example, suppose that the FBI public corruption offices in Knoxville and San Francisco are investigating an allegation of bribery involving a San Francisco lobbyist and a Tennessee congressman. The head FBI agent may want to encrypt a sensitive memo so that only personnel that have certain credentials or attributes can access it. For instance, the head agent may specify the following access structure for accessing this information: ((“Public Corruption Office" AND (“Knoxville" OR “San Francisco")) OR (management-level > 5) OR “Name: Charlie Eppes"). By this, the head agent could mean that the memo should only be seen by agents who work at the public corruption offices at Knoxville or San Francisco, FBI officials very high up in the management chain, and a consultant named Charlie Eppes. As illustrated by this example, it can be crucial that the person in possession of the secret data be able to choose an access policy based on specific knowledge of the underlying data. Furthermore, this person may not know the exact identities of all other people who should be able to access the data, but rather she may only have a way to describe them in terms of descriptive attributes or credentials.

References: 
[1] Amit Sahai and Brent Waters, "Fuzzy Identity-Based Encryption," in EUROCRYPT, Aarhus, 2005, pp. 457-473.
[2] Vipul Goyal, Omkant Pandey, Amit Sahai, and Brent Waters, "Attribute-based encryption for fine-grained access control of encrypted data," in CCS'06, New York, 2006, pp. 89-98.
[3] J Bethencourt, Amit Sahai, and Brent Waters, "Ciphertext-Policy Attribute-Based Encryption," in SP'07, 2007, pp. 321-334.