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.
The paper:
Postscript , gzipped Postscript , PDF