Cryptology ePrint Archive: Report 2016/304
A Fast Attribute Based Encryption
Abstract: Our new Access Control Encryption is an implementation of CP-ABE, when used as part of a key delivery mechanism for an encrypted Data Base. It focuses on improving performance. In ACE the access policies are any predicates over the set of object attributes. Efficiency gains are most pronounced when the DNF representations of policies are compact. In ACE, within the life span of the keys, each user has to perform very few ABE decryptions, regardless of the number of policies accessible to her. Keys to most objects are then computed using only symmetric key decryptions.
ACE is not the first to utilize symmetric key cryptography to reduce the number of CP-ABE operations, when access policies form a multi-level partially ordered set. However, in addition to this significant saving, ACE also takes advantage of overlaps among policies on clauses of the policies, thus further reducing computational complexity.
Let R denote the number of user roles, N be the number of object access policies, k the ratio between the cost of CP-ABE encryption and symmetric key encryption complexities (for 10 attributes k is about a million), and N=cR. The gain factor of ACE vs. a competing hybrid system is kc/(k+c). Usually c>>1, but in some systems it may happen that c<1.
ACE is composed of two sub systems encrypting the same messages: A CP-ABE and a symmetric key encryption system. We prove that ACE is secure under a new Uniform Security Game that we propose and justify, assuming that its building blocks, namely CP-ABE and block ciphers are secure. We require that CP-ABE be secure under the Selective Set Model, and that the block cipher be secure under Multi-User CPA, which we define.
We present Policy Encryption (PE) that can replace CP-ABE as a component of ACE. In many cases, PE is more efficient than CP-ABE. However PE does not prevent collusions. Instead it limits collusions. PE is useful in those cases where owners can compartmentalize objects and subjects, so that within each compartment the owners can tolerate collusions. PE prevents inter compartmental collusions. PE has also the following appealing properties: It relies on older hence more reliable intractability assumption, the Computational Diffie-Hellman assumption, whereas CP-ABE relies on the newer Bilinear Diffie-Hellman assumption. PE uses off-the shelf standard crypto building blocks with one small modification, with proven security. For a small number of compartments PE is much faster than CP-ABE. PE and CP-ABE can coexist in the same system, where ABE is used in high security compartments.
We apply ACE to a practical financial example, the Consolidate Audit Trail (CAT), which is expected to become the largest repository of financial data in the world.
Category / Keywords: Access Control, Attribute Based Encryption, Hierarchical Key Derivation, Monotone Access Structures, Semantic Security, Hybrid Argument proof technique.
Date: received 17 Mar 2016, last revised 28 Mar 2016
Contact author: yacov at live com
Available format(s): PDF | BibTeX Citation
Note: Added 3 references in section 5.
Version: 20160328:150009 (All versions of this report)
Short URL: ia.cr/2016/304
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]