{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T03:31:20Z","timestamp":1648956680031},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","funder":[{"name":"This work was also supported in part through the Google Faculty Research Award."},{"name":"This work was partially funded by NSF grants #1740047 #2007714 and and UC-NL grant LFR-18-548554."}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,11,12]]},"DOI":"10.1145\/3460120.3484794","type":"proceedings-article","created":{"date-parts":[[2021,11,13]],"date-time":"2021-11-13T17:05:34Z","timestamp":1636823134000},"source":"Crossref","is-referenced-by-count":1,"title":["On the R\u00e9nyi Differential Privacy of the Shuffle Model"],"prefix":"10.1145","author":[{"given":"Antonious M.","family":"Girgis","sequence":"first","affiliation":[{"name":"University of California, Los Angeles, Los Angeles, CA, USA"}]},{"given":"Deepesh","family":"Data","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, Los Angeles, CA, USA"}]},{"given":"Suhas","family":"Diggavi","sequence":"additional","affiliation":[{"name":"University of California Los Angeles, Los Angeles, CA, USA"}]},{"given":"Ananda Theertha","family":"Suresh","sequence":"additional","affiliation":[{"name":"Google Research, New York, NY, USA"}]},{"given":"Peter","family":"Kairouz","sequence":"additional","affiliation":[{"name":"Google Research, San Francisco, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,11,13]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978318"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAIT.2021.3054692"},{"key":"e_1_3_2_1_3_1","volume-title":"1st Conference on Information-Theoretic Cryptography, ITC 2020","volume":"14","author":"Balcer Victor","year":"2020","unstructured":"Victor Balcer and Albert Cheu . 2020 . Separating Local & Shuffled Differential Privacy via Histograms . In 1st Conference on Information-Theoretic Cryptography, ITC 2020 , June 17 --19 , 2020, Boston, MA, USA (LIPIcs, Vol. 163), , Yael Tauman Kalai, Adam D. Smith, and Daniel Wichs (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 1:1--1: 14 . https:\/\/doi.org\/10.4230\/LIPIcs.ITC.2020.1 Victor Balcer and Albert Cheu. 2020. Separating Local & Shuffled Differential Privacy via Histograms. In 1st Conference on Information-Theoretic Cryptography, ITC 2020, June 17--19, 2020, Boston, MA, USA (LIPIcs, Vol. 163), , Yael Tauman Kalai, Adam D. Smith, and Daniel Wichs (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 1:1--1:14. https:\/\/doi.org\/10.4230\/LIPIcs.ITC.2020.1"},{"key":"e_1_3_2_1_4_1","volume-title":"Hypothesis Testing Interpretations and Renyi Differential Privacy. In International Conference on Artificial Intelligence and Statistics (AISTATS) (Proceedings of Machine Learning Research","volume":"2506","author":"Balle Borja","year":"2020","unstructured":"Borja Balle , Gilles Barthe , Marco Gaboardi , Justin Hsu , and Tetsuya Sato . 2020 a . Hypothesis Testing Interpretations and Renyi Differential Privacy. In International Conference on Artificial Intelligence and Statistics (AISTATS) (Proceedings of Machine Learning Research , Vol. 108), Silvia Chiappa and Roberto Calandra (Eds.). PMLR, 2496-- 2506 . Borja Balle, Gilles Barthe, Marco Gaboardi, Justin Hsu, and Tetsuya Sato. 2020 a. Hypothesis Testing Interpretations and Renyi Differential Privacy. In International Conference on Artificial Intelligence and Statistics (AISTATS) (Proceedings of Machine Learning Research, Vol. 108), Silvia Chiappa and Roberto Calandra (Eds.). PMLR, 2496--2506."},{"key":"e_1_3_2_1_5_1","volume-title":"Differentially private summation with multi-message shuffling. arXiv preprint arXiv:1906.09116","author":"Balle Borja","year":"2019","unstructured":"Borja Balle , James Bell , Adria Gascon , and Kobbi Nissim . 2019a. Differentially private summation with multi-message shuffling. arXiv preprint arXiv:1906.09116 ( 2019 ). Borja Balle, James Bell, Adria Gascon, and Kobbi Nissim. 2019a. Differentially private summation with multi-message shuffling. arXiv preprint arXiv:1906.09116 (2019)."},{"key":"e_1_3_2_1_6_1","volume-title":"Improved summation from shuffling. arXiv preprint arXiv:1909.11225","author":"Balle Borja","year":"2019","unstructured":"Borja Balle , James Bell , Adria Gasc\u00f3n , and Kobbi Nissim . 2019b. Improved summation from shuffling. arXiv preprint arXiv:1909.11225 ( 2019 ). Borja Balle, James Bell, Adria Gasc\u00f3n, and Kobbi Nissim. 2019b. Improved summation from shuffling. arXiv preprint arXiv:1909.11225 (2019)."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26951-7_22"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417242"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.56"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132769"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53641-4_24"},{"key":"e_1_3_2_1_12_1","volume-title":"The Discrete Gaussian for Differential Privacy. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Canonne Cl\u00e9","year":"2020","unstructured":"Cl\u00e9 ment L. Canonne , Gautam Kamath , and Thomas Steinke . 2020 . The Discrete Gaussian for Differential Privacy. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 , NeurIPS 2020, December 6--12, 2020, virtual, Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/b53b3a3d6ab90ce0268229151c9bde11-Abstract.html Cl\u00e9 ment L. Canonne, Gautam Kamath, and Thomas Steinke. 2020. The Discrete Gaussian for Differential Privacy. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6--12, 2020, virtual, Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/b53b3a3d6ab90ce0268229151c9bde11-Abstract.html"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17653-2_13"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3294996.3295115"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.53"},{"key":"e_1_3_2_1_16_1","volume-title":"Theory of Cryptography Conference (TCC). 265--284","author":"Dwork Cynthia","unstructured":"Cynthia Dwork , Frank McSherry , Kobbi Nissim , and Adam D. Smith . 2006. Calibrating Noise to Sensitivity in Private Data Analysis . In Theory of Cryptography Conference (TCC). 265--284 . Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. 2006. Calibrating Noise to Sensitivity in Private Data Analysis. In Theory of Cryptography Conference (TCC). 265--284."},{"key":"e_1_3_2_1_17_1","first-page":"3","article-title":"The algorithmic foundations of differential privacy","volume":"9","author":"Dwork Cynthia","year":"2014","unstructured":"Cynthia Dwork and Aaron Roth . 2014 . The algorithmic foundations of differential privacy . Foundations and Trends in Theoretical Computer Science , Vol. 9 , 3 -- 4 (2014), 211--407. Cynthia Dwork and Aaron Roth. 2014. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, Vol. 9, 3--4 (2014), 211--407.","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"e_1_3_2_1_18_1","volume-title":"Rothblum","author":"Dwork Cynthia","year":"2016","unstructured":"Cynthia Dwork and Guy N . Rothblum . 2016 . Concentrated Differential Privacy. CoRR , Vol. abs\/ 1603 .01887 (2016). arxiv: 1603.01887 http:\/\/arxiv.org\/abs\/1603.01887 Cynthia Dwork and Guy N. Rothblum. 2016. Concentrated Differential Privacy. CoRR , Vol. abs\/1603.01887 (2016). arxiv: 1603.01887 http:\/\/arxiv.org\/abs\/1603.01887"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.12"},{"key":"e_1_3_2_1_20_1","volume-title":"Analyze Privacy Revisited: Formalizations and Empirical Evaluation. CoRR","author":"Feldman Vitaly","year":"2020","unstructured":"\u00da lfar Erlingsson, Vitaly Feldman , Ilya Mironov , Ananth Raghunathan , Shuang Song , Kunal Talwar , and Abhradeep Thakurta . 2020. Encode, Shuffle , Analyze Privacy Revisited: Formalizations and Empirical Evaluation. CoRR , Vol. abs\/ 2001 .03618 ( 2020 ). https:\/\/arxiv.org\/abs\/2001.03618 \u00da lfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, and Abhradeep Thakurta. 2020. Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation. CoRR, Vol. abs\/2001.03618 (2020). https:\/\/arxiv.org\/abs\/2001.03618"},{"key":"e_1_3_2_1_21_1","volume-title":"Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity. arXiv preprint arXiv:1811.12469","author":"Erlingsson \u00dalfar","year":"2018","unstructured":"\u00dalfar Erlingsson , Vitaly Feldman , Ilya Mironov , Ananth Raghunathan , Kunal Talwar , and Abhradeep Thakurta . 2018. Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity. arXiv preprint arXiv:1811.12469 ( 2018 ). \u00dalfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. 2018. Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity. arXiv preprint arXiv:1811.12469 (2018)."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.151"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_3_2_1_24_1","volume-title":"Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling. arXiv preprint arXiv:2012.12803","author":"Feldman Vitaly","year":"2020","unstructured":"Vitaly Feldman , Audra McMillan , and Kunal Talwar . 2020. Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling. arXiv preprint arXiv:2012.12803 ( 2020 ). Open source implementation of privacy https:\/\/github.com\/apple\/ml-shuffling-amplification. Vitaly Feldman, Audra McMillan, and Kunal Talwar. 2020. Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling. arXiv preprint arXiv:2012.12803 (2020). Open source implementation of privacy https:\/\/github.com\/apple\/ml-shuffling-amplification."},{"key":"e_1_3_2_1_25_1","first-page":"1382","article-title":"On the Power of Multiple Anonymous Messages","volume":"2019","author":"Ghazi Badih","year":"2019","unstructured":"Badih Ghazi , Noah Golowich , Ravi Kumar , Rasmus Pagh , and Ameya Velingker . 2019 a. On the Power of Multiple Anonymous Messages . IACR Cryptol. ePrint Arch. , Vol. 2019 (2019), 1382 . Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker. 2019a. On the Power of Multiple Anonymous Messages. IACR Cryptol. ePrint Arch., Vol. 2019 (2019), 1382.","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_2_1_26_1","volume-title":"Scalable and differentially private distributed aggregation in the shuffled model. arXiv preprint arXiv:1906.08320","author":"Ghazi Badih","year":"2019","unstructured":"Badih Ghazi , Rasmus Pagh , and Ameya Velingker . 2019b. Scalable and differentially private distributed aggregation in the shuffled model. arXiv preprint arXiv:1906.08320 ( 2019 ). Badih Ghazi, Rasmus Pagh, and Ameya Velingker. 2019b. Scalable and differentially private distributed aggregation in the shuffled model. arXiv preprint arXiv:1906.08320 (2019)."},{"key":"e_1_3_2_1_27_1","volume-title":"Shuffled Model of Differential Privacy in Federated Learning. In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS (Proceedings of Machine Learning Research","volume":"2529","author":"Girgis Antonious","year":"2021","unstructured":"Antonious Girgis , Deepesh Data , Suhas N. Diggavi , Peter Kairouz , and Ananda Theertha Suresh . 2021 a. Shuffled Model of Differential Privacy in Federated Learning. In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS (Proceedings of Machine Learning Research , Vol. 130). PMLR , 2521-- 2529 . Antonious Girgis, Deepesh Data, Suhas N. Diggavi, Peter Kairouz, and Ananda Theertha Suresh. 2021a. Shuffled Model of Differential Privacy in Federated Learning. In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS (Proceedings of Machine Learning Research, Vol. 130). PMLR , 2521--2529."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAIT.2021.3056102"},{"key":"e_1_3_2_1_29_1","volume-title":"June","volume":"13","author":"Greenberg Andy","year":"2016","unstructured":"Andy Greenberg . 2016 . Apple's \"differential privacy'is about collecting your data-but not your data. Wired , June , Vol. 13 (2016). Andy Greenberg. 2016. Apple's \"differential privacy'is about collecting your data-but not your data. Wired, June , Vol. 13 (2016)."},{"key":"e_1_3_2_1_30_1","unstructured":"Peter Kairouz et al. 2019. Advances and Open Problems in Federated Learning. CoRR Vol. abs\/1912.04977 (2019). Peter Kairouz et al. 2019. Advances and Open Problems in Federated Learning. CoRR Vol. abs\/1912.04977 (2019)."},{"key":"e_1_3_2_1_31_1","volume-title":"International Conference on Machine Learning, ICML. 2436--2444","author":"Kairouz Peter","year":"2016","unstructured":"Peter Kairouz , Keith Bonawitz , and Daniel Ramage . 2016 . Discrete Distribution Estimation under Local Privacy . In International Conference on Machine Learning, ICML. 2436--2444 . Peter Kairouz, Keith Bonawitz, and Daniel Ramage. 2016. Discrete Distribution Estimation under Local Privacy. In International Conference on Machine Learning, ICML. 2436--2444."},{"key":"e_1_3_2_1_32_1","volume-title":"The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation. CoRR","author":"Kairouz Peter","year":"2021","unstructured":"Peter Kairouz , Ziyu Liu , and Thomas Steinke . 2021. The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation. CoRR , Vol. abs\/ 2102 .06387 ( 2021 ). arxiv: 2102.06387 https:\/\/arxiv.org\/abs\/2102.06387 Peter Kairouz, Ziyu Liu, and Thomas Steinke. 2021. The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation. CoRR , Vol. abs\/2102.06387 (2021). arxiv: 2102.06387 https:\/\/arxiv.org\/abs\/2102.06387"},{"key":"e_1_3_2_1_33_1","volume-title":"International conference on machine learning. PMLR, 1376--1385","author":"Kairouz Peter","year":"2015","unstructured":"Peter Kairouz , Sewoong Oh , and Pramod Viswanath . 2015 . The composition theorem for differential privacy . In International conference on machine learning. PMLR, 1376--1385 . Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2015. The composition theorem for differential privacy. In International conference on machine learning. PMLR, 1376--1385."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2414456.2414474"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSF.2017.11"},{"key":"e_1_3_2_1_37_1","volume-title":"Renyi Differential Privacy of the Sampled Gaussian Mechanism. arXiv preprint arXiv:1908.10530","author":"Mironov Ilya","year":"2019","unstructured":"Ilya Mironov , Kunal Talwar , and Li Zhang . 2019. Renyi Differential Privacy of the Sampled Gaussian Mechanism. arXiv preprint arXiv:1908.10530 ( 2019 ). Ilya Mironov, Kunal Talwar, and Li Zhang. 2019. Renyi Differential Privacy of the Sampled Gaussian Mechanism. arXiv preprint arXiv:1908.10530 (2019)."},{"key":"e_1_3_2_1_38_1","volume-title":"High dimensional statistics. Lecture notes for course 18S997","author":"Rigollet Phillippe","year":"2015","unstructured":"Phillippe Rigollet and Jan-Christian H\u00fctter . 2015. High dimensional statistics. Lecture notes for course 18S997 , Vol. 813 ( 2015 ), 814. Phillippe Rigollet and Jan-Christian H\u00fctter. 2015. High dimensional statistics. Lecture notes for course 18S997, Vol. 813 (2015), 814."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2320500"},{"key":"e_1_3_2_1_40_1","volume-title":"The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 1226--1235","author":"Wang Yu-Xiang","year":"2019","unstructured":"Yu-Xiang Wang , Borja Balle , and Shiva Prasad Kasiviswanathan . 2019 . Subsampled R\u00e9nyi differential privacy and analytical moments accountant . In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 1226--1235 . Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. 2019. Subsampled R\u00e9nyi differential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 1226--1235."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1965.10480775"},{"key":"e_1_3_2_1_42_1","unstructured":"Wikipedia. [n.d.]. Gamma function. https:\/\/en.wikipedia.org\/wiki\/Gamma_function. Wikipedia. [n.d.]. Gamma function. https:\/\/en.wikipedia.org\/wiki\/Gamma_function."},{"key":"e_1_3_2_1_43_1","volume-title":"International Conference on Machine Learning. PMLR, 7634--7642","author":"Zhu Yuqing","year":"2019","unstructured":"Yuqing Zhu and Yu-Xiang Wang . 2019 . Poission subsampled r\u00e9nyi differential privacy . In International Conference on Machine Learning. PMLR, 7634--7642 . Yuqing Zhu and Yu-Xiang Wang. 2019. Poission subsampled r\u00e9nyi differential privacy. In International Conference on Machine Learning. PMLR, 7634--7642."}],"event":{"name":"CCS '21: 2021 ACM SIGSAC Conference on Computer and Communications Security","location":"Virtual Event Republic of Korea","acronym":"CCS '21","sponsor":["SIGSAC ACM Special Interest Group on Security, Audit, and Control"]},"container-title":["Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460120.3484794","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T02:15:21Z","timestamp":1646792121000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460120.3484794"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,12]]},"references-count":43,"alternative-id":["10.1145\/3460120.3484794","10.1145\/3460120"],"URL":"http:\/\/dx.doi.org\/10.1145\/3460120.3484794","relation":{},"published":{"date-parts":[[2021,11,12]]}}}