Team for Research in
Ubiquitous Secure Technology

Citation
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. "Our Data, Ourselves: Privacy via Distributed Noise Generation". EUROCRYPT, May, 2006.

Abstract
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 recent papers [14, 4, 13]. 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. The computational power of even a simple form of these databases, when the query is just of the form Pi f(di), that is, the sum over all rows i in the database of a function f applied to the data in row i, has been demonstrated in [4]. 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.

Electronic downloads

• ourDataOurselves.pdf · application/pdf · 223 kbytes

• HTML

  Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya
  Mironov, and Moni Naor. <a
  href="http://www.truststc.org/pubs/101.html"
  >Our Data, Ourselves: Privacy via Distributed Noise
  Generation</a>, EUROCRYPT, May, 2006.

• Plain text

  Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya
  Mironov, and Moni Naor. "Our Data, Ourselves: Privacy
  via Distributed Noise Generation". EUROCRYPT, May, 2006.

• BibTeX

  @inproceedings{DworkKenthapadiMcSherryMironovNaor06_OurDataOurselvesPrivacyViaDistributedNoiseGeneration,
      author = {Cynthia Dwork, Krishnaram Kenthapadi, Frank
                McSherry, Ilya Mironov, and Moni Naor},
      title = {Our Data, Ourselves: Privacy via Distributed Noise
                Generation},
      booktitle = {EUROCRYPT},
      month = {May},
      year = {2006},
      abstract = {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 recent papers
                [14, 4, 13]. 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. The computational power of even a simple
                form of these databases, when the query is just of
                the form Pi f(di), that is, the sum over all rows
                i in the database of a function f applied to the
                data in row i, has been demonstrated in [4]. 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.},
      URL = {http://www.truststc.org/pubs/101.html}
  }
  

Posted by Dilys Thomas on 30 May 2006.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.