Inverse Décalé

Alors que la plupart des travaux sur la confidentialité différentielle se sont concentrés sur la protection de la vie privée des tuples, il a été réalisé qu'un modèle aussi simple ne peut pas capturer les relations complexes entre les utilisateurs et les tuples dans de nombreuses applications du monde réel. Ainsi, la confidentialité différentielle utilisateur (user-DP) a récemment gagné en attention, ce qui inclut le node-DP pour les données graphiques comme un cas particulier. La plupart des travaux existants sur l'user-DP n'ont étudié que le problème d'estimation de la somme. Dans ce travail, nous concevons un mécanisme DP général pour toute fonction monotone sous l'user-DP avec de fortes garanties d'optimalité. Bien que notre mécanisme général puisse fonctionner en temps super-polynôme, nous montrons comment instancier une version approchée en temps polynomial sur certaines fonctions monotones communes, y compris la somme, la k-sélection, la fréquence maximale et le nombre distinct. Enfin, nous menons des expériences sur toutes ces fonctions et les résultats montrent que notre cadre est plus général et obtient de meilleurs résultats dans de nombreux cas.