Differentially Private Secure Multiplication: Hiding Information in the Rubble of Noise
Not on the map. Why?
Abstract (arXiv)
We consider the problem of private distributed multi-party multiplication. It is well-established that Shamir secret-sharing coding strategies can enable perfect information-theoretic privacy in distributed computation via the celebrated algorithm of Ben Or, Goldwasser and Wigderson (the "BGW algorithm"). However, perfect privacy and accuracy require an honest majority, that is, N ≥ 2t+1 compute nodes are required to ensure privacy against any t colluding adversarial nodes. By allowing for some controlled amount of information leakage and approximate multiplication instead of exact multiplication, we study coding schemes for the setting where the number of honest nodes can be a minority, that is N< 2t+1. We develop a tight characterization privacy-accuracy trade-off for cases where N < 2t+1 by measuring information leakage using differential privacy instead of perfect privacy, and using the mean squared error metric for accuracy. A novel technical aspect is an intricately layered noise distribution that merges ideas from differential privacy and Shamir secret-sharing at different layers.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 13 of its 42 references that are in the map. First posted on arXiv 28 Sep 2023.
Builds on
13 of 42 references.
References · 13
- 2019Federated Learning with Differential Privacy: Algorithms and Performance Analysiscited by 536
- 2020LDP-Fed: Federated Learning with Local Differential Privacycited by 132
- 2018A General Approach to Adding Differential Privacy to Iterative Training Procedurescited by 84
- 2018Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacycited by 66
- 2017The Price of Differential Privacy For Online Learningcited by 45
- 2021Efficient Differentially Private Secure Aggregation for Federated Learning via Hardness of Learning with Errorscited by 25
- 2021Local Differential Privacy Is Equivalent to Contraction of Eγ-Divergencecited by 17
- 2020Analog Lagrange Coded Computingcited by 13
- 2018On the Capacity of Secure Distributed Matrix Multiplicationcited by 5
- 2022Differential Secrecy for Distributed Data and Applications to Robust Differentially Secure Vector Summationcited by 5
- 2017Composing Differential Privacy and Secure Computation: A case study on scaling private record linkagecited by 3
- 2014Differentially Private Multi-party Computation: Optimality of Non-Interactive Randomized Responsecited by 2
Built on by
Not cited yet.