Optimal Lower Bound for Differentially Private Multi-party Aggregation View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2012

AUTHORS

T-H. Hubert Chan , Elaine Shi , Dawn Song

ABSTRACT

We consider distributed private data analysis, where n parties each holding some sensitive data wish to compute some aggregate statistics over all parties’ data. We prove a tight lower bound for the private distributed summation problem. Our lower bound is strictly stronger than the prior lower-bound result by Beimel, Nissim, and Omri published in CRYPTO 2008. In particular, we show that any n-party protocol computing the sum with sparse communication graph must incur an additive error of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\Omega(\sqrt{n})$\end{document} with constant probability, in order to defend against potential coalitions of compromised users. Furthermore, we show that in the client-server communication model, where all users communicate solely with an untrusted server, the additive error must be \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\Omega(\sqrt{n})$\end{document}, regardless of the number of messages or rounds. Both of our lower-bounds, for the general setting and the client-to-server communication model, are strictly stronger than those of Beimel, Nissim and Omri, since we remove the assumption on the number of rounds (and also the number of messages in the client-to-server communication model). Our lower bounds generalize to the (ε, δ) differential privacy notion, for reasonably small values of δ. More... »

PAGES

277-288

Book

TITLE

Algorithms – ESA 2012

ISBN

978-3-642-33089-6
978-3-642-33090-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-33090-2_25

DOI

http://dx.doi.org/10.1007/978-3-642-33090-2_25

DIMENSIONS

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


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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "The University of Hong Kong, Hong Kong", 
          "id": "http://www.grid.ac/institutes/grid.194645.b", 
          "name": [
            "The University of Hong Kong, Hong Kong"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chan", 
        "givenName": "T-H. Hubert", 
        "id": "sg:person.010251411300.37", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010251411300.37"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Maryland, College Park, USA", 
          "id": "http://www.grid.ac/institutes/grid.164295.d", 
          "name": [
            "University of Maryland, College Park, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shi", 
        "givenName": "Elaine", 
        "id": "sg:person.014706274717.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706274717.52"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "UC Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "UC Berkeley, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Song", 
        "givenName": "Dawn", 
        "id": "sg:person.01143152610.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01143152610.86"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2012", 
    "datePublishedReg": "2012-01-01", 
    "description": "We consider distributed private data analysis, where n parties each holding some sensitive data wish to compute some aggregate statistics over all parties\u2019 data. We prove a tight lower bound for the private distributed summation problem. Our lower bound is strictly stronger than the prior lower-bound result by Beimel, Nissim, and Omri published in CRYPTO 2008. In particular, we show that any n-party protocol computing the sum with sparse communication graph must incur an additive error of \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\Omega(\\sqrt{n})$\\end{document} with constant probability, in order to defend against potential coalitions of compromised users. Furthermore, we show that in the client-server communication model, where all users communicate solely with an untrusted server, the additive error must be \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\Omega(\\sqrt{n})$\\end{document}, regardless of the number of messages or rounds. Both of our lower-bounds, for the general setting and the client-to-server communication model, are strictly stronger than those of Beimel, Nissim and Omri, since we remove the assumption on the number of rounds (and also the number of messages in the client-to-server communication model). Our lower bounds generalize to the (\u03b5, \u03b4) differential privacy notion, for reasonably small values of \u03b4.", 
    "editor": [
      {
        "familyName": "Epstein", 
        "givenName": "Leah", 
        "type": "Person"
      }, 
      {
        "familyName": "Ferragina", 
        "givenName": "Paolo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-33090-2_25", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-33089-6", 
        "978-3-642-33090-2"
      ], 
      "name": "Algorithms \u2013 ESA 2012", 
      "type": "Book"
    }, 
    "keywords": [
      "client-server communication model", 
      "communication model", 
      "private data analysis", 
      "number of messages", 
      "sparse communication graph", 
      "untrusted server", 
      "privacy notion", 
      "number of rounds", 
      "CRYPTO 2008", 
      "communication graph", 
      "additive error", 
      "party protocol", 
      "summation problem", 
      "lower bounds", 
      "potential coalitions", 
      "users", 
      "aggregate statistics", 
      "Nissim", 
      "Beimel", 
      "optimal lower bounds", 
      "data analysis", 
      "server", 
      "general setting", 
      "error", 
      "graph", 
      "bounds", 
      "messages", 
      "constant probability", 
      "clients", 
      "protocol", 
      "parties", 
      "model", 
      "number", 
      "rounds", 
      "order", 
      "probability", 
      "notion", 
      "data", 
      "coalition", 
      "statistics", 
      "assumption", 
      "sum", 
      "aggregation", 
      "results", 
      "setting", 
      "OMRI", 
      "analysis", 
      "small values", 
      "values", 
      "wishes", 
      "problem", 
      "sensitive data wish", 
      "data wish", 
      "server communication model", 
      "differential privacy notion", 
      "Private Multi-party Aggregation", 
      "Multi-party Aggregation"
    ], 
    "name": "Optimal Lower Bound for Differentially Private Multi-party Aggregation", 
    "pagination": "277-288", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1012086337"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-33090-2_25"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-33090-2_25", 
      "https://app.dimensions.ai/details/publication/pub.1012086337"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T19:59", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_199.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-33090-2_25"
  }
]
 

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/978-3-642-33090-2_25'

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/978-3-642-33090-2_25'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-33090-2_25'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-33090-2_25'


 

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

