GENERALIZED BEIMEL-CHOR SCHEMES FOR BROADCAST ENCRYPTION AND INTERACTIVE KEY DISTRIBUTION

In 1993, Beimel and Chor presented an unconditionally secure interacti ve protocol which allows a subset of users in a network to establish a common key. This scheme made use of a key predistribution scheme due to Blom, In this paper, we describe some variations and generalization s of the Beimel-Chor scheme, including broadcast encryption schemes as well as interactive key distribution schemes. Our constructions use t he key predistribution scheme of Blundo et al., which is a generalizat ion of the Blom scheme. We obtain families of schemes in which the amo unt of secret information held by the network users can be traded off against the amount of information that needs to be broadcast. We also consider lower bounds for protocols of these types, using the concept of entropy as our main tool. Some of our schemes are optimal (or close to optimal) with respect to the bounds we prove. (C) 1998-Elsevier Sc ience B,V, All rights reserved.