Mechanisms and Methods in the Pointwise Maximal Leakage Framework

QC 20250513

Abstract

The platformization of goods and services has turned data collection and processing into a lucrative business. Along with this collection of consumer microdata comes a threat to individual privacy that cannot be overstated. Given this threat, privacy as a property of data processing systems has emerged as a term for describing the risk of algorithms exposing individuals’ sensitive features to third parties without their explicit consent. In computer science and related fields, this has led to research into mathematical frameworks that can quantify this privacy leakage and offer tools to circumvent unwanted disclosure. Such frameworks aim to enable provable privacy guarantees for algorithms and data processing systems—that is, privacy guarantees that emerge as a mathematical property of an algorithm.

One such framework is pointwise maximal leakage (PML). PML is an information-theoretic privacy measure that quantifies the worst-case leakage of private data to an adversary with arbitrary side information. One benefit of PML is its operational definition based on threat models. In particular, PML is derived by analyzing how effectively an adversary can infer private features from given observations or database statistics. This way of defining privacy carries a precise meaning, as all assumptions about the considered adversaries are made explicit in the threat model. Furthermore, it has recently been shown that privacy guarantees based on PML also offer a strong interpretation of the privacy parameter in terms of the min-entropy of hidden and possibly disclosed features.

This thesis provides fundamental methods for privacy analysis and mechanism design in the PML framework. First, we establish foundational relationships between privacy measures that utilize information density to quantify information leakage. We show how the relation between upper and lower bounds on information density yields novel connections between local information privacy, asymmetric local information privacy, PML, and local differential privacy. We also apply these results to privacy mechanism design.

Second, we study the privacy–utility tradeoff for PML and provide optimal privacy mechanisms for a general class of convex utility functions, assuming that the data-generating distribution of the private data is perfectly known. Leveraging tools from convex analysis and majorization theory, we derive closed-form solutions for optimal mechanisms under certain parameter configurations. Furthermore, we present a linear program for computing optimal mechanisms in a general setting.

Since perfect knowledge of the data-generating distribution is rarely attainable in practice, we propose a framework for PML privacy assessment and mechanism design under empirical prior distribution estimates. We introduce the concepts of local leakage capacity and leakage sensitivity, which facilitate both privacy assessment and mechanism design under prior-distribution uncertainty. We demonstrate that local leakage capacity acts as a Lipschitz constant for PML with respect to the ℓ1-distance between prior distributions. Using large deviation bounds, we derive distribution-independent (ε, δ)-PML guarantees and present an optimal binary mechanism. Moreover, we show that designing mechanisms with uncertain priors reduces to a linearly constrained convex optimization problem, and we apply our methods to assess the leakage properties of standard mechanisms like the Laplace and Gaussian mechanisms.

Finally, we investigate the connection between PML and strong data processing inequalities (SDPIs) for Rényi and Hellinger divergences. We provide conditions under which the data processing inequality for Rényi divergences holds with equality and analyze contraction properties of restricted sets of prior distributions via $f$-divergence inequalities. In particular, we derive an improved Pinsker’s inequality using the joint range technique and extend Binette's optimal reverse Pinsker's inequality to a cross-channel setting, allowing for the refinement of SDPIs to specific sets of input distributions. We use these findings to quantify the local differential privacy amplification of a channel satisfying a PML constraint, even when it does not meet any local differential privacy constraint.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-363308