Functional Dependence of Secrets in a Collaboration Network

Abstract. A collaboration network is a graph formed by communica-tion channels between parties. Parties communicate over these channels to establish secrets, simultaneously enforcing interdependencies between the secrets. The paper studies properties of these interdependencies that are induced by the topology of the network. In previous work, the au-thors developed a complete logical system for one such property, inde-pendence, also known in the information flow literature as nondeducibil-ity. This work describes a complete and decidable logical system for the functional dependence relation between sets of secrets over a collabo-ration network. The system extends Armstrong’s system of axioms for functional dependency in databases.