A note on the set systems used for broadcast encryption

Abstract

An exclusive set system is a family of subsets of a universe with the property that every large subset may be written as the union of subsets from the family. We obtain new upper bounds on the size of such families, showing that in a universe of n elements, there is a system of 48k3 (nk)r/k ln n subsets with the property that every subset of the universe of size n - r can be written as the union of k subsets in the system. Such sets systems form the combinatorial foundation of many broadcast encryption schemes.