Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming
We study the fundamental problem of frequency estimation under both privacy and communication constraints, where the data is distributed among $k$ parties. We consider two application scenarios: (1) one-shot, where the data is static and the aggregator conducts a one-time computation; and (2) streaming, where each party receives a stream of items over time and the aggregator continuously monitors the frequencies. We adopt the model of multiparty differential privacy (MDP), which is more general than local differential privacy (LDP) and (centralized) differential privacy. Our protocols achieve optimality (up to logarithmic factors) permissible by the more stringent of the two constraints. In particular, when specialized to the $\varepsilon$-LDP model, our protocol achieves an error of $\sqrt{k}/(e^{\Theta(\varepsilon)}-1)$ using $O(k\max\{ \varepsilon, \frac{1}{\varepsilon} \})$ bits of communication and $O(k \log u)$ bits of public randomness, where $u$ is the size of the domain.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Achieving Differential Privacy in Vertically Partitioned Multiparty Learning
Preserving differential privacy has been well studied under centralized setting. However, it's very challenging to preserve differential privacy under multiparty setting, especially for the vertically partitioned case. I…
Privacy PreservingTraining Differentially Private Models with Secure Multiparty Computation
We address the problem of learning a machine learning model from training data that originates at multiple data owners while providing formal privacy guarantees regarding the protection of each owner's data. Existing sol…
Privacy PreservingTowards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregation
We design a scalable algorithm to privately generate location heatmaps over decentralized data from millions of user devices. It aims to ensure differential privacy before data becomes visible to a service provider while…
A Hybrid Approach to Privacy-Preserving Federated Learning
Federated learning facilitates the collaborative training of models without the sharing of raw data. However, recent attacks demonstrate that simply maintaining data locality during training processes does not provide su…
BIG-bench Machine LearningFederated LearningPrivacy PreservingSecure and Privacy-Preserving Vertical Federated Learning
We propose a novel end-to-end privacy-preserving framework, instantiated by three efficient protocols for different deployment scenarios, covering both input and output privacy, for the vertically split scenario in feder…
Federated Learning