On the Lift-Based Privacy Measures, Their Operational Meaning, and Privacy-Utility Tradeoff

Abstract

The widespread adoption of data-driven technologies has heightened concerns about the privacy of individuals, as collecting and releasing personal data creates risks of unauthorized access and sensitive inference. A common strategy to mitigate these risks is to apply data randomization before release, limiting an adversary's ability to infer the original data accurately. However, stronger privacy protection often results in reduced utility, leading to a fundamental tension known as the privacy-utility tradeoff. This thesis addresses this challenge by developing an information-theoretic framework for quantifying and controlling information leakage, with the goal of designing privacy mechanisms that offer strong protection while preserving data usability.

At the core of this framework is the concept of "lift," which measures how much an observation changes an adversary's belief about private information. In local privacy settings, this is typically controlled using symmetric bounds. However, we identify a key asymmetry in the behavior of the maximum and minimum lift, which we term "lift asymmetry." We propose a new privacy model called asymmetric local information privacy (ALIP), which allows for separate privacy budgets for minimum and maximum lift. This added flexibility enables improved utility in existing mechanisms like the watchdog mechanism and optimal random response (ORR), either by relaxing constraints on minimum lift or balancing the tradeoff more effectively.

To further improve these mechanisms, we introduce two new techniques. First, we propose subset merging, a method that enhances the utility of the watchdog mechanism by randomizing over subsets of symbols instead of treating them uniformly. Second, we introduce subset random response, which retains the privacy guarantees of ORR while dramatically reducing its computational complexity, making it scalable for large data domains.

We extend our analysis to a class of privacy measures known as lift-based semi-pointwise measures. These include variations of divergence and distance metrics and offer intermediate guarantees between strict pointwise and average-case privacy. We evaluate subset merging under these measures and propose a new method to estimate the optimal achievable utility. This method uses vertex enumeration techniques from ORR to approximate solutions for various divergence-based measures. Our results show that it achieves better utility than heuristic approaches and closely matches theoretical bounds in special cases.

The thesis also proposes a general framework to interpret tunable privacy measures based on alpha-divergence. By extending the concept of quantitative information flow (QIF) to include adversaries modeled using generalized means, we provide consistent operational interpretations for alpha-based measures, including maximal alpha-leakage and its variants. This resolves inconsistencies in earlier definitions and shows that the randomized guessing model commonly used in maximal leakage is unnecessary in this broader framework. Our results unify these measures within a single structure and establish their connection to adversarial inference strategies. We also offer, for the first time, operational meanings for Renyi divergence and Sibson mutual information, reinforcing their role in information-theoretic privacy. Show more