Bounds and constructions for key distribution schemes

Key distribution schemes play a significant role in key assignment schemes which allow participants in a network to communicate by means of symmetric cryptography in a secure way without the need of a unique key for every pair of participants. It is assumed that an adversary can eavesdrop on all communication and can corrupt up to vertices in the network. It follows that, in general, the sender needs to transmit at least shares of the message over different paths to the intended receiver and that each participant needs to possess at least encryption keys. We do assume that vertices in the network will forward messages correctly (but only the corrupted vertices will collude with the adversary to retrieve the message). We focus on two approaches. In the first approach, the goal is to minimize the number of keys per participant. An almost complete answer is presented. The second approach is to minimize the total number of keys that are needed in the network. The number of communication paths that are needed to guarantee secure communication becomes a relevant parameter. Our security relies on the random oracle model.