File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Optimal lower bound for differentially private multi-party aggregation

TitleOptimal lower bound for differentially private multi-party aggregation
Authors
KeywordsAdditive errors
Client-server communication
Communication graphs
Optimal lower bound
Private data analysis
Issue Date2012
PublisherSpringer 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?
AbstractWe 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.
DescriptionLNCS v. 7501 entitled: Algorithms - ESA 2012 : 20th annual European symposium ... proceedings
Persistent Identifierhttp://hdl.handle.net/10722/186488
ISBN
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252

 

DC FieldValueLanguage
dc.contributor.authorChan, HTHen_US
dc.contributor.authorShi, Een_US
dc.contributor.authorSong, Den_US
dc.date.accessioned2013-08-20T12:11:10Z-
dc.date.available2013-08-20T12:11:10Z-
dc.date.issued2012en_US
dc.identifier.citationThe 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-288en_US
dc.identifier.isbn978-364233089-6-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/186488-
dc.descriptionLNCS v. 7501 entitled: Algorithms - ESA 2012 : 20th annual European symposium ... proceedings-
dc.description.abstractWe 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.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.rightsThe original publication is available at www.springerlink.com-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectAdditive errors-
dc.subjectClient-server communication-
dc.subjectCommunication graphs-
dc.subjectOptimal lower bound-
dc.subjectPrivate data analysis-
dc.titleOptimal lower bound for differentially private multi-party aggregationen_US
dc.typeConference_Paperen_US
dc.identifier.emailChan, HTH: hubert@cs.hku.hken_US
dc.identifier.authorityChan, HTH=rp01312en_US
dc.description.naturepostprint-
dc.identifier.doi10.1007/978-3-642-33090-2_25-
dc.identifier.scopuseid_2-s2.0-84866647559-
dc.identifier.hkuros219185en_US
dc.identifier.volume7501-
dc.identifier.spage277-
dc.identifier.epage288-
dc.publisher.placeGermany-
dc.customcontrol.immutablesml 140415-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats