PaperlayerView exact revision on arXiv

Source-linked AI summary

Utility-Privacy Tradeoff in Databases: An Information-theoretic Approach

Lalitha Sankar, S. Raj Rajagopalan, H. Vincent Poor

arXiv:1102.3751v4cs.IT

TL;DR

The paper addresses the open problem of quantifying the tradeoff between useful database disclosure and privacy protection. It develops an information-theoretic framework with statistical models, utility and privacy metrics, disclosure constraints, and side-information modeling. The framework characterizes tight tradeoff bounds and provides sanitization schemes and examples for numerical and categorical databases.

  • Problem

    An analytical characterization of the maximum achievable utility for a given privacy level, and vice versa, remains open while accounting for disclosure precision and prior knowledge.

  • Method

    The paper extends rate-distortion analysis with privacy constraints, statistical database models, disclosure-rate constraints, and side-information models to design sanitization mechanisms.

  • Results

    The framework quantifies fundamental utility-privacy tradeoff bounds and presents sanitization schemes achieving the tradeoff region for numerical and categorical examples.

  • Takeaways & Limitations

    Statistical source models and utility-privacy metrics can determine distortion and suppression choices that provide both privacy and utility guarantees.

Abstract

from arXiv · show

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 safety of personally identifiable information (privacy) while still providing a quantifable 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: i) stochastic data models for both categorical and numerical data; ii) utility-privacy tradeoff regions and the encoding (sanization) schemes achieving them for both classes and their practical relevance; and iii) modeling of prior knowledge at the user and/or data source and optimal encoding schemes for both cases.

I. INTRODUCTION

The paper formulates utility and privacy as competing objectives and develops an information-theoretic framework to characterize their achievable tradeoff. It models database attributes statistically, quantifies utility through distortion and privacy through equivocation, and addresses disclosure precision and prior knowledge.

  • Motivation: Privacy-preserving disclosure must balance informational utility against possible privacy loss, because publishing data can support legitimate transactions while revealing or enabling inference of sensitive attributes.The introduction illustrates this tension with public attributes such as gender and weight and private attributes such as cancer and income.
  • Problem: The open problem is an analytical characterization of all achievable utility-privacy points, including the maximum utility at a given privacy level and vice versa.The paper identifies statistical assumptions, differentiated disclosure across users, and prior knowledge as unresolved modeling questions.
  • Framework: The framework translates rate-distortion theory into the utility-privacy setting, measuring utility through distortion or accuracy and privacy through equivocation or entropy.Privacy is linked to keeping the conditional entropy of private attributes high after public disclosure.
  • Disclosure precision: The paper adds disclosure rate as a constraint because controlled disclosure must specify output precision, especially for categorical data where additive noise is unavailable.Numerical attributes may be noised or quantized, while categorical attributes require explicit precision or suppression choices.
  • Contributions: The authors develop generic models and metrics for multidimensional databases and streams, derive fundamental tradeoff bounds, and present sanitization schemes for numerical and categorical data.The schemes are described as achieving the utility-privacy tradeoff region and are demonstrated on both data classes.
  • Prior knowledge: The framework incorporates internal and external side information and shows that source statistics can determine the optimal sanitization mechanism and the largest utility-privacy tradeoff region.The introduction presents side information as a response to the power of correlations available to users or adversaries.

II. RELATED WORK

Prior privacy techniques range from ad hoc and heuristic methods to formal differential privacy, but a rigorous utility-privacy tradeoff model with optimal mappings remained open. This paper addresses that gap with an information-theoretic approach spanning categorical and numerical data.

  • Earlier census-data methods included sub-sampling, aggregation, and suppression, followed by k-anonymity as the first formal privacy definition.
  • k-anonymity protects against identity disclosure but not attribute-based disclosure, while later methods such as l-diversity and t-closeness remained non-universal against limited adversaries.
  • Differential privacy provides a universal formalism and can sanitize numerical data with appropriately chosen Laplacian noise, but is stronger than this paper’s Shannon-entropy privacy definition.
  • The paper’s sanitization approach covers categorical and numerical data, whereas differential privacy appears limited to numerical data and can incur significant utility loss.
  • The open problem was a rigorous model of privacy-utility tradeoffs with a method achieving all optimal points, motivating information-theoretic analysis.
  • The framework models large datasets statistically and suppresses low-probability, high-information outliers while distorting frequent samples less.
  • Categorical-database solutions formally provide uncertainty by suppressing high-information outliers and distorting other samples to the desired utility level.
  • Distortion can preserve application-selected functions, including aggregate statistics, while randomizing public data to protect private information inferred from it.

