Broadcast Encryption with Size N1/3 and More from k-Lin

We present the first pairing-based ciphertext-policy attribute-based encryption (CP-ABE) scheme for the class of degree $3$ polynomials with compact parameters: the public key, ciphertext and secret keys comprise $O(n)$ group elements, where $n$ is input length for the function. As an immediate corollary, we obtain a pairing-based broadcast encryption scheme for $N$ users with $O(N^{1/3})$-sized parameters, breaking the long-standing $\sqrt{N}$ barrier for pairing-based broadcast encryption. All of our constructions achieve adaptive security against unbounded collusions, and rely on the (bilateral) $k$-Lin assumption in prime-order bilinear groups.