Aattribute based encryption (ABE) and its two flavors

In a conventional public key cryptosystem, there are two distinct keys: a public key and a private key. Bob uses Alice's public key to encrypt a message to Alice. Alice uses her private key to decrypt the message. How does Bob know the public key of Alice? Alice may have given the public key using a secure communication channel. This works only if there is already some trust/familiarity between both Bob and Alice. What if Bob and Alice do not know each other? This method fails. In an unknown open system, we need a trusted third party (TTP) to uniquely bind public keys to users or another entity such as an organization. This is where we need a PKI (Public Key Infrastructure). A PKI has one more trusted entities called Certification Authorities (CAs). For example, Verisign is a CA. CA issues Alice a certificate (which contains the public key of Alice) signed by the CA's public key after verifying Alice's credentials. Bob can now retrieve Alice's certificate and verify it is authentic by checking the signature on it. Certificates may need to be revoked later due to various reasons. For example, if Alice's private key is stolen, she will have to ask the CA to revoke its certificate. How does Bob know if a certificate is revoked? The CA maintains a revocation list which allows Bob to verify if a given certificate is revoked or not. The traditional PKI is somewhat cumbersome as one needs to retrieve certificates, check revocation list, and then encrypt. Is there a better way of doing public key cryptography? Some smart researchers came up with the idea of using user identities (for example, your email address) as public keys [2, 3]. Such systems are called IBE (identity based encryption). How an IBE works? There is no magic here; you still need a trusted third party, but it eliminates the need to do the certificate look up. The idea is as follows:

There is a TTP called KGS (Key Generation Server). Given an identity, KGS generates a private key and the identity acts as the public key. For example, Alice's identity is her email address alice@example.com. Alice uses this identity to obtain a private key from the KGS. Now Bob encrypts a message using Alice's email. Only Alice can decrypt the message since the identity, the public key, alice@example.com belongs to Alice and only she can obtain the private from the KGS. Notice that there is a huge trust placed on the KGS. The security of the whole system relies on the security of the KGS and how well the KGS authenticates users before issuing private keys.


The idea of IBE was further improved to support much better systems. The concept of attribute-based encryption (ABE) has been introduced by Sahai and Waters [6]. ABE can be considered as a generalization of identity based encryption [2, 3] (IBE), where, as mentioned earlier, the encryption is based on some identity. Thus, ABE is more expressive than IBE. In an ABE system, the plaintext is encrypted with a set of attributes. The KGS, which possesses the master key, issues different private keys to users after authenticating the attributes they possess. Thus, these private keys are associated with the set of attributes each user possesses. In its basic form, a user can decrypt a cipher text if and only if there is a match between the attributes
of the ciphertext and the user’s key. For example, Alice has the attributes "role = doc" and "age > 18". Now Bob encrypts a message using the attributes ("role = student" AND "age > 18"). Alice can decrypt the message as she satisfies both attributes. Bob encrypts another message using the attributes ("role = professor" OR "role = staff"). Alice cannot decrypt the message as she does not satisfy the policy. (The workings of the actual ABE schemes are a little different from the above examples, but they give the essential idea behind the schemes.)

The initial ABE system is limited only to threshold policies where there should be at least k out of n attributes common between the attributes used to encrypt the plaintext and the attributes users possess. Pirretti et al. [5] gave an implementation of such a threshold ABE system using a variant of the Sahai-Waters Large Universe construction [6]. For example, Bob encrypts a message for any 3 attributes out of the 5 attributes {a1, a2, a3, a4, a5}. Alice has the attributes {a1, a2, a4, a5} and Eve has {a1, a2}. While Alice can decrypt Bob's message, Eve cannot as she does not satisfy the threshold policy.

Since the initial threshold scheme, a few variants have been introduced to provide more expressive ABE systems. Out of them there are two important variants.

1. Key Policy ABE (KP-ABE)
2. Ciphertext Policy ABE (CP-ABE)

Goyal et al. [4] introduced the idea of KP-ABE systems and Bethencourt et al. [1] introduced the idea of CP-ABE systems. Let's try to understand the idea behind these two variants using diagrams.



As shown in the above diagram, in KP-ABE, Bob encrypts a message using a set of attributes. It defines an access structure, which is a threshold tree of the policy that Bob wants to enforce. Alice and Tim tries to decrypt the message. The attributes Alice has satisfy the access structure and hence she can derive the key and decrypt the document. The attributes Tim has do not satisfy the access structure and therefore cannot derive the key to decrypt the message. The key idea here is that the key is associated with the policy using an access structure.



As shown in the above diagram, CP-ABE reverses the role of encryption and key derivation. The encryption is associate with an access structure which is constructed using the policy. KGS simply issues private keys for the attributes users have. If users (rather their attributes) satisfy the owner defined access structure, they can decrypt it. The second variant is more closer to encryption found in open systems as the ciphertext is associated the policy.



References:
[1] J. Bethencourt, A. Sahai, and B. Waters. Ciphertext-policy attribute-based encryption. In SP ’07: Proceedings of the 2007 IEEE Symposium on Security and Privacy, pages 321–334, Washington, DC, USA, 2007. IEEE Computer Society.
[2] D. Boneh and M. Franklin. Identity-based encryption from the weil pairing. In CRYPTO ’01: Proceedings of the 21st Annual International Cryptology Conference
on Advances in Cryptology, pages 213–229. Springer-Verlag, 2001.
[3] C. Cocks. An identity based encryption scheme based on quadratic residues. In Proceedings of the 8th IMA International Conference on Cryptography and Coding,
pages 360–363, London, UK, 2001. Springer-Verlag.
[4] V. Goyal, O. Pandey, A. Sahai, and B. Waters. Attribute-based encryption for fine-grained access control of encrypted data. In CCS ’06: Proceedings of the 13th ACM conference on Computer and communications security, pages 89–98, New York, NY, USA, 2006. ACM.
[5] M. Pirretti, P. Traynor, P. McDaniel, and B. Waters. Secure attribute-based systems. In CCS ’06: Proceedings of the 13th ACM conference on Computer
and communications security, pages 99–112, New York, NY, USA, 2006. ACM.
[6] A. Sahai and B. Waters. Fuzzy identity-based encryption. In Eurocrypt 2005, LNCS 3494, pages 457–473. Springer-Verlag, 2005.