SPARSI
Open Access
- 29 August 2013
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 6 (13) , 1594-1605
Abstract
We present SPARSI, a novel theoretical framework for partitioning sensitive data across multiple non-colluding adversaries. Most work in privacy-aware data sharing has considered disclosing summaries where the aggregate information about the data is preserved, but sensitive user information is protected. Nonetheless, there are applications, including online advertising, cloud computing and crowdsourcing markets, where detailed and fine-grained user data must be disclosed. We consider a new data sharing paradigm and introduce the problem of privacy-aware data partitioning, where a sensitive dataset must be partitioned among k untrusted parties (adversaries). The goal is to maximize the utility derived by partitioning and distributing the dataset, while minimizing the total amount of sensitive information disclosed. The data should be distributed so that an adversary, without colluding with other adversaries, cannot draw additional inferences about the private information, by linking together multiple pieces of information released to her. The assumption of no collusion is both reasonable and necessary in the above application domains that require release of private user information. SPARSI enables us to formally define privacy-aware data partitioning using the notion of sensitive properties for modeling private information and a hypergraph representation for describing the interdependencies between data entries and private information. We show that solving privacy-aware partitioning is, in general, NP-hard, but for specific information disclosure functions, good approximate solutions can be found using relaxation techniques. Finally, we present a local search algorithm applicable to generic information disclosure functions. We conduct a rigorous performance evaluation with real-world and synthetic datasets that illustrates the effectiveness of SPARSI at partitioning sensitive data while minimizing disclosure.Keywords
This publication has 9 references indexed in Scilit:
- Sedic2011
- 19th Usenix Security Symposium AdvertisementIEEE Security & Privacy, 2010
- Randomized Rounding for Routing and Covering Problems: Experiments and ImprovementsLecture Notes in Computer Science, 2010
- Privacy-Preserving Data PublishingFoundations and Trends® in Databases, 2009
- Dependent rounding and its applications to approximation algorithmsJournal of the ACM, 2006
- k-ANONYMITY: A MODEL FOR PROTECTING PRIVACYInternational Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- Greedy Randomized Adaptive Search ProceduresJournal of Global Optimization, 1995
- Randomized rounding: A technique for provably good algorithms and algorithmic proofsCombinatorica, 1987