演讲人： David Woodruff MIT
时间： 2006-04-07 10:00-2006-04-07 11:00
地点：FIT Building,Tsinghua University
内容：

A family of subsets C of [n] = {1, ..., n} is (r,t)-exclusive if for every subset S of [n] of size at least n-r, there exist sets S1, ..., St in C with S = S1 U S2 U ... U St. These families, also known as complement-cover families, have broad applications, such as information-theoretic broadcast encryption, multi-certificate revocation, and group-testing. We give the first explicit construction of such families with size poly(r, t){n choose r}^{1/t}, essentially matching a basic lower bound. Our techniques are algebraic in nature.
When r,t are small, as is the case for many applications, our construction is tight up to a factor of r. We also provide a poly(r,t, log n) algorithm for finding S1, ..., St, which is crucial for efficient use in applications. Previous constructions either had much larger size, were randomized and took exponential time to find S1, ..., St, or did not work for arbitrary n, r, and t.
Finally, we improve the lower bound on the number of sets containing a given i in [n]. The lower bound shows that our derived broadcast encryption schemes have essentially optimal total number of keys and keys per user for a given number of users n, transmission size t, and revoked set size r. We achieve similar optimality results for multi-certificate revocation.
(Joint work with Craig Gentry and Zulfikar Ramzan.)
 

个人简介: