Differential privateness (DP) is a mathematically rigorous and broadly studied privateness framework that ensures the output of a randomized algorithm stays statistically indistinguishable even when the info of a single person modifications. This framework has been extensively studied in each principle and observe, with many purposes in analytics and machine studying (e.g., 1, 2, 3, 4, 5, 6, 7).
The 2 principal fashions of DP are the central mannequin and the native mannequin. Within the central mannequin, a trusted curator has entry to uncooked information and is accountable for producing an output that’s differentially non-public. The native mannequin requires that each one messages despatched from a person’s gadget are themselves differentially non-public, eradicating the necessity for a trusted curator. Whereas the native mannequin is interesting resulting from its minimal belief necessities, it typically comes with considerably larger utility degradation in comparison with the central mannequin.
In real-world data-sharing eventualities, customers typically place various ranges of belief in others, relying on their relationships. For example, somebody may really feel comfy sharing their location information with household or shut mates however would hesitate to permit strangers to entry the identical info. This asymmetry aligns with philosophical views of privateness as management over private info, the place people specify with whom they’re prepared to share their information. Such nuanced privateness preferences spotlight the necessity for frameworks that transcend the binary belief assumptions of current differentially non-public fashions, accommodating extra real looking belief dynamics in privacy-preserving programs.
In “Differential Privateness on Belief Graphs”, printed on the Improvements in Theoretical Pc Science Convention (ITCS 2025), we use a belief graph to mannequin relationships, the place the vertices symbolize customers, and linked vertices belief one another (see beneath). We discover tips on how to apply DP to those belief graphs, making certain that the privateness assure applies to messages shared between a person (or their trusted neighbors) and everybody else they don’t belief. Specifically, the distribution of messages exchanged by every person u or one in every of their neighbors with some other person not trusted by u must be statistically indistinguishable if the enter held by u modifications, which we name belief graph DP (TGDP).
