Privacy-Preservation Over Directed Graphs: A Case Study of Average Consensus

Privacy preservation over directed graphs remains poorly understood: asymmetry breaks reciprocity, invalidates extensions from undirected settings, and alters what an adversary can infer from message exchanges. Using average consensus as a canonical case, we (i) present an information-theoretic analysis that establishes a lower bound on unavoidable leakage for any exactly accurate protocol, and (ii) propose a new algorithm that achieves this bound while preserving exact accuracy. Formally, within an ideal-world secure multiparty computation framework, we prove that any exactly accurate protocol inevitably reveals, to an honest-but-curious adversary, the partial sums of the honest connected components that remain after corrupt nodes are removed. Guided by this insight, we propose a secret-sharing-based scheme that integrates seamlessly with any consensus algorithm and achieves the privacy bound without compromising accuracy. Experimental simulations consolidate our theoretical results: the proposed method attains the privacy bound, converges to the exact average, and outperforms prior approaches in terms of both privacy and accuracy.