Ciphertext Policy Attribute Based Encryption

Today at PKC 2011 a talk was given by Hakan Seyalioglu on the paper by Brent Waters, entitled "Ciphertext-Policy Attribute-Based Encryption: An Expressive, Efficient, and Provably Secure Realization".

First, let us consider what attribute based encryption is and why this may be useful. In standard public key cryptography, a file is encrypted under a user's public key. The corresponding secret key (and that key alone) can then be used to decrypt the ciphertext. Now, assume users each have various attributes associated to them. For example, Alice may be in a group called "internal affairs", she is female, and based in the USA office of her organisation. Thus we assign her the attributes "internal affairs", "female" and "USA". If Bob wants to encrypt a document so it can be decrypted by everyone who is a member of the "internal affairs" group, he could create an encryption of the document for every user in this group using their public key. However, what if Bob does not know who is in the group? What if users are added to this group at a later time? In this situation, we can not use standard public key cryptography, therefore we turn to attribute based encryption (ABE).

In ABE, a key authority is considered to be a trusted party who generates keys for users within a system. The key authority has a master secret key (MSK) and public key (PK). For each user in the system the key authority generates keys based on the users attributes, using the MSK. Each user is then given their corresponding secret key, SK. Now, when a user wants to encrypt a document they construct a policy for this document. The policy specifies which attributes are required to decrypt this document, for example ("internal affairs" OR ("female" AND "Canada")). Given the constructed policy and the PK (of the key authority for a system), documents can then be encrypted and distributed to everyone - but only decrypted by users which match the policy assigned to the ciphertext.

Note that if we have the policy ("internal affairs" AND "female" AND "Canada") neither Bob (given the attributes "male" and "Canada") nor Alice should be able to decrypt documents with this policy. We can see that together they meet the criteria - so crucially, we do not want collusion between users to allow them to decrypt documents - only a user who meets the criteria alone should be able to decrypt the document.

Waters introduces a new ciphertext-policy based (as opposed to key-policy based) ABE. When one constructs a new scheme, the security must be considered - formally one produces a proof reducing to some hard cryptographic problem. One consideration when constructing new schemes is what hard problem we wish the scheme to be reduced to. However, ultimately security may depend on whether the hard problem to which you reduce is truly hard. Therefore, Waters gives several different constructions, each reducing to a different problem. One scheme has a ciphertext size of O(n), private key size of O(A) and an encryption time of O(n), where n is the size of an access formula (i.e. the size of the policy), and A is the number of attributes in a user's key. The other schemes have worse complexities, but reduce to different (harder) assumptions. This paper demonstrates well the trade off between assumptions required and the efficiency of the resulting scheme.