A Comprehensive Comparison of Multiparty Secure Additions with Differential Privacy

By Slawomir Goryczka, Li Xiong. 2015

161 citations recorded by the source corpus.

This paper considers the problem of secure data aggregation (mainly summation) in a distributed setting, while ensuring differential privacy of the result. We study secure multiparty addition protocols using well known security schemes: Shamir’s secret sharing, perturbation-based, and various encryptions. We supplement our study with our new enhanced encryption scheme EFT, which is efficient and fault tolerant.Differential privacy of the final result is achieved by either distributed Laplace or Geometric mechanism (respectively DLPA or DGPA), while approximated differential privacy is achieved by diluted mechanisms. Distributed random noise is generated collectively by all participants, which draw random variables from one of several distributions: Gamma, Gauss, Geometric, or their diluted versions. We introduce a new distributed privacy mechanism with noise drawn from the Laplace distribution, which achieves smaller redundant noise with efficiency. We compare complexity and security characteristics of the protocols with different differential privacy mechanisms and security schemes. More importantly, we implemented all protocols and present an experimental comparison on their performance and scalability in a real distributed environment. Based on the evaluations, we identify our security scheme and Laplace DLPA as the most efficient for secure distributed data aggregation with differential privacy.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Federated & Distributed Learning, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Federated & Distributed Learning

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “There is a rich literature exploring secure aggregation in both the single-server setting (via pairwise additive masking [12, 188, 73], via threshold homomorphic encryption [356, 193, 92], and via generic secure multi-party computation [86]) as well as in the multiple non-colluding servers setting [”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, methodology): “In DP, the Discrete Laplace distribution was observed to be infinitely divisible by Goryczka & Xiong (2015), and this property was used by Balle et al. (2020) for real summation in the shuffled model, albeit with several messages per user, each consisting of Ω(log n) bits.”
Private Summation in the Multi-Message Shuffle Model (2020, positive): “A discrete random variable with this property is provided in [16], where it is shown that a discrete Laplace random variable can be expressed as the sum of n diﬀerences of two P´olya random variables (the P´olya distribution is a generalization of the negative binomial distribution).”
Honeycrisp: large-scale differentially private aggregation without a trusted core (2019, methodology): “It uses pair-wise blinding to hide user inputs (as in [1, 38]), but does not focus on differential privacy.”
Differentially Private Summation with Multi-Message Shuffling (2019, methodology): “A discrete random variable with this property is provided in [5], where it is shown that a discrete Laplace random variable can be expressed as the sum of n differences of two Pólya random variables (the Pólya distribution is a generalization of the negative binomial distribution).”
Practical Secure Aggregation for Federated Learning on User-Held Data (2016, critical): “Pairwise blinding in a modulo addition-based encryption scheme has been explored, but existing schemes are neither efficient for vectors nor robust to even single failure [2, 12].”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “The resulting protocols can enable multiple parties to collaboratively compute an agreed-upon function without leaking input information from any party except for what can be inferred from the output [e.g., 23, 43, 95].”
A Survey on Federated Learning Systems: Vision, Hype and Reality for Data Privacy and Protection (2019, background): “other, and an FLS can adopt multiple methods to enhance the privacy guarantees [60], [78], [189].”
Differentially Private Distributed Online Learning (2018, background): “[30] studied existing SMC solutions with differential privacy in distributed setting and compared the complexities and security characteristics of them.”
Privacy and Robustness in Federated Learning: Attacks and Defenses (2020, background): “Besides, SMC-based protocols can enable multiple participants to collaboratively compute an agreed-upon function without leaking input information from any participant except for what can be inferred from the outcomes of the computation [101], [102].”
Practical Secure Aggregation for Privacy-Preserving Machine Learning (2017, methodology): “suggested by [18], are the most closely related to our scheme,”