File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-642-33090-2_25
- Scopus: eid_2-s2.0-84866647559
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Optimal lower bound for differentially private multi-party aggregation
Title | Optimal lower bound for differentially private multi-party aggregation |
---|---|
Authors | |
Keywords | Additive errors Client-server communication Communication graphs Optimal lower bound Private data analysis |
Issue Date | 2012 |
Publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
Citation | The 20th Annual European Symposium on Algorithms (ESA 2012), Ljubljana, Slovenia, 10-12 September 2012. In Lecture Notes in Computer Science, 2012, v. 7501, p. 277-288 How to Cite? |
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 Ω(√n) 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 Ω(√n), 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 δ. © 2012 Springer-Verlag. |
Description | LNCS v. 7501 entitled: Algorithms - ESA 2012 : 20th annual European symposium ... proceedings |
Persistent Identifier | http://hdl.handle.net/10722/186488 |
ISBN | |
ISSN | 2020 SCImago Journal Rankings: 0.249 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, HTH | en_US |
dc.contributor.author | Shi, E | en_US |
dc.contributor.author | Song, D | en_US |
dc.date.accessioned | 2013-08-20T12:11:10Z | - |
dc.date.available | 2013-08-20T12:11:10Z | - |
dc.date.issued | 2012 | en_US |
dc.identifier.citation | The 20th Annual European Symposium on Algorithms (ESA 2012), Ljubljana, Slovenia, 10-12 September 2012. In Lecture Notes in Computer Science, 2012, v. 7501, p. 277-288 | en_US |
dc.identifier.isbn | 978-364233089-6 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | http://hdl.handle.net/10722/186488 | - |
dc.description | LNCS v. 7501 entitled: Algorithms - ESA 2012 : 20th annual European symposium ... proceedings | - |
dc.description.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 Ω(√n) 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 Ω(√n), 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 δ. © 2012 Springer-Verlag. | - |
dc.language | eng | en_US |
dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | - |
dc.relation.ispartof | Lecture Notes in Computer Science | en_US |
dc.rights | The original publication is available at www.springerlink.com | - |
dc.subject | Additive errors | - |
dc.subject | Client-server communication | - |
dc.subject | Communication graphs | - |
dc.subject | Optimal lower bound | - |
dc.subject | Private data analysis | - |
dc.title | Optimal lower bound for differentially private multi-party aggregation | en_US |
dc.type | Conference_Paper | en_US |
dc.identifier.email | Chan, HTH: hubert@cs.hku.hk | en_US |
dc.identifier.authority | Chan, HTH=rp01312 | en_US |
dc.description.nature | postprint | - |
dc.identifier.doi | 10.1007/978-3-642-33090-2_25 | - |
dc.identifier.scopus | eid_2-s2.0-84866647559 | - |
dc.identifier.hkuros | 219185 | en_US |
dc.identifier.volume | 7501 | - |
dc.identifier.spage | 277 | - |
dc.identifier.epage | 288 | - |
dc.publisher.place | Germany | - |
dc.customcontrol.immutable | sml 140415 | - |
dc.identifier.issnl | 0302-9743 | - |