Efficient Noise Generation to Achieve Differential Privacy with Applications to Secure Multiparty Computation

This paper studies the problem of constructing secure multiparty computation protocols whose outputs satisfy differential privacy. We first provide a general framework for multiparty protocols generating shares of noise drawn from distributions capable of achieving differential privacy. Then, using this framework, we propose two kinds of protocols based on secret sharing. The first one is a constant-round protocol which enables parties to jointly generate shares of noise drawn from the discrete Laplace distribution. This protocol always outputs shares of noise while the previously known protocol fails with non-zero probability. The second protocol allows the parties to non-interactively obtain shares of noise following the binomial distribution by predistributing keys for pseudorandom functions in the setup phase. As a result, the parties can compute a share of noise enough to provide the computational analogue of ϵ -differential privacy with communication complexity independent of ϵ. It is much more efficient than the previous protocols which require communication complexity proportional to ϵ^{- 2} to achieve (information-theoretic) (ϵ, δ) -differential privacy for some δ> 0.