Optimal Symmetric Secret Distribution of Star Networks

摘要

In this paper, we present a lower bound on secret distribution in star network. Examples of star communication network exist in various systems including sensor networks where there is one base station and several sensors that need to communicate with it. While the previous result had shown the possibility of performing secret distribution in a star network using 2 log n secrets, the lower bound for this problem was unknown. With this motivation, in this paper, we derive a tight bound for the number of secrets required for secret distribution in a star network. We show that as n, the number of satellite nodes in the star network, tends to infinity, it suffices to maintain log n + 1/2 log log n + 1 secrets at the center node. However, log n + 1/2 log log n secrets do not. Even in the absence of the constraint of n approaches infinity, we argue that these bounds are reasonably tight, i.e., there are several examples for finite values of n where log n+1/2 log log n) secrets do not suffice although log n + 1/2 log log n + 1) secrets suffice for virtually all cases of practical interest. We also show that our protocol could provide a tradeoff between internal and external attacks and to reduce the number of secrets in acyclic, planar and fully connected bipartite graphs.