Coordination Under Security Constraints

Abstract

We undertake an investigation on the nature of communication for secure coordination. Coordination places constraints on the joint behavior of agents in a network. Two different approaches to coordination are considered. Strong coordination may be understood as the distributed generation of correlated random variables, while empirical coordination has close ties with the theory of lossy compression i.e. rate-distortion theory.

Secrecy is a natural requirement for strong coordination, which seeks to synthesize actions that appear random even when subjected to statistical tests. For strong coordination, we show that perfect secrecy is more stringent than a game-theoretic formulation of secrecy. A number of networks are analyzed, with tight results for several cases of interest. A complete solution is provided for arbitrarily long cascade networks. We also study the effect of localized common randomness among nodes and in doing so, revisit a conjecture about the relation between strong coordination and empirical coordination.

Secure empirical coordination may be viewed as a repeated game being played between the communication system and an eavesdropper. In this context, we show that perfect secrecy is less stringent than a game-theoretic formulation of secrecy. We solve the problem for a three-node network with a two-sided helper under some restrictions. We highlight a connection between the theory of linear-quadratic-Gaussian optimal control and rate-distortion theory. An optimistic result from the asymptotic theory is used to provide a tight bound for real-time control. Using this as motivation, we optimize the secure empirical coordination rate region under the Gaussian distribution.

We supplement our asymptotic results on secure coordination by devising optimal codes for real-time secure communication. These problems are of a combinatorial flavor. Both fixed-length and variable-length encodings are considered. The fixed-length code design problem is equivalent to a maximum weighted matching problem on hypergraphs. We provide algorithms to design the optimal code when secrecy is measured by Hamming distortion or equivocation. We demonstrate the benefit of a stochastic encoder and provide a near-optimal construction for one bit of secret key. For variable-length encodings, we characterize the optimal payoff-key curve under zero-delay encoding -- albeit at the expense of a high communication rate.