  How to achieve differential privacy in the distributed setting, where the
dataset is distributed among the distrustful parties, is an important problem.
We consider in what condition can a protocol inherit the differential privacy
property of a function it computes. The heart of the problem is the secure
multiparty computation of randomized function. A notion \emph{obliviousness} is
introduced, which captures the key security problems when computing a
randomized function from a deterministic one in the distributed setting. By
this observation, a sufficient and necessary condition about computing a
randomized function from a deterministic one is given. The above result can not
only be used to determine whether a protocol computing differentially private
function is secure, but also be used to construct secure one. Then we prove
that the differential privacy property of a function can be inherited by the
protocol computing it if the protocol privately computes it. A composition
theorem of differentially private protocols is also presented. We also
construct some protocols to generate random variate in the distributed setting,
such as the uniform random variates and the inversion method. By using these
fundamental protocols, we construct protocols of the Gaussian mechanism, the
Laplace mechanism and the Exponential mechanism. Importantly, all these
protocols satisfy obliviousness and so can be proved to be secure in a
simulation based manner. We also provide a complexity bound of computing
randomized function in the distribute setting. Finally, to show that our
results are fundamental and powerful to multiparty differential privacy, we
construct a differentially private empirical risk minimization protocol.

Cryptography and Security;Databases