{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:53:47Z","timestamp":1775638427899,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T00:00:00Z","timestamp":1667779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"HKRGC","award":["16201819, 16205420, 16205422"],"award-info":[{"award-number":["16201819, 16205420, 16205422"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,11,7]]},"DOI":"10.1145\/3548606.3560608","type":"proceedings-article","created":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T11:41:28Z","timestamp":1667821288000},"page":"2219-2232","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Frequency Estimation in the Shuffle Model with Almost a Single Message"],"prefix":"10.1145","author":[{"given":"Qiyao","family":"Luo","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China, Hong Kong"}]},{"given":"Yilei","family":"Wang","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China, Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2022,11,7]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Apple Differential Privacy Team. [n.d.]. Apple Differential Privacy Technical Overview. https:\/\/www.apple.com\/privacy\/docs\/Differential_Privacy_Overview.pdf.  Apple Differential Privacy Team. [n.d.]. Apple Differential Privacy Technical Overview. https:\/\/www.apple.com\/privacy\/docs\/Differential_Privacy_Overview.pdf."},{"key":"e_1_3_2_1_2_1","volume-title":"1st Conference on Information-Theoretic Cryptography. 1:1--1: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. 1:1--1:14 . Victor Balcer and Albert Cheu. 2020. Separating Local & Shuffled Differential Privacy via Histograms. In 1st Conference on Information-Theoretic Cryptography. 1:1--1:14."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.142"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Borja Balle James Bell Adri\u00e0 Gasc\u00f3n and Kobbi Nissim. 2019. The Privacy Blanket of the Shuffle Model. In CRYPTO.  Borja Balle James Bell Adri\u00e0 Gasc\u00f3n and Kobbi Nissim. 2019. The Privacy Blanket of the Shuffle Model. In CRYPTO.","DOI":"10.1007\/978-3-030-26951-7_22"},{"key":"e_1_3_2_1_5_1","volume-title":"Private Summation in the Multi-Message Shuffle Model. In ACM SIGSAC Conference on Computer and Communications Security.","author":"Balle Borja","year":"2020","unstructured":"Borja Balle , James Bell , Adri\u00e0 Gasc\u00f3n , and Kobbi Nissim . 2020 . Private Summation in the Multi-Message Shuffle Model. In ACM SIGSAC Conference on Computer and Communications Security. Borja Balle, James Bell, Adri\u00e0 Gasc\u00f3n, and Kobbi Nissim. 2020. Private Summation in the Multi-Message Shuffle Model. In ACM SIGSAC Conference on Computer and Communications Security."},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 31st International Conference on Neural Information Processing Systems. 2285--2293","author":"Bassily Raef","year":"2017","unstructured":"Raef Bassily , Kobbi Nissim , Uri Stemmer , and Abhradeep Thakurta . 2017 . Practical Locally Private Heavy Hitters . In Proceedings of the 31st International Conference on Neural Information Processing Systems. 2285--2293 . Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Thakurta. 2017. Practical Locally Private Heavy Hitters. In Proceedings of the 31st International Conference on Neural Information Processing Systems. 2285--2293."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Raef Bassily and Adam Smith. 2015. Local private efficient protocols for succinct histograms. In ACM STOC. 127--135.  Raef Bassily and Adam Smith. 2015. Local private efficient protocols for succinct histograms. In ACM STOC. 127--135.","DOI":"10.1145\/2746539.2746632"},{"key":"e_1_3_2_1_8_1","volume-title":"On the Round Complexity of the Shuffle Model. In TCC 2020","author":"Beimel Amos","year":"2020","unstructured":"Amos Beimel , Iftach Haitner , Kobbi Nissim , and Uri Stemmer . 2020 . On the Round Complexity of the Shuffle Model. In TCC 2020 . https:\/\/arxiv.org\/abs\/2009.13510 Amos Beimel, Iftach Haitner, Kobbi Nissim, and Uri Stemmer. 2020. On the Round Complexity of the Shuffle Model. In TCC 2020. https:\/\/arxiv.org\/abs\/2009.13510"},{"key":"e_1_3_2_1_9_1","unstructured":"Sourav Biswas Yihe Dong Gautam Kamath and Jonathan Ullman. 2020. CoinPress: Practical Private Mean and Covariance Estimation. In Advances in Neural and Information Processing Systems.  Sourav Biswas Yihe Dong Gautam Kamath and Jonathan Ullman. 2020. CoinPress: Practical Private Mean and Covariance Estimation. In Advances in Neural and Information Processing Systems."},{"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.1145\/2840728.2840747"},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of the 20th Annual European Conference on Algorithms. 277--288","author":"Hubert Chan T-H.","year":"2012","unstructured":"T-H. Hubert Chan , Elaine Shi , and Dawn Song . 2012 . Optimal Lower Bound for Differentially Private Multi-Party Aggregation . In Proceedings of the 20th Annual European Conference on Algorithms. 277--288 . T-H. Hubert Chan, Elaine Shi, and Dawn Song. 2012. Optimal Lower Bound for Differentially Private Multi-Party Aggregation. In Proceedings of the 20th Annual European Conference on Algorithms. 277--288."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/358549.358563"},{"key":"e_1_3_2_1_14_1","first-page":"1","article-title":"On Distributed Differential Privacy and Counting Distinct Elements","volume":"56","author":"Chen Lijie","year":"2021","unstructured":"Lijie Chen , Badih Ghazi , Ravi Kumar , and Pasin Manurangsi . 2021 . On Distributed Differential Privacy and Counting Distinct Elements . In ITCS. 56 : 1 -- 56 :18. Lijie Chen, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. 2021. On Distributed Differential Privacy and Counting Distinct Elements. In ITCS. 56:1--56:18.","journal-title":"ITCS."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17653-2_13"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP46214.2022.9833614"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0172-z"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49896-5_15"},{"key":"e_1_3_2_1_19_1","volume-title":"Symposium on Security and Privacy. 2--15","author":"Danezis G.","unstructured":"G. Danezis , R. Dingledine , and N. Mathewson . 2003. Mixminion: design of a type III anonymous remailer protocol . In Symposium on Security and Privacy. 2--15 . G. Danezis, R. Dingledine, and N. Mathewson. 2003. Mixminion: design of a type III anonymous remailer protocol. In Symposium on Security and Privacy. 2--15."},{"key":"e_1_3_2_1_20_1","volume-title":"Tor: The Second-Generation Onion Router. In 13th USENIX Security Symposium (USENIX Security 04)","author":"Dingledine Roger","year":"2004","unstructured":"Roger Dingledine , Nick Mathewson , and Paul Syverson . 2004 . Tor: The Second-Generation Onion Router. In 13th USENIX Security Symposium (USENIX Security 04) . Roger Dingledine, Nick Mathewson, and Paul Syverson. 2004. Tor: The Second-Generation Onion Router. In 13th USENIX Security Symposium (USENIX Security 04)."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.151"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_3_2_1_23_1","volume-title":"Lossless Compression of Efficient Private Local Randomizers. In International Conference on Machine Learning.","author":"Feldman Vitaly","year":"2021","unstructured":"Vitaly Feldman and Kunal Talwar . 2021 . Lossless Compression of Efficient Private Local Randomizers. In International Conference on Machine Learning. Vitaly Feldman and Kunal Talwar. 2021. Lossless Compression of Efficient Private Local Randomizers. In International Conference on Machine Learning."},{"key":"e_1_3_2_1_24_1","unstructured":"Jen Fitzpatrick and Karen DeSalvo. [n.d.]. Helping public health officials combat COVID-19. https:\/\/blog.google\/technology\/health\/covid-19-community-mobility-reports\/.  Jen Fitzpatrick and Karen DeSalvo. [n.d.]. Helping public health officials combat COVID-19. https:\/\/blog.google\/technology\/health\/covid-19-community-mobility-reports\/."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-77883-5_16"},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning.","author":"Ghazi Badih","year":"2020","unstructured":"Badih Ghazi , Ravi Kumar , Pasin Manurangsi , and Rasmus Pagh . 2020 . Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead . In Proceedings of the 37th International Conference on Machine Learning. Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and Rasmus Pagh. 2020. Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead. In Proceedings of the 37th International Conference on Machine Learning."},{"key":"e_1_3_2_1_27_1","volume-title":"International Conference on Machine Learning.","author":"Ghazi Badih","year":"2021","unstructured":"Badih Ghazi , Ravi Kumar , Pasin Manurangsi , Rasmus Pagh , and Amer Sinha . 2021 b. Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message . In International Conference on Machine Learning. Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Amer Sinha. 2021b. Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message. In International Conference on Machine Learning."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134030"},{"key":"e_1_3_2_1_29_1","unstructured":"Ziyue Huang Yuting Liang and Ke Yi. 2021. Instance-optimal Mean Estimation Under Differential Privacy. In Advances in Neural Information Processing Systems.  Ziyue Huang Yuting Liang and Ke Yi. 2021. Instance-optimal Mean Estimation Under Differential Privacy. In Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Y. Ishai E. Kushilevitz R. Ostrovsky and A. Sahai. 2006. Cryptography from Anonymity. In FOCS.  Y. Ishai E. Kushilevitz R. Ostrovsky and A. Sahai. 2006. Cryptography from Anonymity. In FOCS.","DOI":"10.1109\/FOCS.2006.25"},{"key":"e_1_3_2_1_31_1","volume-title":"Secure multi-party differential privacy. Advances in neural information processing systems","author":"Kairouz Peter","year":"2015","unstructured":"Peter Kairouz , Sewoong Oh , and Pramod Viswanath . 2015. Secure multi-party differential privacy. Advances in neural information processing systems , Vol. 28 ( 2015 ). Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2015. Secure multi-party differential privacy. Advances in neural information processing systems, Vol. 28 (2015)."},{"key":"e_1_3_2_1_32_1","unstructured":"Andreas Kopp. [n.d.]. Microsoft SmartNoise Differential Privacy Machine Learning Case Studies. https:\/\/azure.microsoft.com\/en-in\/resources\/microsoft-smartnoisedifferential-privacy-machine-learning-case-studies\/.  Andreas Kopp. [n.d.]. Microsoft SmartNoise Differential Privacy Machine Learning Case Studies. https:\/\/azure.microsoft.com\/en-in\/resources\/microsoft-smartnoisedifferential-privacy-machine-learning-case-studies\/."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146847.1146848"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818000.2818027"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"M.G. Reed P.F. Syverson and D.M. Goldschlag. 1998. Anonymous connections and onion routing. IEEE Journal on Selected Areas in Communications (1998) 482--494.  M.G. Reed P.F. Syverson and D.M. Goldschlag. 1998. Anonymous connections and onion routing. IEEE Journal on Selected Areas in Communications (1998) 482--494.","DOI":"10.1109\/49.668972"},{"key":"e_1_3_2_1_36_1","volume-title":"Rubin","author":"Reiter Michael K.","year":"1998","unstructured":"Michael K. Reiter and Aviel D . Rubin . 1998 . Crowds : Anonymity for Web Transactions. ACM Transactions on Information and System Security ( 1998), 66--92. Michael K. Reiter and Aviel D. Rubin. 1998. Crowds: Anonymity for Web Transactions. ACM Transactions on Information and System Security (1998), 66--92."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3146549"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Salil Vadhan. 2017. The Complexity of Differential Privacy. 347--450.  Salil Vadhan. 2017. The Complexity of Differential Privacy. 347--450.","DOI":"10.1007\/978-3-319-57048-8_7"},{"key":"e_1_3_2_1_39_1","volume-title":"26th USENIX Security Symposium Security. 729--745","author":"Wang Tianhao","year":"2017","unstructured":"Tianhao Wang , Jeremiah Blocki , Ninghui Li , and Somesh Jha . 2017 . Locally differentially private protocols for frequency estimation . In 26th USENIX Security Symposium Security. 729--745 . Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. 2017. Locally differentially private protocols for frequency estimation. In 26th USENIX Security Symposium Security. 729--745."},{"key":"e_1_3_2_1_40_1","volume-title":"Locally Differentially Private Sparse Vector Aggregation. In 2022 IEEE Symposium on Security and Privacy (SP). 422--439","author":"Zhou Mingxun","year":"2022","unstructured":"Mingxun Zhou , Tianhao Wang , T-H. Hubert Chan , Giulia Fanti , and Elaine Shi . 2022 . Locally Differentially Private Sparse Vector Aggregation. In 2022 IEEE Symposium on Security and Privacy (SP). 422--439 . Mingxun Zhou, Tianhao Wang, T-H. Hubert Chan, Giulia Fanti, and Elaine Shi. 2022. Locally Differentially Private Sparse Vector Aggregation. In 2022 IEEE Symposium on Security and Privacy (SP). 422--439."},{"key":"e_1_3_2_1_41_1","volume-title":"Federated Heavy Hitters with Differential Privacy. In International Conference on Artificial Intelligence and Statistics (AISTATS)","author":"Zhu Wennan","year":"2020","unstructured":"Wennan Zhu , Peter Kairouz , Brendan McMahan , Haicheng Sun , and Vivian (Wei) Li . 2020 . Federated Heavy Hitters with Differential Privacy. In International Conference on Artificial Intelligence and Statistics (AISTATS) 2020. Wennan Zhu, Peter Kairouz, Brendan McMahan, Haicheng Sun, and Vivian (Wei) Li. 2020. Federated Heavy Hitters with Differential Privacy. In International Conference on Artificial Intelligence and Statistics (AISTATS) 2020."}],"event":{"name":"CCS '22: 2022 ACM SIGSAC Conference on Computer and Communications Security","location":"Los Angeles CA USA","acronym":"CCS '22","sponsor":["SIGSAC ACM Special Interest Group on Security, Audit, and Control"]},"container-title":["Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3548606.3560608","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3548606.3560608","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:58Z","timestamp":1750182538000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3548606.3560608"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,7]]},"references-count":41,"alternative-id":["10.1145\/3548606.3560608","10.1145\/3548606"],"URL":"https:\/\/doi.org\/10.1145\/3548606.3560608","relation":{},"subject":[],"published":{"date-parts":[[2022,11,7]]},"assertion":[{"value":"2022-11-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}