Proceedings of the VLDB Endowment · 2015 · 17 citations · 18 references
ComputingComputer ScienceAlgorithmsCryptographyDatabasesData AnonymizationData PrivacyData ProtectionDatabase PrivacyDifferential PrivacyPrivacy-preserving ProtocolsNeighbor DiscoveryPrivacy-preserving Query ProcessingPrivate Query AnsweringPrivate Query ProcessingQuery Answering Under Privacy ConstraintsRange QueriesTransformationsWorkload
The problem of designing error optimal differentially private algorithms is well studied. Recent work applying differential privacy to real world settings have used variants of differential privacy that appropriately modify the notion of neighboring databases. The problem of designing error optimal algorithms for such variants of differential privacy is open. In this paper, we show a novel transformational equivalence result that can turn the problem of query answering under differential privacy with a modified notion of neighbors to one of query answering under standard differential privacy, for a large class of neighbor definitions. We utilize the Blowfish privacy framework that generalizes differential privacy. Blowfish uses a policy graph to instantiate different notions of neighboring databases. We show that the error incurred when answering a workload W on a database x under a Blowfish policy graph G is identical to the error required to answer a transformed workload f G ( W ) on database g G ( x ) under standard differential privacy, where f G and g G are linear transformations based on G. Using this result, we develop error efficient algorithms for releasing histograms and multidimensional range queries under different Blowfish policies. We believe the tools we develop will be useful for finding mechanisms to answer many other classes of queries with low error under other policy graphs.
18
Cynthia Dwork, Moritz Hardt, Toniann Pitassi et al. · 2012 · 3.4K citations
Miguel E. Andrés, Nicolás E. Bordenabe, Konstantinos Chatzikokolakis et al. · 2013 · 1K citations · Full text
Computing, Cybersecurity, Geographic Information Systems +10
The geometry of graphs and some of its algorithmic applications
Nathan Linial, Eran London, Yuri Rabinovich · COMBINATORICA · 1995 · 974 citations
Differential privacy under continual observation
Cynthia Dwork, Moni Naor, Toniann Pitassi et al. · 2010 · 585 citations