Practical constructions and new proof methods for large universe attribute-based encryption

We propose two large universe Attribute-Based Encryption constructions. In a large universe ABE system any string can be used as an attribute and attributes need not be enumerated at system setup. Our first construction establishes a novel large universe Ciphertext-Policy ABE scheme on prime order bilinear groups, while the second achieves a significant efficiency improvement over the large universe Key-Policy ABE system of Lewko-Waters and Lewko. Both schemes are selectively secure in the standard model under two ``q-type'' assumptions similar to ones used in prior works. Our work brings back ``program and cancel'' techniques to this problem and aims in providing practical large universe ABE implementations. To showcase the efficiency improvements over prior constructions, we provide implementations and benchmarks of our schemes in Charm; a programming environment for rapid prototyping of cryptographic primitives. We compare them to implementations of the only three published constructions that offer unbounded ABE in the standard model.