{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,15]],"date-time":"2025-08-15T02:33:38Z","timestamp":1755225218456,"version":"3.43.0"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,8,25]]},"DOI":"10.1145\/3708821.3736199","type":"proceedings-article","created":{"date-parts":[[2025,8,13]],"date-time":"2025-08-13T06:30:56Z","timestamp":1755066656000},"page":"635-650","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Robust Locally Differentially Private Graph Analysis"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3808-4652","authenticated-orcid":false,"given":"Amrita","family":"Roy Chowdhury","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, Ann Arbor, Michigan, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-0367-509X","authenticated-orcid":false,"given":"Jacob","family":"Imola","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9646-7710","authenticated-orcid":false,"given":"Kamalika","family":"Chaudhuri","sequence":"additional","affiliation":[{"name":"UCSD, San Diego, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,8,24]]},"reference":[{"key":"e_1_3_3_2_2_2","unstructured":"[n. d.]. Full Paper. https:\/\/drive.google.com\/file\/d\/1JqNR3YsA4l\u2013mFC2v4y0vFItOfHqv5Zb\/view?usp=sharing."},{"key":"e_1_3_3_2_3_2","doi-asserted-by":"publisher","unstructured":"Andris Ambainis Markus Jakobsson and Helger Lipmaa. 2003. Cryptographic Randomized Response Techniques. 10.48550\/ARXIV.CS\/0302025","DOI":"10.48550\/ARXIV.CS\/0302025"},{"key":"e_1_3_3_2_4_2","doi-asserted-by":"crossref","unstructured":"Udit Arora Hridoy\u00a0Sankar Dutta Brihi Joshi Aditya Chetan and Tanmoy Chakraborty. 2020. Analyzing and detecting collusive users involved in blackmarket retweeting activities. ACM Transactions on Intelligent Systems and Technology (TIST) 11 3 (2020) 1\u201324.","DOI":"10.1145\/3380537"},{"key":"e_1_3_3_2_5_2","volume-title":"arXiv:https:\/\/arXiv.org\/abs\/1807.00459","author":"Bagdasaryan Eugene","year":"2018","unstructured":"Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. 2018. How to backdoor federated learning. In arXiv:https:\/\/arXiv.org\/abs\/1807.00459."},{"key":"e_1_3_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85174-5_25"},{"key":"e_1_3_3_2_7_2","unstructured":"James Bell-Clark Adri\u00e0 Gasc\u00f3n Baiyu Li Mariana Raykova and Amrita\u00a0Roy Chowdhury. 2025. V\u03f5 rity: Verifiable Local Differential Privacy. Cryptology ePrint Archive Paper 2025\/851. https:\/\/eprint.iacr.org\/2025\/851"},{"key":"e_1_3_3_2_8_2","first-page":"634","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Bhagoji Arjun\u00a0Nitin","year":"2019","unstructured":"Arjun\u00a0Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo. 2019. Analyzing federated learning through an adversarial lens. In Proceedings of the International Conference on Machine Learning. 634\u2013643."},{"key":"e_1_3_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/3042573.3042761"},{"key":"e_1_3_3_2_10_2","unstructured":"Tariq Bontekoe Hassan\u00a0Jameel Asghar and Fatih Turkmen. 2024. Efficient Verifiable Differential Privacy with Input Authenticity in the Local and Shuffle Model. arxiv:https:\/\/arXiv.org\/abs\/2406.18940\u00a0[cs.CR] https:\/\/arxiv.org\/abs\/2406.18940"},{"key":"e_1_3_3_2_11_2","volume-title":"arXiv:https:\/\/arXiv.org\/abs\/2107.03311","author":"Burkhalter Lukas","year":"2021","unstructured":"Lukas Burkhalter, Hidde Lycklama, Alexander Viand, Nicolas K\u00fcchler, and Anwar Hithnawi. 2021. RoFL: Attestable Robustness for Secure Federated Learning. In arXiv:https:\/\/arXiv.org\/abs\/2107.03311."},{"key":"e_1_3_3_2_12_2","first-page":"947","volume-title":"30th USENIX Security Symposium (USENIX Security 21)","author":"Cao Xiaoyu","year":"2021","unstructured":"Xiaoyu Cao, Jinyuan Jia, and Neil\u00a0Zhenqiang Gong. 2021. Data Poisoning Attacks to Local Differential Privacy Protocols. In 30th USENIX Security Symposium (USENIX Security 21). USENIX Association, 947\u2013964. https:\/\/www.usenix.org\/conference\/usenixsecurity21\/presentation\/cao-xiaoyu"},{"key":"e_1_3_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/296806.296824"},{"key":"e_1_3_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_25"},{"key":"e_1_3_3_2_15_2","volume-title":"arXiv:https:\/\/arXiv.org\/abs\/1712.05526","author":"Chen Xinyun","year":"2017","unstructured":"Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. 2017. Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning. In arXiv:https:\/\/arXiv.org\/abs\/1712.05526."},{"key":"e_1_3_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00001"},{"key":"e_1_3_3_2_17_2","unstructured":"Amrita\u00a0Roy Chowdhury Jacob Imola and Kamalika Chaudhuri. [n. d.]. Code. https:\/\/github.com\/jimola\/GraphPoisoning."},{"key":"e_1_3_3_2_18_2","unstructured":"Amrita\u00a0Roy Chowdhury Jacob Imola and Kamalika Chaudhuri. 2022. Full Paper. arxiv:https:\/\/arXiv.org\/abs\/2210.14376\u00a0[cs.CR] https:\/\/arxiv.org\/abs\/2210.14376"},{"key":"e_1_3_3_2_19_2","doi-asserted-by":"crossref","unstructured":"Aaron Clauset Mark\u00a0EJ Newman and Cristopher Moore. 2004. Finding community structure in very large networks. Physical review E 70 6 (2004) 066111.","DOI":"10.1103\/PhysRevE.70.066111"},{"key":"e_1_3_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.53"},{"key":"e_1_3_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.53"},{"key":"e_1_3_3_2_22_2","doi-asserted-by":"crossref","unstructured":"Hridoy\u00a0Sankar Dutta and Tanmoy Chakraborty. 2022. Blackmarket-driven collusion on online media: a survey. ACM\/IMS Transactions on Data Science (TDS) 2 4 (2022) 1\u201337.","DOI":"10.1145\/3517931"},{"key":"e_1_3_3_2_23_2","doi-asserted-by":"publisher","unstructured":"Cynthia Dwork Nancy Lynch and Larry Stockmeyer. 1988. Consensus in the presence of partial synchrony. J. ACM 35 2 (April 1988) 288\u2013323. 10.1145\/42282.42283","DOI":"10.1145\/42282.42283"},{"key":"e_1_3_3_2_24_2","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork and Aaron Roth. 2014. The Algorithmic Foundations of Differential Privacy. Found. Trends Theor. Comput. Sci. 9 (Aug. 2014) 211\u2013407.","DOI":"10.1561\/0400000042"},{"key":"e_1_3_3_2_25_2","unstructured":"Paul Erd\u0151s Alfr\u00e9d R\u00e9nyi et\u00a0al. 1960. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci 5 1 (1960) 17\u201360."},{"key":"e_1_3_3_2_26_2","volume-title":"CCS","author":"Erlingsson \u00dalfar","year":"2014","unstructured":"\u00dalfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014. Rappor: Randomized aggregatable privacy-preserving ordinal response. In CCS."},{"key":"e_1_3_3_2_27_2","volume-title":"USENIX Security Symposium","author":"Fang Minghong","year":"2020","unstructured":"Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil\u00a0Zhenqiang Gong. 2020. Local Model Poisoning Attacks to Byzantine-Robust Federated Learning. In USENIX Security Symposium."},{"key":"e_1_3_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891"},{"key":"e_1_3_3_2_29_2","unstructured":"Andy Greenberg. 2016. Apple\u2019s \u2018Differential Privacy\u2019 Is About Collecting Your Data\u2014But Not Your Data. Wired (Jun 13 2016)."},{"key":"e_1_3_3_2_30_2","unstructured":"Venkatesan Guruswami Atri Rudra and Madhu Sudan. 2012. Essential coding theory. Draft available at http:\/\/www. cse. buffalo. edu\/atri\/courses\/coding-theory\/book 2 1 (2012)."},{"key":"e_1_3_3_2_31_2","doi-asserted-by":"publisher","unstructured":"Hikaru Horigome Hiroaki Kikuchi Masahiro Fujita and Chia-Mu Yu. 2024. Robust Estimation Method against Poisoning Attacks for Key-Value Data with Local Differential Privacy. Applied Sciences 14 14 (2024). 10.3390\/app14146368","DOI":"10.3390\/app14146368"},{"key":"e_1_3_3_2_32_2","doi-asserted-by":"publisher","unstructured":"Kai Huang Gaoya Ouyang Qingqing Ye Haibo Hu Bolong Zheng Xi Zhao Ruiyuan Zhang and Xiaofang Zhou. 2024. LDPGuard: Defenses Against Data Poisoning Attacks to Local Differential Privacy Protocols. IEEE Transactions on Knowledge and Data Engineering 36 7 (2024) 3195\u20133209. 10.1109\/TKDE.2024.3358909","DOI":"10.1109\/TKDE.2024.3358909"},{"key":"e_1_3_3_2_33_2","first-page":"983","volume-title":"30th USENIX Security Symposium (USENIX Security 21)","author":"Imola Jacob","year":"2021","unstructured":"Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. 2021. Locally differentially private analysis of graph statistics. In 30th USENIX Security Symposium (USENIX Security 21). 983\u20131000."},{"key":"e_1_3_3_2_34_2","unstructured":"Jacob Imola Takao Murakami and Kamalika Chaudhuri. 2022. Communication-Efficient Triangle Counting under Local Differential Privacy. arXiv:https:\/\/arXiv.org\/abs\/2110.06485 [cs] (Jan. 2022). http:\/\/arxiv.org\/abs\/2110.06485 arXiv:https:\/\/arXiv.org\/abs\/2110.06485."},{"key":"e_1_3_3_2_35_2","volume-title":"arXiv:https:\/\/arXiv.org\/abs\/1912.04977","author":"Kairouz Peter","year":"2019","unstructured":"Peter Kairouz, H.\u00a0Brendan McMahan, Brendan Avent, Aurelien Bellet, Mehdi Bennis, Arjun\u00a0Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael\u00a0G.L. D\u2019Oliveira, Hubert Eichner, Salim\u00a0El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adria Gascon, Badih Ghazi, Phillip\u00a0B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecny, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrede Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Ozgur, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian\u00a0U. Stich, Ziteng Sun, Ananda\u00a0Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix\u00a0X. Yu, Han Yu, and Sen Zhao. 2019. Advances and Open Problems in Federated Learning. In arXiv:https:\/\/arXiv.org\/abs\/1912.04977."},{"key":"e_1_3_3_2_36_2","first-page":"1376","volume-title":"International conference on machine learning","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\u20131385."},{"key":"e_1_3_3_2_37_2","unstructured":"Fumiyuki Kato Yang Cao and Masatoshi Yoshikawa. 2021. Preventing Manipulation Attack in Local Differential Privacy using Verifiable Randomization Mechanism. CoRR abs\/2104.06569 (2021). arXiv:https:\/\/arXiv.org\/abs\/2104.06569https:\/\/arxiv.org\/abs\/2104.06569"},{"key":"e_1_3_3_2_38_2","doi-asserted-by":"publisher","unstructured":"Xiaoguang Li Neil\u00a0Zhenqiang Gong Ninghui Li Wenhai Sun and Hui Li. 2022. Fine-grained Poisoning Attacks to Local Differential Privacy Protocols for Mean and Variance Estimation. 10.48550\/ARXIV.2205.11782","DOI":"10.48550\/ARXIV.2205.11782"},{"key":"e_1_3_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.5555\/2999134.2999195"},{"key":"e_1_3_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9569"},{"key":"e_1_3_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_7"},{"key":"e_1_3_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_3_3_2_43_2","doi-asserted-by":"publisher","unstructured":"M. Pease R. Shostak and L. Lamport. 1980. Reaching Agreement in the Presence of Faults. J. ACM 27 2 (April 1980) 228\u2013234. 10.1145\/322186.322188","DOI":"10.1145\/322186.322188"},{"key":"e_1_3_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134086"},{"key":"e_1_3_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134086"},{"key":"e_1_3_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4549"},{"key":"e_1_3_3_2_47_2","doi-asserted-by":"publisher","unstructured":"Amrita Roy\u00a0Chowdhury Chuan Guo Somesh Jha and Laurens van\u00a0der Maaten. 2021. EIFFeL: Ensuring Integrity for Federated Learning. 10.48550\/ARXIV.2112.12727","DOI":"10.48550\/ARXIV.2112.12727"},{"key":"e_1_3_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP46214.2022.9833647"},{"key":"e_1_3_3_2_49_2","doi-asserted-by":"publisher","unstructured":"Haiying Shen Yuhua Lin Karan Sapra and Ze Li. 2016. Enhancing Collusion Resilience in Reputation Systems. IEEE Transactions on Parallel and Distributed Systems 27 8 (2016) 2274\u20132287. 10.1109\/TPDS.2015.2489198","DOI":"10.1109\/TPDS.2015.2489198"},{"key":"e_1_3_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68208-7_18"},{"key":"e_1_3_3_2_51_2","first-page":"0090","volume-title":"EDBT\/ICDT Workshops","author":"Wang Yue","year":"2016","unstructured":"Yue Wang, Xintao Wu, and Donghui Hu. 2016. Using Randomized Response for Differential Privacy Preserving Data Collection.. In EDBT\/ICDT Workshops , Vol.\u00a01558. 0090\u20136778."},{"key":"e_1_3_3_2_52_2","doi-asserted-by":"crossref","unstructured":"Stanley\u00a0L Warner. 1965. Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias. J. Amer. Statist. Assoc. 60 60 no. 309 (1965) 63\u201369.","DOI":"10.1080\/01621459.1965.10480775"},{"key":"e_1_3_3_2_53_2","doi-asserted-by":"publisher","unstructured":"Yongji Wu Xiaoyu Cao Jinyuan Jia and Neil\u00a0Zhenqiang Gong. 2021. Poisoning Attacks to Local Differential Privacy Protocols for Key-Value Data. 10.48550\/ARXIV.2111.11534","DOI":"10.48550\/ARXIV.2111.11534"},{"key":"e_1_3_3_2_54_2","volume-title":"ICLR","author":"Xie Chulin","year":"2020","unstructured":"Chulin Xie, Keli Huang, Pin-Yu Chen, and Bo Li. 2020. DBA: Distributed Backdoor Attacks against Federated Learning. In ICLR."},{"key":"e_1_3_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30216-2_8"}],"event":{"name":"ASIA CCS '25: 20th ACM Asia Conference on Computer and Communications Security","location":"Hanoi Vietnam","acronym":"ASIA CCS '25","sponsor":["SIGSAC ACM Special Interest Group on Security, Audit, and Control"]},"container-title":["Proceedings of the 20th ACM Asia Conference on Computer and Communications Security"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3708821.3736199","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,13]],"date-time":"2025-08-13T07:26:43Z","timestamp":1755070003000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708821.3736199"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,24]]},"references-count":54,"alternative-id":["10.1145\/3708821.3736199","10.1145\/3708821"],"URL":"https:\/\/doi.org\/10.1145\/3708821.3736199","relation":{},"subject":[],"published":{"date-parts":[[2025,8,24]]},"assertion":[{"value":"2025-08-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}