{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:55:02Z","timestamp":1775595302045,"version":"3.50.1"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,4,2]]},"abstract":"<jats:p>Differential Privacy (DP) has become the gold standard for protecting individual privacy in data analytics, and the shuffle-DP model has attracted significant attention from both academia and industry due to its favorable balance between privacy and utility. However, existing shuffle-DP protocols rely on a strong assumption: all users behave honestly. In real-world scenarios, adversarial users can exploit this vulnerability through poisoning attacks, compromising both privacy guarantees and the utility of analytical results. While defending against poisoning attacks in the shuffle-DP model has recently gained interest, existing solutions are limited to frequency estimation tasks. To address this issue, we propose the first general defense framework for all union-preserving queries, capable of transforming any shuffle-DP protocol into a version resilient to poisoning attacks. Beyond robust defense against poisoning attacks, our framework achieves high utility of analytical results. Compared to the original shuffle-DP protocol, it retains asymptotically equivalent error in attack-free settings and incurs only a polylogarithmic increase in error when a constant number of attackers are present. We demonstrate the generality of our framework on several common queries, including summation, frequency estimation, and range counting. Experimental results confirm that our approach effectively defends against poisoning attacks while maintaining strong utility and communication efficiency.<\/jats:p>","DOI":"10.1145\/3786638","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:54:13Z","timestamp":1775584453000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["Defense against Poisoning Attacks under Shuffle-DP"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-1853-9028","authenticated-orcid":false,"given":"Siyi","family":"Wang","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4167-8670","authenticated-orcid":false,"given":"Qiyao","family":"Luo","sequence":"additional","affiliation":[{"name":"OceanBase, Ant Group, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-2948-8340","authenticated-orcid":false,"given":"Yihua","family":"Hu","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2518-4160","authenticated-orcid":false,"given":"Lixu","family":"Wang","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-3530-6476","authenticated-orcid":false,"given":"Chuanhui","family":"Yang","sequence":"additional","affiliation":[{"name":"OceanBase, Ant Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7872-6969","authenticated-orcid":false,"given":"Zhan","family":"Qin","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1969-2591","authenticated-orcid":false,"given":"Kui","family":"Ren","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.142"},{"key":"e_1_2_1_2_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_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417242"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 2006 ACM Symposium on Information, Computer and Communications Security. 16\u201325","author":"Barreno Marco","unstructured":"Marco Barreno, Blaine Nelson, Russell Sears, Anthony D. Joseph, and J. D. Tygar. 2006. Can machine learning be secure?. In Proceedings of the 2006 ACM Symposium on Information, Computer and Communications Security. 16\u201325."},{"key":"e_1_2_1_5_1","first-page":"451","volume-title":"USA","author":"Beimel Amos","year":"2008","unstructured":"Amos Beimel, Kobbi Nissim, and Eran Omri. 2008. Distributed private data analysis: Simultaneously solving how and what. In Advances in Cryptology-CRYPTO 2008: 28th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2008. Proceedings 28. Springer, 451-468."},{"key":"e_1_2_1_6_1","first-page":"169","article-title":"Semi-homomorphic Encryption and Multiparty Computation","volume":"2011","author":"Bendlin Rikke","year":"2011","unstructured":"Rikke Bendlin, Ivan Damg\u00e5rd, Claudio Orlandi, and Sarah Zakarias. 2011. Semi-homomorphic Encryption and Multiparty Computation. In Advances in Cryptology - EUROCRYPT 2011. 169-188.","journal-title":"Advances in Cryptology - EUROCRYPT"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 29th International Coference on International Conference on Machine Learning. 1467\u20131474","author":"Biggio Battista","year":"2012","unstructured":"Battista Biggio, Blaine Nelson, and Pavel Laskov. 2012. Poisoning attacks against support vector machines. In Proceedings of the 29th International Coference on International Conference on Machine Learning. 1467\u20131474."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132769"},{"key":"e_1_2_1_9_1","first-page":"947","volume-title":"30th USENIX Security Symposium (USENIX Security 21)","author":"Cao Xiaoyu","year":"2021","unstructured":"Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. 2021. Data Poisoning Attacks to Local Differential Privacy Protocols. In 30th USENIX Security Symposium (USENIX Security 21). 947-964."},{"key":"e_1_2_1_10_1","volume-title":"European Symposium on Algorithms. Springer, 277-288","author":"Hubert Chan TH","year":"2012","unstructured":"TH Hubert Chan, Elaine Shi, and Dawn Song. 2012. Optimal lower bound for differentially private multi-party aggregation. In European Symposium on Algorithms. Springer, 277-288."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-0602-4_18"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/358549.358563"},{"key":"e_1_2_1_13_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_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00001"},{"key":"e_1_2_1_15_1","first-page":"375","volume-title":"Darmstadt","author":"Cheu Albert","year":"2019","unstructured":"Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. 2019. Distributed differential privacy via shuffling. In Advances in Cryptology-EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part I 38. Springer, 375-403."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP46214.2022.9833614"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196906"},{"key":"e_1_2_1_18_1","first-page":"643","article-title":"Multiparty Computation from Somewhat Homomorphic Encryption","volume":"2012","author":"Damg\u00e5rd Ivan","year":"2012","unstructured":"Ivan Damg\u00e5rd, Valerio Pastro, Nigel Smart, and Sarah Zakarias. 2012. Multiparty Computation from Somewhat Homomorphic Encryption. In Advances in Cryptology - CRYPTO 2012. 643-662.","journal-title":"Advances in Cryptology - CRYPTO"},{"key":"e_1_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."},{"key":"e_1_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)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517844"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP46215.2023.10179466"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork Aaron Roth et al. 2014. The algorithmic foundations of differential privacy. Foundations and trends\u00ae in theoretical computer science Vol. 9 3-4 (2014) 211-407.","DOI":"10.1561\/0400000042"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.151"},{"key":"e_1_2_1_26_1","first-page":"1605","volume-title":"29th USENIX Security Symposium (USENIX Security 20)","author":"Fang Minghong","year":"2020","unstructured":"Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Gong. 2020. Local Model Poisoning Attacks to Byzantine-Robust Federated Learning. In 29th USENIX Security Symposium (USENIX Security 20). 1605-1622."},{"key":"e_1_2_1_27_1","first-page":"463","article-title":"On the Power of Multiple Anonymous Messages: Frequency Estimation and\u00a0Selection in the Shuffle Model of\u00a0Differential Privacy","volume":"2021","author":"Ghazi Badih","year":"2021","unstructured":"Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker. 2021a. On the Power of Multiple Anonymous Messages: Frequency Estimation and\u00a0Selection in the Shuffle Model of\u00a0Differential Privacy. In Advances in Cryptology - EUROCRYPT 2021. 463-488.","journal-title":"Advances in Cryptology - EUROCRYPT"},{"key":"e_1_2_1_28_1","volume-title":"Pure-DP Aggregation in the Shuffle Model: Error-Optimal and Communication-Efficient. In 5th Conference on Information-Theoretic Cryptography, ITC","volume":"304","author":"Ghazi Badih","year":"2024","unstructured":"Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. 2024. Pure-DP Aggregation in the Shuffle Model: Error-Optimal and Communication-Efficient. In 5th Conference on Information-Theoretic Cryptography, ITC 2024, Vol. 304. 4:1-4:13."},{"key":"e_1_2_1_29_1","volume-title":"International Conference on Machine Learning. PMLR, 3505-3514","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 International Conference on Machine Learning. PMLR, 3505-3514."},{"key":"e_1_2_1_30_1","volume-title":"International Conference on Machine Learning. PMLR, 3692-3701","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. PMLR, 3692-3701."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing. 218\u2013229","author":"Goldreich O.","unstructured":"O. Goldreich, S. Micali, and A. Wigderson. 1987. How to play ANY mental game. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing. 218\u2013229."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882931"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920970"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3698803"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725348"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560659"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.25"},{"key":"e_1_2_1_38_1","unstructured":"Kaggle. 2014. San Francisco City Employee Salary Data. https:\/\/www.kaggle.com\/datasets\/kaggle\/sf-salaries. Accessed: 2025-05-18."},{"key":"e_1_2_1_39_1","unstructured":"Kaggle. 2020. Monthly Salary of Public Worker in Brazil. https:\/\/www.kaggle.com\/datasets\/gustavomodelli\/monthly-salary-of-public-worker-in-brazil. Accessed: 2025-05-18."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989345"},{"key":"e_1_2_1_42_1","first-page":"202","article-title":"Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid","volume":"96","author":"Ron Kohavi","year":"1996","unstructured":"Ron Kohavi et al., 1996. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid.. In Kdd, Vol. 96. 202-207.","journal-title":"Kdd"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300102"},{"key":"e_1_2_1_44_1","first-page":"1739","volume-title":"32nd USENIX Security Symposium (USENIX Security 23)","author":"Li Xiaoguang","year":"2023","unstructured":"Xiaoguang Li, Ninghui Li, Wenhai Sun, Neil Zhenqiang Gong, and Hui Li. 2023. Fine-grained Poisoning Attack to Local Differential Privacy Protocols for Mean and Variance Estimation. In 32nd USENIX Security Symposium (USENIX Security 23). 1739-1756."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639285"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389700"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560608"},{"key":"e_1_2_1_48_1","volume-title":"Proc. ACM Manag. Data","volume":"3","author":"Luo Qiyao","year":"2025","unstructured":"Qiyao Luo, Jianzhe Yu, Wei Dong, Quanqing Xu, Chuanhui Yang, and Ke Yi. 2025. RM2: Answer Counting Queries Efficiently under Shuffle Differential Privacy. Proc. ACM Manag. Data, Vol. 3, 3, Article 210 (2025), 24 pages."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559850"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146847.1146848"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556576"},{"key":"e_1_2_1_52_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.","DOI":"10.1109\/49.668972"},{"key":"e_1_2_1_53_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\u201392."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526190"},{"key":"e_1_2_1_55_1","first-page":"480","volume-title":"UK","author":"Tolpegin Vale","year":"2020","unstructured":"Vale Tolpegin, Stacey Truex, Mehmet Emre Gursoy, and Ling Liu. 2020. Data poisoning attacks against federated learning systems. In Computer security-ESORICs 2020: 25th European symposium on research in computer security, ESORICs 2020, guildford, UK, September 14-18, 2020, proceedings, part i 25. Springer, 480-501."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658644.3670298"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3424573.3424576"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134053"},{"key":"e_1_2_1_59_1","first-page":"519","volume-title":"31st USENIX Security Symposium (USENIX Security 22)","author":"Wu Yongji","year":"2022","unstructured":"Yongji Wu, Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. 2022. Poisoning Attacks to Local Differential Privacy Protocols for Key-Value Data. In 31st USENIX Security Symposium (USENIX Security 22). 519-536."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725414"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3134428"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709739"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3786638","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T19:57:02Z","timestamp":1775591822000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3786638"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,2]]}},"alternative-id":["10.1145\/3786638"],"URL":"https:\/\/doi.org\/10.1145\/3786638","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]}}}