Provably Private Distributed Averaging Consensus: An Information-Theoretic Approach
Provably Private Distributed Averaging Consensus: An Information-Theoretic Approach
复制标题
DOI：
10.1109/tit.2023.3300711
复制
发表时间：
2022-02
影响因子：
2.5
通讯作者：
Mohammad Fereydounian;Aryan Mokhtari;Ramtin Pedarsani;Hamed Hassani
中科院分区：
文献类型：
--
作者：
Mohammad Fereydounian;Aryan Mokhtari;Ramtin Pedarsani;Hamed Hassani
在这项工作中，我们专注于以私人方式解决分散的共识问题。彼此之间，分布式共识问题是一个经典的问题，其收敛特征是众所周知的。与邻近的节点交换有关用户本地值的信息。我们的建议方法是仔细设计从每个节点传递给其邻居的噪声消息，以使共识算法仍然准确地收敛到本地的平均值值，虽然有关本地值的最小信息是通过精确表征节点的私人消息和另一个对手收集的所有消息来形式化的。在没有所谓的广义叶子的情况下，为任何网络保留了隐私，并在隐私时间和收敛时间之间进行了权衡。可以通过我们的方法实现，而所需的隐私水平只会影响收敛时间。
In this work, we focus on solving a decentralized consensus problem in a private manner. Specifically, we consider a setting in which a group of nodes, connected through a network, aim at computing the mean of their local values without revealing those values to each other. The distributed consensus problem is a classic problem that has been extensively studied and its convergence characteristics are well-known. However, state-of-the-art consensus methods build on the idea of exchanging local information with neighboring nodes which leaks information about the users’ local values. We propose an algorithmic framework that is capable of achieving the convergence limit and rate of classic consensus algorithms while keeping the users’ local values private. The key idea of our proposed method is to carefully design noisy messages that are passed from each node to its neighbors such that the consensus algorithm still converges precisely to the average of local values, while a minimum amount of information about local values is leaked. We formalize this by precisely characterizing the mutual information between the private message of a node and all the messages that another adversary collects over time. We prove that our method is capable of preserving users’ privacy for any network without a so-called generalized leaf, and formalize the trade-off between privacy and convergence time. Unlike many private algorithms, any desired accuracy is achievable by our method, and the required level of privacy only affects the convergence time.