Weighted universal recovery, practical secrecy, and an efficient algorithm for solving both

摘要

In this paper, we consider a network of n nodes, each initially possessing a subset of packets. Each node is permitted to broadcast functions of its own packets and the messages it receives to all other nodes via an error-free channel. We provide an algorithm that efficiently solves the Weighted Universal Recovery Problem and the Secrecy Generation Problem for this network. In the Weighted Universal Recovery Problem, the goal is to design a sequence of transmissions that ultimately permits all nodes to recover all packets initially present in the network. We show how to compute a transmission scheme that is optimal in the sense that the weighted sum of the number of transmissions is minimized. For the Secrecy Generation Problem, the goal is to generate a secret-key among the nodes that cannot be derived by an eavesdropper privy to the transmissions. In particular, we wish to generate a secret-key of maximum size. Further, we discuss private-key generation, which applies to the case where a subset of nodes is compromised by the eavesdropper. For the network under consideration, both of these problems are combinatorial in nature. We demonstrate that each of these problems can be solved efficiently and exactly. Notably, we do not require any terms to grow asymptotically large to obtain our results. This is in sharp contrast to classical information-theoretic problems despite the fact that our problems are information-theoretic in nature. Finally, the algorithm we describe efficiently solves an Integer Linear Program of a particular form. Due to the general form we consider, it may prove useful beyond these applications.