Unbounded Broadcast and KP-ABE with Sublinear Ciphertext from Pairings

We present the first pairing-based unbounded broadcast encryption and key-policy attribute-based encryption (KP-ABE) with sublinear ciphertext size. Here, unbounded means set-up and the public parameters do not impose a bound on the size of the broadcast set, attribute length, or policy size.

• Our broadcast encryption scheme supports an unbounded number of users, and achieves $|mpk| = O(1), |ct| = O(\sqrt{N}), |sk| = O(\sqrt{N})$ where $N$ denotes an upper bound on the size of the broadcast set.
• Our KP-ABE supports boolean formula and span programs, and achieves $|mpk| = O(1), |ct| = O(\sqrt{N}), |sk| = O(\sqrt{N} \cdot |f|)$ where $N$ is the attribute length and $|f|$ the policy size. We prove adaptive security for the broadcast encryption and selective security for the KP-ABE, based on the $k$-Lin assumption in the standard model without random oracles.