Differentially Private Secure Multiplication: Hiding Information in the Rubble of Noise
This work addresses secure computation in adversarial settings where an honest majority is not available, offering a trade-off between privacy and accuracy for applications like federated learning or sensitive data processing.
The paper tackles the problem of private distributed multi-party multiplication by developing coding schemes that allow for a minority of honest nodes (N < 2t+1), using differential privacy to measure information leakage and mean squared error for accuracy, achieving a tight characterization of the privacy-accuracy trade-off.
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 \geq 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.