Secure distributed computation over hierarchical networks with heterogeneous data
Hierarchical Secure Distributed Linearly Separable Computation with Arbitrary Heterogeneous Data Assignment
Distributed, Parallel, and Cluster Computing
Summary
This paper looks at how to safely perform calculations using data spread across many users connected through a three-layer network (users, relays, server). The goal is for the server to get only the final computed results and not learn anything else about individual users’ data, while relays should also learn nothing about the data. The authors handle cases where users hold different amounts and types of data and develop methods that still work even if some users stop responding or try to mislead. Their work extends from simple single-result computations to more complex multiple-result tasks.
What this means in practice
- •For cloud service engineers: Implement secure and efficient distributed computations in cloud platforms with users holding different datasets and unreliable participation.
- •For data privacy teams: Protect sensitive user data during multi-layer distributed computations by ensuring intermediate servers and relays learn no private inputs.
Authors
Ziting Zhang, Chenyi Sun, Kai Wan, Xiang Zhang
Abstract
This paper studies secure distributed linearly separable computation over a three-layer hierarchical network, where clustered users communicate with a central server through relays. The server aims to recover Kc linear combinations of K intermediate outcomes, where each intermediate outcome is a separable function of one dataset. We consider a more general setting with arbitrary heterogeneous data assignment across users, where ''arbitrary'' means that the data assignment is given in advance (which can be in any form) and ''heterogeneous'' means that the users may hold different numbers of datasets. Under this assignment, each user computes the intermediate outcomes of its assigned datasets and sends masked messages to its associated relay. The relays subsequently process and forward the received messages to the server. We impose two security constraints: (i) security against server, requiring the server to learn only the desired task function without gaining any additional information about users' inputs; and (ii) security against relays, ensuring each relay learns nothing about users' inputs. Moreover, the server or any relay may collude with a subset of users. For Kc=1, the underlying computation reduces to distributed gradient coding. We propose a secure scheme tolerating user dropouts and user collusion, achieving the optimal two-layer communication rates in one regime and order-optimal communication rates within a factor of 2 in the other regime. For Kc>1, we extend the proposed construction to multi-dimensional linearly separable tasks under the no-dropout setting.