Perfectly-Secure Key Distribution for Dynamic Conferences

Abstract

A key distribution scheme for dynamic conferences is a method by which initially an (off-line) trusted server distributes private individual pieces of information to a set of users. Later any group of users of a given size (a dynamic conference) is able to compute a common secure key. In this paper we study the theory and applications of such perfectly secure systems. In this setting, any group of t users can compute a common key by each user computing using only his private piece of information and the identities of the other t − 1 group users. 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 t-size conference comprised of other users.First we consider a non-interactive model where users compute the common key without any interaction. We prove a lower bound on the size of the user's piece of information of\( \left( {\begin{array}{*{20}c} {k + t - 1} \\ {t - 1} \\ \end{array} } \right) \) times the size of the common key. We then establish the optimality of this bound, by describing and analyzing a scheme which exactly meets this limitation (the construction extends the one in []). Then, we consider the model where interaction is allowed in the common key computation phase, and show a gap between the models by exhibiting an interactive scheme in which the user's information is only k + t − 1 times the size of the common key. We further show various applications and useful modifications of our basic scheme. Finally, we present its adaptation to network topologies with neighborhood constraints.