{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T09:17:15Z","timestamp":1780391835833,"version":"3.54.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"HKRGC","award":["16205422, 16204223, and 16203924"],"award-info":[{"award-number":["16205422, 16204223, and 16203924"]}]},{"name":"NTU-NAP startup grant","award":["024584-00001"],"award-info":[{"award-number":["024584-00001"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>Differential privacy (DP) is a leading standard for protecting individual privacy in data collection and analysis. This paper explores the shuffle model of DP, which balances privacy and utility by allowing users to send messages to a trusted shuffler before reaching an untrusted analyzer anonymously. We focus on efficiently implementing the matrix mechanism in shuffle-DP, where efficiency is defined by the number of messages each user sends. Our contributions include a baseline shuffle-DP mechanism that naively adapts the matrix mechanism, followed by an improved mechanism that reduces message complexity while maintaining error levels comparable to central-DP. We demonstrate the versatility of our approach across common query workloads, such as range queries and data cubes, achieving significant improvements in message efficiency. Experimental results confirm that our method outperforms the baseline solution while closely matching the accuracy of central-DP mechanisms.<\/jats:p>","DOI":"10.1145\/3725415","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-24","source":"Crossref","is-referenced-by-count":3,"title":["RM\n                    <sup>2<\/sup>\n                    : Answer Counting Queries Efficiently under Shuffle Differential Privacy"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4167-8670","authenticated-orcid":false,"given":"Qiyao","family":"Luo","sequence":"first","affiliation":[{"name":"OceanBase, Ant Group, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-1418-1728","authenticated-orcid":false,"given":"Jianzhe","family":"Yu","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0394-4125","authenticated-orcid":false,"given":"Wei","family":"Dong","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8989-9662","authenticated-orcid":false,"given":"Quanqing","family":"Xu","sequence":"additional","affiliation":[{"name":"OceanBase, Ant Group, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-3530-6476","authenticated-orcid":false,"given":"Chuanhui","family":"Yang","sequence":"additional","affiliation":[{"name":"OceanBase, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2178-3716","authenticated-orcid":false,"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2016. Netflix Prize dataset. https:\/\/archive.org\/download\/nf_prize_dataset.tar. Accessed: 2016-02-04."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3226070"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 32nd International Conference on Neural Information Processing Systems","author":"Agarwal Naman","year":"2018","unstructured":"Naman Agarwal, Ananda Theertha Suresh, Felix Yu, Sanjiv Kumar, and H. Brendan McMahan. 2018. cpSGD: communication-efficient and differentially-private distributed SGD. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, (Montr\u00e9al, Canada) (NIPS'18). Curran Associates Inc., Red Hook, NY, USA, 7575--7586."},{"key":"e_1_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.","DOI":"10.1007\/978-3-030-26951-7_22"},{"key":"e_1_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."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265569"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132769"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/358549.358563"},{"key":"e_1_2_1_10_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.","journal-title":"ITCS."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783379"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17653-2_13"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.24432\/C5VP42"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339496"},{"key":"e_1_2_1_15_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."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/3294996.3295115"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989347"},{"key":"e_1_2_1_18_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)."},{"key":"e_1_2_1_19_1","volume-title":"Our Data","author":"Dwork Cynthia","year":"2006","unstructured":"Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. 2006. Our Data, Ourselves: Privacy Via Distributed Noise Generation. In Advances in Cryptology - EUROCRYPT 2006, Serge Vaudenay, (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 486-503."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.21428\/2c646de5.7ec6ab93"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-030--77883--5_16"},{"key":"e_1_2_1_24_1","unstructured":"Badih Ghazi Pritish Kamath Ravi Kumar Pasin Manurangsi and Kewen Wu. 2022. On differentially private counting on trees. arXiv preprint arXiv:2212.11967 (2022)."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning, (ICML'20)","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, (ICML'20). JMLR.org, Article 328, 10 pages."},{"key":"e_1_2_1_26_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. 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_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.85"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920970"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.25"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807104"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168653"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0398-x"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560608"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146847.1146848"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556576"},{"key":"e_1_2_1_36_1","first-page":"482","volume-title":"IEEE Journal on Selected Areas in Communications","author":"Reed M.G.","year":"1998","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."},{"key":"e_1_2_1_37_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."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.3037971"},{"key":"e_1_2_1_39_1","first-page":"594","article-title":"Learning new words","volume":"9","author":"Thakurta Abhradeep Guha","year":"2017","unstructured":"Abhradeep Guha Thakurta, Andrew H Vyrros, Umesh S Vaishampayan, Gaurav Kapoor, Julien Freudiger, Vivek Rangarajan Sridhar, and Doug Davidson. 2017a. Learning new words. US Patent 9,594,741.","journal-title":"US Patent"},{"key":"e_1_2_1_40_1","first-page":"705","article-title":"Emoji frequency detection and deep link frequency","volume":"9","author":"Thakurta Abhradeep Guha","year":"2017","unstructured":"Abhradeep Guha Thakurta, Andrew H Vyrros, Umesh S Vaishampayan, Gaurav Kapoor, Julien Freudinger, Vipul Ved Prakash, Arnaud Legendre, and Steven Duplinsky. 2017b. Emoji frequency detection and deep link frequency. US Patent 9,705,908.","journal-title":"US Patent"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.247"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3430915.3430927"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3134428"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725415","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:58:30Z","timestamp":1774983510000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725415"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725415"],"URL":"https:\/\/doi.org\/10.1145\/3725415","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}