B. Background: Rate-distortion Theory

The paper frames sanitization as rate-distortion-style quantization over large database realizations, subject to both utility and privacy constraints. It characterizes optimal tradeoffs through converse bounds and achievable mappings, including settings with side information.

  • The framework has two steps: modeling the data and deriving the mathematical formalism for sanitization.
  • Sanitization maps a database to one of M = 2^nR output databases so every input has a sanitized database within distortion nD.
  • The source-sanitized pairs must satisfy both a distortion constraint and a bound on leakage about private attributes through the sanitized database.
  • Only public attributes are sanitized, so the sanitized database may lie in a subspace where the utility requirement applies.
  • Users may possess correlated side information, and decoders combine it with the sanitized database to reconstruct the final database.
  • The U-P region combines converse outer bounds with achievable inner-bound codes; when they meet, the construction achieves the entire tradeoff.
  • For tractable Gaussian, Laplacian, and arbitrary discrete sources, constructive schemes often attain tight utility-privacy tradeoffs.
  • Statistics enable perturbation mappings matched to the source and eliminate signal-perturbation mismatch; quantization irreversibility prevents reversal despite statistical knowledge.

IV. MODEL AND METRICS

The model represents a large database as independent rows whose attributes may be correlated, separating public attributes from private ones. Public information is sanitized before release, while users may combine it with correlated side information for reconstruction.

  • A. Model for Databases: A database is a matrix whose rows represent individuals and columns represent attributes, with row independence assumed generally for large databases.
  • A. Model for Databases: Each row is modeled as a joint observation of K attributes, allowing correlations across attributes that can reveal information about one another.
  • Public and private attributes: Attributes are partitioned into public and private sets, while the notation also permits an attribute or a function of it to be both public and private.
  • Revealed attributes and side information: Because correlated public attributes can reveal private attributes, public data is sanitized or distorted before being released.
  • Revealed attributes and side information: Users may have correlated side information modeled jointly with database entries, and reconstruction combines that information with released public attributes.

B. Metrics: The Privacy and Utility Principle

The paper defines utility through similarity between perturbed and original database responses, and privacy through uncertainty about private attributes given the response. These measures provide a common abstract basis for application-specific privacy-utility analysis.

  • Utility is highest for an unperturbed database and approaches zero when the perturbed database is unrelated to the original.
  • The utility metric is an appropriately chosen average distance between the original and perturbed databases.
  • Privacy is maximized when the perturbed response is independent of the data.
  • The privacy metric measures uncertainty or equivocation about private attributes given the response, reflecting the difficulty of extracting private information.
  • Mutual information is used in related formulations to quantify leakage or secrecy between private attributes and the response.

C. Utility and Privacy Aware Encoding

The paper models database sanitization as lossy compression: an encoder maps input databases to indexed sanitized outputs, from which users reconstruct public variables subject to utility and privacy constraints.

  • Encoding framework: The encoder FE maps allowable input databases to indices in J, selecting among M sanitized database outputs.The resulting index identifies a quantized database designed to satisfy distortion and privacy constraints.
  • Encoding framework: Users reconstruct a database from the transmitted index and optional side information, so the reconstructed database may differ from the sanitized output.The reconstruction is produced through a mapping that uses J and Z^n when side information is available.
  • Utility and privacy metrics: Utility is defined by an upper bound on average distortion of public variables under a specified distortion function.Examples include Euclidean distance, Hamming distance, and Kullback–Leibler divergence.
  • Utility and privacy metrics: Privacy is quantified primarily by equivocation, the conditional entropy of private variables, while leakage can be quantified by mutual information.With side information, equivocation lies between H(X_Kh|X_Kr,Z) and H(X_Kh|Z), and leakage lies between I(X_Kh;Z) and I(X_Kh;X_Kr,Z).
  • Utility and privacy metrics: The formalism averages distortion and equivocation over database realizations drawn from the underlying joint distribution.The averaging interpretation relies on the statistical model of database entries and, for large n, stationarity assumptions.
  • Scope of constraints: The exposition focuses on constraints over all public and private attributes, although the framework can be generalized to subsets.A general database may impose utility constraints on public subsets and privacy constraints on private subsets.

