Team for Research in
Ubiquitous Secure Technology

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

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

Citation formats  
  • 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.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.