Efficient broadcast encryption using multiple interpolation methods

We propose a new broadcast encryption scheme based on polynomial interpolations. Our scheme, obtained from the Naor-Pinkas scheme by partitioning the user set and interpolating multiple polynomials, turns out to be better in efficiency than the best known broadcast schemes like the Subset Difference and the Layered Subset Difference methods, which are tree based schemes. More precisely, when r users are revoked among n users, our method requires O(log(n/m)) user keys and O(αr + m) transmission overhead in the worst case, where m is the number of partitions of the user set and can be chosen to optimize its efficiency, and α is a predetermined constant satisfying 1 < α < 2. So, our scheme is always better in the storage than the tree based schemes (whose storage overhead is O(log² n) or O(log ^3/2 n)). In the transmission overhead, our scheme beats those schemes except for a very small r/n. The computation cost is worse than the other schemes but is reasonable for systems with moderate computing power. The security proof is given based on the computational Diffie-Hellman problem.