Perfectly secure key distribution for dynamic conferences

In this paper we analyze perfectly secure key distribution schemes for dynamic conferences. In this setting, any member of a group of t users can compute a common key using only his private initial piece of information and the identities of the other t - 1 users in the group. Keys are secure against coalitions of up to k users; that is, even if k users pool together their pieces they cannot compute anything about a key of any conference comprised of t other users. First we consider a noninteractive model where users compute the common key without any interaction. We prove the tight bound on the size of each user's piece of information of ((k+t-1)(t-1)) times the size of the common key. Then, we consider the model where interaction is allowed in the common key computation phase and show a gap between the models by exhibiting a one-round interactive scheme in which the user's information is only k + t - 1 times the size of the common key. Finally, we present its adaptation to network topologies with neighbourhood constraints and to asymmetric (e.g., client-server) communication models, (C) 1998 Academic Press.