Our Data, Ourselves: Privacy via Distributed Noise Generation

Cynthia Dwork       Krishnaram Kenthapadi        Frank McSherry      Ilya Mironov        Moni Naor      


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 . Slides: ppt.

Back to On-Line Publications

Back Home