V. UTILITY-PRIVACY TRADEOFFS

The paper formulates utility, privacy, and precision jointly through rate-distortion-equivocation theory. Its tradeoff region characterizes feasible operating points and identifies boundary functions for fixed distortion.

  • Tradeoff formulation: Utility is mapped to distortion, privacy to equivocation, and precision to rate within an information-theoretic source-coding formulation.Rate-distortion theory is augmented with privacy constraints quantified through equivocation.
  • Tradeoff formulation: The U-P tradeoff region T is the set of feasible distortion-equivocation pairs, while the RDE region additionally tracks rate.For a desired distortion, the RDE formulation yields feasible rate-equivocation tuples whose projection gives U-P tradeoffs.
  • Tradeoff boundaries: For a fixed distortion D, R(D,E) is the minimal rate and Γ(D) is the maximal privacy achievable at that distortion.These functions form the rate and privacy boundaries shown in Fig. 3(b).
  • Tradeoff boundaries: Fixing any one of utility, privacy, or precision determines the feasible operating points for the other two.The framework therefore represents the database problem as a three-way tradeoff among distortion, equivocation, and rate.
  • Achievability: The achievable RDE region is obtained by matching outer bounds from converse arguments with inner bounds from a constructive coding scheme.The procedure first bounds rate and equivocation for reliable decoding at distortion D, then constructs a scheme attaining those bounds.
  • Privacy-rate distinction: The minimal-rate encoding scheme need not maximize equivocation for a given distortion, because rate and privacy can be optimized by different distributions.Maximal privacy may require additional precision for the component of the public data orthogonal to the private data.

A. Capturing the Effects of Side-Information

The paper extends the utility-privacy framework to users with correlated side information, distinguishing encoders with no side-information knowledge, statistical knowledge, or exact knowledge.

  • Side-information models: The side-information setting models auxiliary information available to the user from prior interactions or correlated external sources.The encoder may be uninformed, statistically informed, or perfectly informed about that side information.
  • Results: The side-information theorems generalize earlier RDE results and characterize the corresponding utility-privacy tradeoff region.The paper presents a new proof for achievable equivocation in this setting.
  • Statistically informed encoder: For a statistically informed encoder, quantize-and-bin coding reduces transmission using the correlation between the quantized database and the user’s side information.The rate is reduced to I(X_Kr,X_Kh;U) − I(Z;U), with I(Z;U) measuring correlation between Z^n and U^n.
  • Statistically informed encoder: The user combines the transmitted bin index with side information to reconstruct the quantized database and then the public reconstruction at distortion D.The reconstruction is lossless for U^n before producing the desired approximation of X_Kr^n.
  • Statistically informed encoder: The quantize-and-bin scheme guarantees an equivocation lower bound of H(X_Kh|U,Z) for fixed distortion D.This inner bound relies on lossless reconstruction of the quantized database from the bin index and side information.
  • Uninformed encoder: In the uninformed case, setting Z=∅ and U=X̂_Kr simplifies quantize-and-bin coding to ordinary quantization.The resulting formulation recovers the no-side-information case.

2) U-P Tradeoffs: Informed Encoder:

With an informed encoder that knows the user’s side information, the paper characterizes the RDE region using joint compression and a quantize-and-forward scheme.

  • Informed encoder: The informed-encoder theorem characterizes achievable rate-equivocation pairs for a target distortion when the encoder has perfect side-information knowledge.The characterization is expressed through a distribution involving public, private, side-information, and reconstructed variables.
  • Informed encoder: The encoder jointly compresses the database and side information before transmitting information that enables reconstruction at the user.The scheme applies when both (X_K,Z^n) are available at the encoder.
  • Quantize-and-forward: Quantize-and-forward uses binning with the user’s side information to reduce transmission and permit lossless reconstruction of the quantized public database.The transmission rate is reduced through the correlation between the encoded representation and Z.
  • Privacy guarantee: For fixed distortion D, the quantize-and-forward scheme guarantees minimal equivocation H(X_Kh|X̂_Kr,Z).The bound is established using the fact that the user can reconstruct the quantized public database from the bin index and side information.

VI. ILLUSTRATION OF RESULTS

