Bounds for key distribution patterns
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\).
- Key storage in secure networks
- Some constructions for key distribution patterns
- Secure frameproof codes, key distribution patterns, group testing algorithms and related structures
- Constructions for key distribution patterns
- Key distribution patterns using tangent circle structures
- On key storage in secure networks
- Some new bounds for cover-free families
- Bounds and constructions for key distribution schemes
- Steiner key distribution patterns
- Few Steiner systems S(3,k,v) are KDPs
- Some constructions of mutually orthogonal Latin squares and superimposed codes
- scientific article; zbMATH DE number 1008447 (Why is no real title available?)
- scientific article; zbMATH DE number 1024493 (Why is no real title available?)
- A Review of Secret Key Distribution Based on Bounded Observability
- Binary representations of underdetermined data and superimposed codes
- Tree-Based Key Distribution Patterns
- Advances in Cryptology - ASIACRYPT 2003
- Uniqueness of some optimal superimposed codes
This page was built for publication: Bounds for key distribution patterns
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1819120)
