Bounds for key distribution patterns (Q1819120)

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\).