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": "2022-01-01T19:27", 
    "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_71.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 Nb88a875b98f94edda3df2bc360cfdc98
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 Nbc77f02a289a4f0d931f523eebb38319
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N62bb622b5a1044b18506a90a193d4a55
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 N247b7623114047b3ae846e55d40730cf
72 N6ba09c4839df4969b6e6293a6d130fa3
73 schema:publisher N09794f5860a64d8a87eb6202940936c2
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 2022-01-01T19:27
77 schema:sdLicense https://scigraph.springernature.com/explorer/license/
78 schema:sdPublisher Nb149b0fab6a541d5974d4a6a9a2747ce
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 N09794f5860a64d8a87eb6202940936c2 schema:name Springer Nature
84 rdf:type schema:Organisation
85 N247b7623114047b3ae846e55d40730cf schema:name doi
86 schema:value 10.1007/978-3-642-33090-2_25
87 rdf:type schema:PropertyValue
88 N62bb622b5a1044b18506a90a193d4a55 schema:isbn 978-3-642-33089-6
89 978-3-642-33090-2
90 schema:name Algorithms – ESA 2012
91 rdf:type schema:Book
92 N6ba09c4839df4969b6e6293a6d130fa3 schema:name dimensions_id
93 schema:value pub.1012086337
94 rdf:type schema:PropertyValue
95 N96d1a5e89f3a43ad83a82ec4c50c6b96 schema:familyName Epstein
96 schema:givenName Leah
97 rdf:type schema:Person
98 Na70b8b204f4f4f81b3ff806bf0b13496 schema:familyName Ferragina
99 schema:givenName Paolo
100 rdf:type schema:Person
101 Naf13e29451634e7abaca26021766fe63 rdf:first sg:person.01143152610.86
102 rdf:rest rdf:nil
103 Nb149b0fab6a541d5974d4a6a9a2747ce schema:name Springer Nature - SN SciGraph project
104 rdf:type schema:Organization
105 Nb88a875b98f94edda3df2bc360cfdc98 rdf:first sg:person.010251411300.37
106 rdf:rest Nda62340448ae471a864e63fd54e4a104
107 Nbc77f02a289a4f0d931f523eebb38319 rdf:first N96d1a5e89f3a43ad83a82ec4c50c6b96
108 rdf:rest Nc976348bae0747ccbd14927c74aab90d
109 Nc976348bae0747ccbd14927c74aab90d rdf:first Na70b8b204f4f4f81b3ff806bf0b13496
110 rdf:rest rdf:nil
111 Nda62340448ae471a864e63fd54e4a104 rdf:first sg:person.014706274717.52
112 rdf:rest Naf13e29451634e7abaca26021766fe63
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)


...