142 TRIPLES      23 PREDICATES      83 URIs      76 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-33090-2_25 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N5e547e6f6fa84acdbea4956f131a958c
4 schema:datePublished 2012
5 schema:datePublishedReg 2012-01-01
6 schema:description We consider distributed private data analysis, where n parties each holding some sensitive data wish to compute some aggregate statistics over all parties’ data. We prove a tight lower bound for the private distributed summation problem. Our lower bound is strictly stronger than the prior lower-bound result by Beimel, Nissim, and Omri published in CRYPTO 2008. In particular, we show that any n-party protocol computing the sum with sparse communication graph must incur an additive error of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\Omega(\sqrt{n})$\end{document} with constant probability, in order to defend against potential coalitions of compromised users. Furthermore, we show that in the client-server communication model, where all users communicate solely with an untrusted server, the additive error must be \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\Omega(\sqrt{n})$\end{document}, regardless of the number of messages or rounds. Both of our lower-bounds, for the general setting and the client-to-server communication model, are strictly stronger than those of Beimel, Nissim and Omri, since we remove the assumption on the number of rounds (and also the number of messages in the client-to-server communication model). Our lower bounds generalize to the (ε, δ) differential privacy notion, for reasonably small values of δ.
7 schema:editor N41e2eecc93c94f3a915880cf45418ac7
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Ne74388f2ca304f1aa373697470af9700
12 schema:keywords Beimel
13 CRYPTO 2008
14 Multi-party Aggregation
15 Nissim
16 OMRI
17 Private Multi-party Aggregation
18 additive error
19 aggregate statistics
20 aggregation
21 analysis
22 assumption
23 bounds
24 client-server communication model
25 clients
26 coalition
27 communication graph
28 communication model
29 constant probability
30 data
31 data analysis
32 data wish
33 differential privacy notion
34 error
35 general setting
36 graph
37 lower bounds
38 messages
39 model
40 notion
41 number
42 number of messages
43 number of rounds
44 optimal lower bounds
45 order
46 parties
47 party protocol
48 potential coalitions
49 privacy notion
50 private data analysis
51 probability
52 problem
53 protocol
54 results
55 rounds
56 sensitive data wish
57 server
58 server communication model
59 setting
60 small values
61 sparse communication graph
62 statistics
63 sum
64 summation problem
65 untrusted server
66 users
67 values
68 wishes
69 schema:name Optimal Lower Bound for Differentially Private Multi-party Aggregation
70 schema:pagination 277-288
71 schema:productId N7225a4bc2e8742b49ebaad79248465be
72 Nbf57bdb596bd43a49028281ed1828944
73 schema:publisher N81e8daa8c47c49ac8c31ea4c25fe19ee
74 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012086337
75 https://doi.org/10.1007/978-3-642-33090-2_25
76 schema:sdDatePublished 2021-12-01T19:59
77 schema:sdLicense https://scigraph.springernature.com/explorer/license/
78 schema:sdPublisher Na2d102850fe44f0186e2631ed6438e5a
79 schema:url https://doi.org/10.1007/978-3-642-33090-2_25
80 sgo:license sg:explorer/license/
81 sgo:sdDataset chapters
82 rdf:type schema:Chapter
83 N163bbb85499f42699cd2cee323c5c131 schema:familyName Epstein
84 schema:givenName Leah
85 rdf:type schema:Person
86 N2c79bf76be494c80aeadb87ed75754d1 schema:familyName Ferragina
87 schema:givenName Paolo
88 rdf:type schema:Person
89 N41e2eecc93c94f3a915880cf45418ac7 rdf:first N163bbb85499f42699cd2cee323c5c131
90 rdf:rest N52c45c8211ef4107a7df66157c76b5c8
91 N46200e48184f44b7a9ab142877f0e022 rdf:first sg:person.01143152610.86
92 rdf:rest rdf:nil
93 N52c45c8211ef4107a7df66157c76b5c8 rdf:first N2c79bf76be494c80aeadb87ed75754d1
94 rdf:rest rdf:nil
95 N5e547e6f6fa84acdbea4956f131a958c rdf:first sg:person.010251411300.37
96 rdf:rest N710b315c45794259b62fbca588d89457
97 N710b315c45794259b62fbca588d89457 rdf:first sg:person.014706274717.52
98 rdf:rest N46200e48184f44b7a9ab142877f0e022
99 N7225a4bc2e8742b49ebaad79248465be schema:name dimensions_id
100 schema:value pub.1012086337
101 rdf:type schema:PropertyValue
102 N81e8daa8c47c49ac8c31ea4c25fe19ee schema:name Springer Nature
103 rdf:type schema:Organisation
104 Na2d102850fe44f0186e2631ed6438e5a schema:name Springer Nature - SN SciGraph project
105 rdf:type schema:Organization
106 Nbf57bdb596bd43a49028281ed1828944 schema:name doi
107 schema:value 10.1007/978-3-642-33090-2_25
108 rdf:type schema:PropertyValue
109 Ne74388f2ca304f1aa373697470af9700 schema:isbn 978-3-642-33089-6
110 978-3-642-33090-2
111 schema:name Algorithms – ESA 2012
112 rdf:type schema:Book
113 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
114 schema:name Information and Computing Sciences
115 rdf:type schema:DefinedTerm
116 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
117 schema:name Data Format
118 rdf:type schema:DefinedTerm
119 sg:person.010251411300.37 schema:affiliation grid-institutes:grid.194645.b
120 schema:familyName Chan
121 schema:givenName T-H. Hubert
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010251411300.37
123 rdf:type schema:Person
124 sg:person.01143152610.86 schema:affiliation grid-institutes:grid.47840.3f
125 schema:familyName Song
126 schema:givenName Dawn
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01143152610.86
128 rdf:type schema:Person
129 sg:person.014706274717.52 schema:affiliation grid-institutes:grid.164295.d
130 schema:familyName Shi
131 schema:givenName Elaine
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706274717.52
133 rdf:type schema:Person
134 grid-institutes:grid.164295.d schema:alternateName University of Maryland, College Park, USA
135 schema:name University of Maryland, College Park, USA
136 rdf:type schema:Organization
137 grid-institutes:grid.194645.b schema:alternateName The University of Hong Kong, Hong Kong
138 schema:name The University of Hong Kong, Hong Kong
139 rdf:type schema:Organization
140 grid-institutes:grid.47840.3f schema:alternateName UC Berkeley, USA
141 schema:name UC Berkeley, USA
142 rdf:type schema:Organization
 




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


...