
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 deriving bounds on the information storage at each node as well as on the total information which the subkeys contain. It is shown that KDP's will not in general give KDS's with node storage as good as that achieved by the KDS's of Blom, but the difference will be negligible if \(w\) is small with respect to \(n\).
secure networks, Cryptography, key distribution patterns
secure networks, Cryptography, key distribution patterns
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 9 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
