Utility-Privacy Tradeoffs in Databases: An Information-Theoretic Approach

Ensuring the usefulness of electronic data sources while providing necessary privacy guarantees is an important unsolved problem. This problem drives the need for an analytical framework that can quantify the privacy of personally identifiable information while still providing a quantifiable benefit (utility) to multiple legitimate information consumers. This paper presents an information-theoretic framework that promises an analytical model guaranteeing tight bounds of how much utility is possible for a given level of privacy and vice-versa. Specific contributions include: 1) stochastic data models for both categorical and numerical data; 2) utility-privacy tradeoff regions and the encoding (sanization) schemes achieving them for both classes and their practical relevance; and 3) modeling of prior knowledge at the user and/or data source and optimal encoding schemes for both cases.

I. Introduction

Just as information technology and electronic communications have been rapidly applied to almost every sphere of human activity, including commerce, medicine and social networking, the risk of accidental or intentional disclosure of sensitive private information has increased. The concomitant creation of large centralized searchable data repositories and deployment of applications that use them has made leakage of private information such as medical data, credit card information, power consumption data, etc. highly probable and thus an important and urgent societal problem. In contrast to the secrecy problem, in the privacy problem, disclosing data provides informational utility while enabling possible loss of privacy at the same time. Thus, as shown in Fig. 1, in the course of a legitimate transaction, a user learns some public information (e.g., gender and weight), which is allowed and needs to be supported for the transaction to be meaningful, and at the same time he can also learn/infer private information (e.g., cancer diagnosis and income), which needs to be prevented (or minimized). Thus, every user of the data is (potentially) also an adversary. Fig. 1.

Example database with public and private attributes and its sanitized version.