Bounds and constructions for key distribution schemes

Yvo Desmedt*, Niels Duif, Henk Van Tilborg, Huaxiong Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


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 t vertices in the network. It follows that, in general, the sender needs to transmit at least t + 1 shares of the message over different paths to the intended receiver and that each participant needs to possess at least t + 1 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 hat are needed to guarantee secure communication becomes a relevant parameter. Our security relies on the random oracle model.

Original languageEnglish
Pages (from-to)273-293
Number of pages21
JournalAdvances in Mathematics of Communications
Issue number3
Publication statusPublished - Aug 2009


  • Ad hoc networks
  • Block designs
  • Combinatorics
  • Graph theory
  • Key distribution
  • Privacy
  • Secure communication
  • Steiner systems


Dive into the research topics of 'Bounds and constructions for key distribution schemes'. Together they form a unique fingerprint.

Cite this