2026-07-23T22:35:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22681 2026-04-17T05:32:14Z ddc:004 open_access

Differential Privacy on Trust Graphs Ghazi, Badih Kumar, Ravi Manurangsi, Pasin Wang, Serena Differential privacy trust graphs minimum dominating set packing number We study differential privacy (DP) in a multi-party setting where each party only trusts a (known) subset of the other parties with its data. Specifically, given a trust graph where vertices correspond to parties and neighbors are mutually trusting, we give a DP algorithm for aggregation with a much better privacy-utility trade-off than in the well-studied local model of DP (where each party trusts no other party). We further study a robust variant where each party trusts all but an unknown subset of at most t of its neighbors (where t is a given parameter), and give an algorithm for this setting. We complement our algorithms with lower bounds, and discuss implications of our work to other tasks in private learning and analytics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Badih Ghazi and Ravi Kumar and Pasin Manurangsi and Serena Wang 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.53 urn:nbn:de:0030-drops-226816 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.53 eng https://creativecommons.org/licenses/by/4.0/legalcode