{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T09:26:35Z","timestamp":1769073995888,"version":"3.49.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,10,31]],"date-time":"2017-10-31T00:00:00Z","timestamp":1509408000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong RGC","award":["HKU719312E"],"award-info":[{"award-number":["HKU719312E"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>We consider a distributed private data analysis setting, where multiple parties each hold some sensitive data and they wish to run a protocol to learn some aggregate statistics over the distributed dataset, while protecting each user\u2019s privacy. As an initial effort, we consider a distributed summation problem. We first show a lower bound, that is, under information-theoretic differential privacy, any multi-party protocol with a small number of messages must have large additive error. We then show that by adopting a computational differential privacy notion, one can circumvent this lower bound and design practical protocols for the periodic distributed summation problem. Our construction has several desirable features. First, it works in the client-server model and requires no peer-to-peer communication among the clients. Second, our protocol is fault tolerant and can output meaningful statistics even when a subset of the participants fail to respond. Our constructions guarantee the privacy of honest parties even when a fraction of the participants may be compromised and colluding. In addition, we propose a new distributed noise addition mechanism that guarantees small total error.<\/jats:p>","DOI":"10.1145\/3146549","type":"journal-article","created":{"date-parts":[[2017,12,21]],"date-time":"2017-12-21T16:58:29Z","timestamp":1513875509000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Distributed Private Data Analysis"],"prefix":"10.1145","volume":"13","author":[{"given":"Elaine","family":"Shi","sequence":"first","affiliation":[{"name":"Cornell University, NY, USA"}]},{"given":"T.-H. Hubert","family":"Chan","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Pokfulam Road, Hong Kong"}]},{"given":"Eleanor","family":"Rieffel","sequence":"additional","affiliation":[{"name":"NASA Ames Research Center, CA, USA"}]},{"given":"Dawn","family":"Song","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2017,12,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85174-5_25"},{"key":"e_1_2_1_2_1","volume-title":"Bernstein and Tanja Lange (editors","author":"Daniel","year":"2011","unstructured":"Daniel J. Bernstein and Tanja Lange (editors ). eBACS: ECRYPT Benchmarking of Cryptographic Systems. Retreived March 7, 2011 from http:\/\/bench.cr.yp.to. Daniel J. Bernstein and Tanja Lange (editors). eBACS: ECRYPT Benchmarking of Cryptographic Systems. Retreived March 7, 2011 from http:\/\/bench.cr.yp.to."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374464"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30576-7_18"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46803-6_19"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49896-5_30"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1525856.1525858"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043621.2043626"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_25"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"T.-H. Hubert Chan Elaine Shi and Dawn Song. 2012. Privacy-preserving stream aggregation with fault tolerance. In Financial Cryptography. 200--214.  T.-H. Hubert Chan Elaine Shi and Dawn Song. 2012. Privacy-preserving stream aggregation with fault tolerance. In Financial Cryptography. 200--214.","DOI":"10.1007\/978-3-642-32946-3_15"},{"key":"e_1_2_1_11_1","article-title":"Differentially private empirical risk minimization","author":"Chaudhuri Kamalika","year":"2011","unstructured":"Kamalika Chaudhuri , Claire Monteleoni , and Anand D. Sarwate . 2011 . Differentially private empirical risk minimization . Journal of Machine Learning Research 12 ( July 2011), 1069--1109. http:\/\/dl.acm.org\/citation.cfm?id&equals;2021036. Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. 2011. Differentially private empirical risk minimization. Journal of Machine Learning Research 12 (July 2011), 1069--1109. http:\/\/dl.acm.org\/citation.cfm?id&equals;2021036.","journal-title":"Journal of Machine Learning Research 12"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90120-X"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the Conference and Workshop on Neural Information Processing Systems (NIPS\u201912)","author":"Duchi John C.","unstructured":"John C. Duchi , Michael I. Jordan , and Martin J. Wainwright . 2012. Privacy aware learning . In Proceedings of the Conference and Workshop on Neural Information Processing Systems (NIPS\u201912) . 1439--1447. John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. 2012. Privacy aware learning. In Proceedings of the Conference and Workshop on Neural Information Processing Systems (NIPS\u201912). 1439--1447."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1866739.1866758"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_29"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806787"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.12"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536440"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536464"},{"key":"e_1_2_1_23_1","unstructured":"Oded Goldreich. Secure Multi-Party Computation. Retrieved from http:\/\/www.wisdom.weizmann.ac.il\/&sim;oded\/PS\/prot.ps.  Oded Goldreich. Secure Multi-Party Computation. Retrieved from http:\/\/www.wisdom.weizmann.ac.il\/&sim;oded\/PS\/prot.ps."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Shafi Goldwasser S. Dov Gordon Vipul Goyal Abhishek Jain Jonathan Katz Feng-Hao Liu Amit Sahai Elaine Shi and Hong-Sheng Zhou. 2014. Multi-input functional encryption. In Eurocrypt.  Shafi Goldwasser S. Dov Gordon Vipul Goyal Abhishek Jain Jonathan Katz Feng-Hao Liu Amit Sahai Elaine Shi and Hong-Sheng Zhou. 2014. Multi-input functional encryption. In Eurocrypt.","DOI":"10.1007\/978-3-642-55220-5_32"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033036.2033047"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.85"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2009.06.003"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.14"},{"key":"e_1_2_1_29_1","unstructured":"J. Menezes P. C. Van Oorschot and S. A. Vanstone. 1997. Handbook of Applied Cryptography. CRC Press Boca Raton FL (1997).   J. Menezes P. C. Van Oorschot and S. A. Vanstone. 1997. Handbook of Applied Cryptography. CRC Press Boca Raton FL (1997)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.43"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03356-8_8"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958521"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807247"},{"key":"e_1_2_1_35_1","volume-title":"International Conference on Collaboration Technologies and Systems (CTS\u201911)","author":"Rieffel Eleanor","unstructured":"Eleanor Rieffel , Jacob Biehl , Bill van Melle , and Adam J. Lee . 2011. Secured histories for presence systems . In International Conference on Collaboration Technologies and Systems (CTS\u201911) , 446--456. Eleanor Rieffel, Jacob Biehl, Bill van Melle, and Adam J. Lee. 2011. Secured histories for presence systems. In International Conference on Collaboration Technologies and Systems (CTS\u201911), 446--456."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806794"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the Network and Distributed System Security Symposium (NDSS\u201911)","author":"Shi Elaine","year":"2011","unstructured":"Elaine Shi , T.-H. Hubert Chan , Eleanor G. Rieffel , Richard Chow , and Dawn Song . 2011 . Privacy-preserving aggregation of time-series data . In Proceedings of the Network and Distributed System Security Symposium (NDSS\u201911) . Elaine Shi, T.-H. Hubert Chan, Eleanor G. Rieffel, Richard Chow, and Dawn Song. 2011. Privacy-preserving aggregation of time-series data. In Proceedings of the Network and Distributed System Security Symposium (NDSS\u201911)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993743"},{"key":"e_1_2_1_39_1","volume-title":"Wright","author":"Yang Zhiqiang","year":"2005","unstructured":"Zhiqiang Yang , Sheng Zhong , and Rebecca N . Wright . 2005 . Privacy-preserving classification of customer data without loss of accuracy. In Proceedings of the SIAM International Conference on Date Mining (SDM\u201905). Zhiqiang Yang, Sheng Zhong, and Rebecca N. Wright. 2005. Privacy-preserving classification of customer data without loss of accuracy. In Proceedings of the SIAM International Conference on Date Mining (SDM\u201905)."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3146549","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3146549","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:13:33Z","timestamp":1750212813000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3146549"}},"subtitle":["Lower Bounds and Practical Constructions"],"short-title":[],"issued":{"date-parts":[[2017,10,31]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3146549"],"URL":"https:\/\/doi.org\/10.1145\/3146549","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,31]]},"assertion":[{"value":"2016-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}