Paper 2026/1960

Unbounded Broadcast and KP-ABE with Sublinear Ciphertext from Pairings

Abstract

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.