  We present SPARSI, a 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 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 apply SPARSI
together with the proposed algorithms on data from a real advertising scenario
and show that we can partition data with no disclosure to any single
advertiser.
