Differential Privacy on Trust Graphs
This work addresses privacy challenges for distributed systems where parties have limited trust, offering practical solutions for private learning and analytics.
The paper tackles the problem of differential privacy in multi-party settings with trust relationships, achieving a significantly improved privacy-utility trade-off compared to the local model, and also addresses a robust variant with unknown untrusted neighbors.
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.