Bounds for key distribution patterns
type: Item
instance of: scholarly article
title: Bounds for key distribution patterns
zbMATH Open document ID: 0944.94009
author: Kathleen A. S. Quinn
published in: Journal of Cryptology
publication date: 2000-09-24T00:00:00Z
review text: Consider a network of \(v\) nodes. It is desired for a server to give each node sufficient information so that any two nodes wishing to communicate with a symmetric cryptosystem can derive a unique and secure common key from the information each has. It will be assumed the keys have \(n\) bits. A key distribution scheme (KDS) is a means to achieve this goal. A KDS is said to \(w\)-secure if, given any pair of nodes, any set of \(w\) or fewer other nodes are unable to collaborate to gain an advantage in guessing the key in use between two other nodes. Clearly the trivial KDS where each node is given a unique key for each of the other nodes, is \((v-2)\)-secure. It has previously been shown [\textit{R. Blom}, An optimal class of symmetric key generation systems, Eurocrypt, `84, Lect. Notes Comput. Sci. 209, 335-338 (1984)] that in any \(w\)-secure system, each node must store at least \((w+1)n\) bits and this lower bound is tight. An incidence structure is a triple \({\mathcal S} = ({\mathcal P}, {\mathcal B}, {\mathcal I})\) where \({\mathcal P}\) and \({\mathcal B}\) are non-empty sets of objects, called points (nodes) and blocks (subkeys) respectively and \({\mathcal I} \subseteq {\mathcal P} \times {\mathcal B}\). The set of blocks incident with a point \(P\) is denoted by \((P)\) and the set of points incident with a block \(x\) is denoted \((x)\). A \(w\)-secure key distribution pattern (\(w\)-KDP) is a finite incidence structure \({\mathcal K} = ({\mathcal P},{\mathcal B},{\mathcal I})\) with at least \(w+2\) points with the property that \[ (P_1) \cap (P_2) \not\subseteq (Q_1) \cup (Q_2) \cup \cdots \cup (Q_w) \] for all subsets \(\{ P_i , Q_j \}\) of \(w+2\) points of \({\mathcal P}\) where \(w \geq 1\). The known bounds on the number of subkeys at each node and the total number of subkeys are reviewed and new bounds are given. The question of the extent to which the key storage requirements of a network can be reduced by the use of a KDP is considered by der…
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 1385124
zbMATH Keywords: key distribution patterns
zbMATH Keywords: secure networks
reviewed by: Ian Blake
MaRDI profile type: Publication
full work available at URL: s001459900054
OpenAlex ID: W2059022735
DOI: 10.1007/S001459900054
description: scientific article; zbMATH DE number 1385124