August  2009, 3(3): 273-293. doi: 10.3934/amc.2009.3.273

Bounds and constructions for key distribution schemes


BT Chair of Information Security, Department of Computer Science, University College London, London, United Kingdom


Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, Netherlands


Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore

Received  March 2009 Revised  June 2009 Published  August 2009

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.
Citation: Yvo Desmedt, Niels Duif, Henk van Tilborg, Huaxiong Wang. Bounds and constructions for key distribution schemes. Advances in Mathematics of Communications, 2009, 3 (3) : 273-293. doi: 10.3934/amc.2009.3.273

Tuvi Etzion, Alexander Vardy. On $q$-analogs of Steiner systems and covering designs. Advances in Mathematics of Communications, 2011, 5 (2) : 161-176. doi: 10.3934/amc.2011.5.161


Serap Ergün, Sirma Zeynep Alparslan Gök, Tuncay Aydoǧan, Gerhard Wilhelm Weber. Performance analysis of a cooperative flow game algorithm in ad hoc networks and a comparison to Dijkstra's algorithm. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1085-1100. doi: 10.3934/jimo.2018086


Andrew J. Majda, Yuan Yuan. Fundamental limitations of Ad hoc linear and quadratic multi-level regression models for physical systems. Discrete & Continuous Dynamical Systems - B, 2012, 17 (4) : 1333-1363. doi: 10.3934/dcdsb.2012.17.1333


Mirela Domijan, Markus Kirkilionis. Graph theory and qualitative analysis of reaction networks. Networks & Heterogeneous Media, 2008, 3 (2) : 295-322. doi: 10.3934/nhm.2008.3.295


M. D. König, Stefano Battiston, M. Napoletano, F. Schweitzer. On algebraic graph theory and the dynamics of innovation networks. Networks & Heterogeneous Media, 2008, 3 (2) : 201-219. doi: 10.3934/nhm.2008.3.201


Kazuhiko Kuraya, Hiroyuki Masuyama, Shoji Kasahara. Load distribution performance of super-node based peer-to-peer communication networks: A nonstationary Markov chain approach. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 593-610. doi: 10.3934/naco.2011.1.593


Ruiqiang Guo, Lu Song. Optical chaotic secure algorithm based on space laser communication. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1355-1369. doi: 10.3934/dcdss.2019093


Mohammad Sadeq Dousti, Rasool Jalili. FORSAKES: A forward-secure authenticated key exchange protocol based on symmetric key-evolving schemes. Advances in Mathematics of Communications, 2015, 9 (4) : 471-514. doi: 10.3934/amc.2015.9.471


Hirotada Honda. On a model of target detection in molecular communication networks. Networks & Heterogeneous Media, 2019, 14 (4) : 633-657. doi: 10.3934/nhm.2019025


Joseph D. Skufca, Erik M. Bollt. Communication and Synchronization in Disconnected Networks with Dynamic Topology: Moving Neighborhood Networks. Mathematical Biosciences & Engineering, 2004, 1 (2) : 347-359. doi: 10.3934/mbe.2004.1.347


I-Lin Wang, Ju-Chun Lin. A compaction scheme and generator for distribution networks. Journal of Industrial & Management Optimization, 2016, 12 (1) : 117-140. doi: 10.3934/jimo.2016.12.117


Ginestra Bianconi, Riccardo Zecchina. Viable flux distribution in metabolic networks. Networks & Heterogeneous Media, 2008, 3 (2) : 361-369. doi: 10.3934/nhm.2008.3.361


Guangzhou Chen, Yue Guo, Yong Zhang. Further results on the existence of super-simple pairwise balanced designs with block sizes 3 and 4. Advances in Mathematics of Communications, 2018, 12 (2) : 351-362. doi: 10.3934/amc.2018022


Karthikeyan Rajagopal, Serdar Cicek, Akif Akgul, Sajad Jafari, Anitha Karthikeyan. Chaotic cuttlesh: king of camouage with self-excited and hidden flows, its fractional-order form and communication designs with fractional form. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1001-1013. doi: 10.3934/dcdsb.2019205


Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete & Continuous Dynamical Systems, 2011, 30 (1) : 261-298. doi: 10.3934/dcds.2011.30.261


Alessia Marigo. Optimal traffic distribution and priority coefficients for telecommunication networks. Networks & Heterogeneous Media, 2006, 1 (2) : 315-336. doi: 10.3934/nhm.2006.1.315


Katayun Barmak, Eva Eggeling, Maria Emelianenko, Yekaterina Epshteyn, David Kinderlehrer, Richard Sharp, Shlomo Ta'asan. An entropy based theory of the grain boundary character distribution. Discrete & Continuous Dynamical Systems, 2011, 30 (2) : 427-454. doi: 10.3934/dcds.2011.30.427


Barton E. Lee. Consensus and voting on large graphs: An application of graph limit theory. Discrete & Continuous Dynamical Systems, 2018, 38 (4) : 1719-1744. doi: 10.3934/dcds.2018071


Jake Bouvrie, Boumediene Hamzi. Kernel methods for the approximation of some key quantities of nonlinear systems. Journal of Computational Dynamics, 2017, 4 (1&2) : 1-19. doi: 10.3934/jcd.2017001


Chun-Xiang Guo, Guo Qiang, Jin Mao-Zhu, Zhihan Lv. Dynamic systems based on preference graph and distance. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1139-1154. doi: 10.3934/dcdss.2015.8.1139

2020 Impact Factor: 0.935


  • PDF downloads (85)
  • HTML views (0)
  • Cited by (6)

[Back to Top]