The paper illustrates information-theoretic sanitization for categorical and numerical databases, deriving optimal mappings that characterize utility–privacy tradeoffs. The examples show how distribution-aware perturbations suppress low-probability outliers and how Gaussian outputs minimize rate and leakage for numerical data.

  • Illustration of results: The illustrations cover categorical and numerical databases using probabilistic mappings designed to achieve utility–privacy tradeoff points.The paper presents corresponding optimal coding schemes and connects them to practical privacy-preserving techniques.
  • Categorical databases: Minimizing the utility rate RU(D) for a desired distortion also maximizes equivocation EU(D), yielding the maximal privacy utility–privacy region.The categorical construction focuses on achievable distortion–equivocation pairs with maximal privacy.
  • Categorical databases: For categorical data, reverse waterfilling suppresses samples below a probability threshold, flattening the output distribution as distortion D increases.The mapping formally supports outlier suppression, aggregation, and imputation as privacy-leakage-minimizing heuristics under the model.
  • Categorical databases: Suppressed low-probability entries can retain their original uncertainty, while every published sample remains probabilistically ambiguous about its source.The mapping minimizes leakage for all samples and provides maximal privacy to entries treated as outliers relative to the utility measure.
  • Numerical databases: For Gaussian numerical databases, Gaussian reconstructed outputs minimize both rate and leakage, and the largest tradeoff region is enclosed by L(D).The privacy-maximal code therefore requires the reconstructed database to remain Gaussian; Gaussian-distributed applications can operate on sanitized data with modified parameters.
  • Numerical databases: The sanitization mechanism is irreversible except at D = 0, so the original data cannot be recovered when sanitization introduces nonzero distortion.This illustrates the lossy-compression basis of the proposed information-theoretic mechanism.

VII. CONCLUDING REMARKS

The paper develops an information-theoretic framework for trading privacy against utility across numeric and categorical data. It establishes tradeoff regions and encoding schemes for i.i.d. sources with known distributions, while identifying broader-source and strong-anonymity limitations.

  • The framework treats privacy and utility as conflicting characteristics that can be systematically traded off.
  • Rate-distortion theory yields a utility-privacy tradeoff region for i.i.d. data sources with known distributions.
  • The theory covers both numeric and categorical data and proposes privacy based on preserving existing uncertainty about hidden data.
  • The examples are an initial step toward practical approaches with precise guarantees, followed by domain-specific distributions, metrics, parameters, and test-data analysis.
  • The model remains to be generalized for non-i.i.d. sources, unknown distributions, and sources lacking strong structural properties.
  • The privacy guarantee is an average Shannon-entropy metric and may be inadequate where strong anonymity is required for every individual.

APPENDIX

The appendix proves achievability and converse bounds for quantize-and-bin coding in statistically informed and informed encoder cases. The arguments use typicality, Markov relations, convexity or concavity, and vanishing error terms to establish decodability and equivocation bounds.

  • Statistically Informed Case: The proofs derive rate and equivocation bounds using the i.i.d. assumption, Markov chains, conditioning properties, and convexity of the rate-distortion function.
  • Statistically Informed Case: The statistically informed encoder uses a quantize-and-bin scheme with rate R = I(XK; U|Z) + ǫ.
  • Statistically Informed Case: Joint typical decoding recovers the quantized sequence with decoding error tending to zero as n →∞.
  • Informed Encoder Case: The informed-case converse and equivocation proof rely on standard converse arguments, concavity, conditioning, and a Markov relation induced by the coding scheme.
  • Informed Encoder Case: For the informed encoder, the database encoder encodes both XK and Z, with the reconstructed private-public component depending on both variables.
  • Informed Encoder Case: The informed encoder also uses quantization and binning, while the decoder uses Zn and the bin index J to recover the quantized sequence.

B. Proof of (28f)

The proof establishes an entropy inequality for the quantize-and-bin construction, with an error term that vanishes as the blocklength grows. The surrounding illustration includes an input distribution and rate-leakage plots for the uninformed case.

  • The proof establishes H(XKh|U^n, Z^n) ≤ n(H(XKh|U, Z) + ǫ(n)), where ζ(n) →0 as n →∞.
  • The accompanying figures present input-versus-output distributions and rate-and-leakage results for the uninformed case.
Loading 1102.3751v4…