Skip to main content

Sparsi: Partitioning sensitive data amongst multiple adversaries

Publication ,  Journal Article
Rekatsinas, T; Deshpande, A; Machanavajjhala, A
Published in: Proceedings of the VLDB Endowment
January 1, 2013

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. © 2013 VLDB Endowment.

Duke Scholars

Published In

Proceedings of the VLDB Endowment

DOI

EISSN

2150-8097

Publication Date

January 1, 2013

Volume

6

Issue

13

Start / End Page

1594 / 1605

Related Subject Headings

  • 4605 Data management and data science
  • 0807 Library and Information Studies
  • 0806 Information Systems
  • 0802 Computation Theory and Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Rekatsinas, T., Deshpande, A., & Machanavajjhala, A. (2013). Sparsi: Partitioning sensitive data amongst multiple adversaries. Proceedings of the VLDB Endowment, 6(13), 1594–1605. https://doi.org/10.14778/2536258.2536270
Rekatsinas, T., A. Deshpande, and A. Machanavajjhala. “Sparsi: Partitioning sensitive data amongst multiple adversaries.” Proceedings of the VLDB Endowment 6, no. 13 (January 1, 2013): 1594–1605. https://doi.org/10.14778/2536258.2536270.
Rekatsinas T, Deshpande A, Machanavajjhala A. Sparsi: Partitioning sensitive data amongst multiple adversaries. Proceedings of the VLDB Endowment. 2013 Jan 1;6(13):1594–605.
Rekatsinas, T., et al. “Sparsi: Partitioning sensitive data amongst multiple adversaries.” Proceedings of the VLDB Endowment, vol. 6, no. 13, Jan. 2013, pp. 1594–605. Scopus, doi:10.14778/2536258.2536270.
Rekatsinas T, Deshpande A, Machanavajjhala A. Sparsi: Partitioning sensitive data amongst multiple adversaries. Proceedings of the VLDB Endowment. 2013 Jan 1;6(13):1594–1605.

Published In

Proceedings of the VLDB Endowment

DOI

EISSN

2150-8097

Publication Date

January 1, 2013

Volume

6

Issue

13

Start / End Page

1594 / 1605

Related Subject Headings

  • 4605 Data management and data science
  • 0807 Library and Information Studies
  • 0806 Information Systems
  • 0802 Computation Theory and Mathematics