We provide methods
In this work we provide efficient distributed protocols for generating
shares of random noise, secure against malicious participants. The
purpose of the noise generation is to create a distributed
implementation of the privacy-preserving statistical databases
described in some recent papers. In these databases, privacy is
obtained by perturbing the true answer to a database query by the
addition of a small amount of Gaussian or exponentially distributed
random noise. A distributed implementation eliminates the need
for a trusted database administrator.
The results for noise generation are of independent interest. The generation of Gaussian noise introduces a technique for distributing shares of many unbiased coins with fewer executions of verifiable secret sharing than would be needed using previous approaches (reduced by a factor of n). The generation of exponentially distributed noise uses two shallow circuits: one for generating many arbitrarily but identically biased coins at an amortized cost of two unbiased random bits apiece, independent of the bias, and the other to combine bits of appropriate biases to obtain an exponential distribution.