A family of subsets C of [n] \underline{\underline {def}} {1, . . . , n} is (r, t)- exclusive if for every S \subset [n] of size at least n - r, there exist S_1, . . . , S_t \in C with S = S_1\cupS_2\cup? ? ? \cupS_t. These families, also known as complement-cover families, have cryptographic applications, and form the basis of informationtheoretic broadcast encryption and multi-certificate revocation. We give the first explicit construction of such families with size poly(r,t)n^{r/t}, essentially matching a basic lower bound. Our techniques are algebraic in nature.

When r = O(t), as is natural for many applications, we can improve our bound to poly(r,t)\left( \begin{gathered} n \hfill \\ r \hfill \\ \end{gathered} \right)^{1/t}. Further, when r, t are small, our construction is tight up to a factor of r. We also provide a poly(r, t, log n) algorithm for finding S_1, . . . , S_t, which is crucial for efficient use in applications. Previous constructions either had much larger size, were randomized and took super-polynomial time to find S_1, . . . , S_t, or did not work for arbitrary n, r, and t. Finally, we improve the known lower bound on the number of sets containing each i \in [n]. Our bound shows that our derived broadcast encryption schemes have essentially optimal total number of keys and keys per user for n users, transmission size t, and revoked set size r.