Bounds and constructions for key distribution schemes

Pages: 273 - 293,
Volume 3,
Issue 3,
August
2009 doi:10.3934/amc.2009.3.273

Yvo Desmedt - BT Chair of Information Security, Department of Computer Science, University College London, London, United Kingdom (email)

Niels Duif - Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, Netherlands (email)

Henk van Tilborg - Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, Netherlands (email)

Huaxiong Wang - Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore (email)

Abstract:
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 that are needed to guarantee secure communication becomes a relevant parameter. Our security relies on the random oracle model.

Keywords: Key distribution, secure communication, ad hoc networks, privacy, graph theory, block designs, Steiner systems, combinatorics.

Mathematics Subject Classification: Primary: 94A60; Secondary: 11T71, 14G50.

Received: March 2009;
Revised:
June 2009;
Available Online: August 2009.