Our Data, Ourselves: Privacy Via Distributed Noise Generation View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2006

AUTHORS

Cynthia Dwork , Krishnaram Kenthapadi , Frank McSherry , Ilya Mironov , Moni Naor

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 ∑if(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. More... »

PAGES

486-503

Book

TITLE

Advances in Cryptology - EUROCRYPT 2006

ISBN

978-3-540-34546-6
978-3-540-34547-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11761679_29

DOI

http://dx.doi.org/10.1007/11761679_29

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1011183161


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Microsoft Research, Silicon Valley Campus", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Microsoft Research, Silicon Valley Campus"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dwork", 
        "givenName": "Cynthia", 
        "id": "sg:person.016065712157.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016065712157.59"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Stanford University, USA", 
          "id": "http://www.grid.ac/institutes/grid.168010.e", 
          "name": [
            "Stanford University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kenthapadi", 
        "givenName": "Krishnaram", 
        "id": "sg:person.016621065061.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016621065061.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Microsoft Research, Silicon Valley Campus", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Microsoft Research, Silicon Valley Campus"
          ], 
          "type": "Organization"
        }, 
        "familyName": "McSherry", 
        "givenName": "Frank", 
        "id": "sg:person.016226764441.61", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016226764441.61"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Microsoft Research, Silicon Valley Campus", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Microsoft Research, Silicon Valley Campus"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mironov", 
        "givenName": "Ilya", 
        "id": "sg:person.07446432517.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07446432517.15"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Weizmann Institute of Science, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Weizmann Institute of Science, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Naor", 
        "givenName": "Moni", 
        "id": "sg:person.07776170271.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "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 \u2211if(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.", 
    "editor": [
      {
        "familyName": "Vaudenay", 
        "givenName": "Serge", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11761679_29", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-34546-6", 
        "978-3-540-34547-3"
      ], 
      "name": "Advances in Cryptology - EUROCRYPT 2006", 
      "type": "Book"
    }, 
    "keywords": [
      "verifiable secret sharing", 
      "database administrators", 
      "malicious participants", 
      "database queries", 
      "computational power", 
      "secret sharing", 
      "statistical databases", 
      "previous approaches", 
      "random noise", 
      "queries", 
      "shallow circuits", 
      "true answer", 
      "Gaussian noise", 
      "random bits", 
      "independent interest", 
      "database", 
      "implementation", 
      "bits", 
      "noise", 
      "privacy", 
      "execution", 
      "noise generation", 
      "sharing", 
      "unbiased random bits", 
      "row i", 
      "generation", 
      "protocol", 
      "biased coin", 
      "administrators", 
      "simple form", 
      "cost", 
      "data", 
      "technique", 
      "work", 
      "answers", 
      "coins", 
      "need", 
      "share", 
      "function f", 
      "power", 
      "interest", 
      "recent paper", 
      "exponential distribution", 
      "circuit", 
      "sum", 
      "vias", 
      "purpose", 
      "results", 
      "unbiased coin", 
      "amount", 
      "form", 
      "addition", 
      "small amount", 
      "distribution", 
      "biases", 
      "participants", 
      "bias", 
      "paper", 
      "approach", 
      "privacy-preserving statistical databases", 
      "appropriate biases", 
      "Privacy Via"
    ], 
    "name": "Our Data, Ourselves: Privacy Via Distributed Noise Generation", 
    "pagination": "486-503", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011183161"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11761679_29"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11761679_29", 
      "https://app.dimensions.ai/details/publication/pub.1011183161"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:16", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_282.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11761679_29"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/11761679_29'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/11761679_29'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11761679_29'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11761679_29'


 

This table displays all metadata directly associated to this object as RDF triples.

160 TRIPLES      23 PREDICATES      89 URIs      81 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11761679_29 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 anzsrc-for:0806
4 schema:author N9f58c762e2534babbe69048aa5f963fd
5 schema:datePublished 2006
6 schema:datePublishedReg 2006-01-01
7 schema:description 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 ∑if(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.
8 schema:editor Ne95ba0a4678047e48c5cb9547b8e3734
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree true
12 schema:isPartOf Nebf4711908064671ae549224f464af35
13 schema:keywords Gaussian noise
14 Privacy Via
15 addition
16 administrators
17 amount
18 answers
19 approach
20 appropriate biases
21 bias
22 biased coin
23 biases
24 bits
25 circuit
26 coins
27 computational power
28 cost
29 data
30 database
31 database administrators
32 database queries
33 distribution
34 execution
35 exponential distribution
36 form
37 function f
38 generation
39 implementation
40 independent interest
41 interest
42 malicious participants
43 need
44 noise
45 noise generation
46 paper
47 participants
48 power
49 previous approaches
50 privacy
51 privacy-preserving statistical databases
52 protocol
53 purpose
54 queries
55 random bits
56 random noise
57 recent paper
58 results
59 row i
60 secret sharing
61 shallow circuits
62 share
63 sharing
64 simple form
65 small amount
66 statistical databases
67 sum
68 technique
69 true answer
70 unbiased coin
71 unbiased random bits
72 verifiable secret sharing
73 vias
74 work
75 schema:name Our Data, Ourselves: Privacy Via Distributed Noise Generation
76 schema:pagination 486-503
77 schema:productId N7e0d6d6ce9f94f4baec3862a0e88fa5d
78 Nce2746e4ac1547de8e82a5a54850b3b7
79 schema:publisher N81b06c0d2d2640e5ac3af2370a316445
80 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011183161
81 https://doi.org/10.1007/11761679_29
82 schema:sdDatePublished 2022-01-01T19:16
83 schema:sdLicense https://scigraph.springernature.com/explorer/license/
84 schema:sdPublisher Nbda0d877f49a470fa8687506a7c94aaa
85 schema:url https://doi.org/10.1007/11761679_29
86 sgo:license sg:explorer/license/
87 sgo:sdDataset chapters
88 rdf:type schema:Chapter
89 N214d3aa8c2d542128e8f63da7f810807 rdf:first sg:person.07446432517.15
90 rdf:rest N2d69f554281541d2bacbdd6d3beca1ae
91 N2d69f554281541d2bacbdd6d3beca1ae rdf:first sg:person.07776170271.83
92 rdf:rest rdf:nil
93 N3544c5c9768e4869840d5cf9a0f9dd64 schema:familyName Vaudenay
94 schema:givenName Serge
95 rdf:type schema:Person
96 N7e0d6d6ce9f94f4baec3862a0e88fa5d schema:name dimensions_id
97 schema:value pub.1011183161
98 rdf:type schema:PropertyValue
99 N81b06c0d2d2640e5ac3af2370a316445 schema:name Springer Nature
100 rdf:type schema:Organisation
101 N9f58c762e2534babbe69048aa5f963fd rdf:first sg:person.016065712157.59
102 rdf:rest Nf4df832940f94a12bf2b5a0f91df2635
103 Nbda0d877f49a470fa8687506a7c94aaa schema:name Springer Nature - SN SciGraph project
104 rdf:type schema:Organization
105 Ncb28a7a8c65a4d12b341c5ce7a922c83 rdf:first sg:person.016226764441.61
106 rdf:rest N214d3aa8c2d542128e8f63da7f810807
107 Nce2746e4ac1547de8e82a5a54850b3b7 schema:name doi
108 schema:value 10.1007/11761679_29
109 rdf:type schema:PropertyValue
110 Ne95ba0a4678047e48c5cb9547b8e3734 rdf:first N3544c5c9768e4869840d5cf9a0f9dd64
111 rdf:rest rdf:nil
112 Nebf4711908064671ae549224f464af35 schema:isbn 978-3-540-34546-6
113 978-3-540-34547-3
114 schema:name Advances in Cryptology - EUROCRYPT 2006
115 rdf:type schema:Book
116 Nf4df832940f94a12bf2b5a0f91df2635 rdf:first sg:person.016621065061.62
117 rdf:rest Ncb28a7a8c65a4d12b341c5ce7a922c83
118 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
119 schema:name Information and Computing Sciences
120 rdf:type schema:DefinedTerm
121 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
122 schema:name Data Format
123 rdf:type schema:DefinedTerm
124 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
125 schema:name Information Systems
126 rdf:type schema:DefinedTerm
127 sg:person.016065712157.59 schema:affiliation grid-institutes:None
128 schema:familyName Dwork
129 schema:givenName Cynthia
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016065712157.59
131 rdf:type schema:Person
132 sg:person.016226764441.61 schema:affiliation grid-institutes:None
133 schema:familyName McSherry
134 schema:givenName Frank
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016226764441.61
136 rdf:type schema:Person
137 sg:person.016621065061.62 schema:affiliation grid-institutes:grid.168010.e
138 schema:familyName Kenthapadi
139 schema:givenName Krishnaram
140 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016621065061.62
141 rdf:type schema:Person
142 sg:person.07446432517.15 schema:affiliation grid-institutes:None
143 schema:familyName Mironov
144 schema:givenName Ilya
145 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07446432517.15
146 rdf:type schema:Person
147 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
148 schema:familyName Naor
149 schema:givenName Moni
150 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
151 rdf:type schema:Person
152 grid-institutes:None schema:alternateName Microsoft Research, Silicon Valley Campus
153 schema:name Microsoft Research, Silicon Valley Campus
154 rdf:type schema:Organization
155 grid-institutes:grid.13992.30 schema:alternateName Weizmann Institute of Science, Israel
156 schema:name Weizmann Institute of Science, Israel
157 rdf:type schema:Organization
158 grid-institutes:grid.168010.e schema:alternateName Stanford University, USA
159 schema:name Stanford University, USA
160 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...