Defining and Enforcing Privacy in Data Sharing

Other Titles


Recent advances in processing and storing information has led to an explosion of data collection. Many organizations like the Census, hospitals and even search engine companies collect, analyze and distribute personal information in return for useful services. However, the collected data track entire public and private lives of individuals, thus resulting in an immense privacy risk of unauthorized disclosure. This dissertation presents novel conceptual and practical tools to ensure privacy of individuals while enabling the dissemination of valuable data about humans to improve their lives. Our contributions include novel formal definitions of the privacy risk arising from unauthorized disclosure, and practical algorithms for enforcing these definitions of privacy.

We consider two distinct settings of data dissemination that require different notions of privacy. In the first part of this dissertation, we consider a setting where no sensitive information should be disclosed. We consider the problem of deciding whether answering a query on a relational database leads to any disclosure of sensitive information. This problem was shown to be intractable; we propose practical algorithms for a reasonably large set of query classes.

In the second part of the dissertation, we consider the problem of publishing anonymous'' aggregate information about populations of individuals while preserving the privacy of individual-specific information. We present a novel framework for reasoning about the privacy risk in this setting. We also propose the first formal privacy definition and practical algorithms for publishing anonymous'' data that provably guarantees privacy of the individuals contributing to the data while releasing useful aggregate information. We also present a case study of applying formal privacy definitions to a real Census data publishing application.

Journal / Series

Volume & Issue


Prof. Johannes Gehrke, Committee Chair. Prof. Eva Tardos, Committee Member. Prof. Joseph Halpern, Committee Member. Dr. Jayavel Shanmugasundaram, Committee Member.


Date Issued




Privacy; Databases; K-Anonymity; L-Diversity; Access Control; Anonymous Data Publishing


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record