Differentially Private Secure Multiplication: Hiding Information in the
  Rubble of Noise
Viveck R. Cadambe Ateet Devulapalli Haewon Jeong Flavio P. Calmon
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.