RSS Google AI Blog
Follow
Differential privacy on trust graphs
Differential privacy (DP) is a mathematically rigorous privacy framework that ensures the output of a randomized algorithm remains statistically indistinguishable even if the data of a single user changes. There are two main models of DP: the central model, where a trusted curator has access to raw data, and the local model, where all messages sent from a user's device are themselves differentially private. In real-world data-sharing scenarios, users often place varying levels of trust in others, depending on their relationships. This asymmetry highlights the need for frameworks that go beyond binary trust assumptions. The concept of trust graph DP (TGDP) models relationships, where vertices represent users, and connected vertices trust each other. TGDP ensures that the privacy guarantee applies to messages shared between a user and everyone else they do not trust. TGDP interpolates between the central and local models in a natural way, and its accuracy can be quantified through a simple aggregation task. An algorithm based on a dominating set of the trust graph can satisfy TGDP, and its error is upper bounded by a function of the dominating set. A lower bound on the error of TGDP algorithms is also provided, and closing the gap between the upper and lower bounds is an open problem. The TGDP model can be applied to federated learning and analytics, allowing for more realistic trust dynamics in privacy-preserving systems.