This paper explores the implications of guaranteeing privacy by imposing a lower bound on the information density between the private and the public data. We introduce a novel and operationally meaningful privacy measure called pointwise maximal cost (PMC) and demonstrate that imposing an upper bound on PMC is equivalent to enforcing a lower bound on the information density. PMC quantifies the information leakage about a secret to adversaries who aim to minimize non-negative cost functions after observing the outcome of a privacy mechanism. When restricted to finite alphabets, PMC can equivalently be defined as the information leakage to adversaries aiming to minimize the probability of incorrectly guessing randomized functions of the secret. We study the properties of PMC and apply it to standard privacy mechanisms to demonstrate its practical relevance. Through a detailed examination, we connect PMC with other privacy measures that impose upper or lower bounds on the information density. These are pointwise maximal leakage (PML), local differential privacy (LDP), and (asymmetric) local information privacy. In particular, we show that a mechanism satisfies LDP if and only if it has both bounded PMC and bounded PML. Overall, our work fills a conceptual and operational gap in the taxonomy of privacy measures, bridges existing disconnects between different frameworks, and offers insights for selecting a suitable notion of privacy in a given application.

We analyze the privacy guarantees of the Laplace mechanism releasing the histogram of a dataset through the lens of pointwise maximal leakage (PML). While differential privacy is commonly used to quantify the privacy loss, it is a context-free definition that does not depend on the data distribution. In contrast, PML enables a more refined analysis by incorporating assumptions about the data distribution. We show that when the probability of each histogram bin is bounded away from zero, stronger privacy protection can be achieved for a fixed level of noise. Our results demonstrate the advantage of context-aware privacy measures and show that incorporating assumptions about the data can improve privacy-utility tradeoffs.

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.

Plattformiseringen av varor och tjänster har gjort insamling och bearbetning av data till en lukrativ verksamhet. I takt med denna insamling av konsumentmikrodata uppstår ett hot mot individers dataintegritet som inte kan underskattas. Mot bakgrund av detta hot har dataintegritet som en egenskap hos databehandlingssystem vuxit fram som en term för att beskriva risken att algoritmer avslöjar individers känsliga egenskaper för tredje part utan deras uttryckliga samtycke. Inom datavetenskap och angränsande områden har detta lett till forskningsinsatser för att utveckla matematiska ramverk som kan kvantifiera detta informationsläckage och erbjuda verktyg för att motverka oönskade avslöjanden. Sådana ramverk syftar till att möjliggöra garanterad dataintegritet för algoritmer och databehandlingssystem, det vill säga garantier som framträder som en matematisk egenskap hos en algoritm. Ett sådant ramverk är punktvist maximalt läckage (PML). PML är ett informationsteoretiskt mått på dataintegritet som kvantifierar det värsta fallet av informationsläckage av privat data till en angripare med godtycklig sidoinformation. En fördel med PML är dess operationella definition baserad på hotmodeller. Specifikt härleds PML genom att analysera hur effektivt en angripare kan härleda privata egenskaper från givna observationer eller databasstatistik. Detta sätt att definiera dataintegritet ger en matematiskt precis innebörd, då alla antaganden om angriparna görs explicita i hotmodellen. Vidare har det nyligen visats att integritetsgarantier enligt PML också erbjuder en stark tolkning av integritetsparametern i termer av minimumentropin hos dold och eventuellt avslöjad information. Denna avhandling tillhandahåller grundläggande metoder för integritetsanalys och mekanismdesign inom PML-ramverket. För det första etablerar vi fundamentala samband mellan integritetsmått som använder informationsdensitet för att mäta informationsläckage. Vi visar hur förhållandet mellan övre och nedre gränser för informationstäthet ger nya kopplingar mellan lokal informationsintegritet, asymmetrisk lokal informationsintegritet, PML och lokal differentiell dataintegritet. Vi tillämpar också dessa resultat för mekanismdesign för dataintegritet. För det andra undersöker vi avvägningen mellan dataintegritet och nytta för PML och tillhandahåller optimala mekanismer för en generell klass av konvexa nyttokriterier, givet att den datagenererande fördelningen av privat data är perfekt känd. Genom att använda verktyg från konvex analys och majoriseringsteori härleder vi slutna uttryck för optimala mekanismer under vissa parameterkonfigurationer. Vidare presenterar vi ett linjärt program för att beräkna optimala mekanismer i allmänhet. Eftersom perfekt kännedom om den datagenererande fördelningen sällan är möjlig i praktiken, föreslår vi ett ramverk för PML-integritetsanalys och -mekanismdesign baserat på empiriska skattningar av à-priorifördelningar. Vi introducerar begreppen lokal-läckagekapacitet och -läckagekänslighet, vilka underlättar både integritetsanalys och mekanismdesign under à-priorifördelningsosäkerhet. Vi visar att lokal läckagekapacitet fungerar som en Lipschitzkonstant för PML med avseende på ℓ1-avståndet mellan à-priorifördelningar. Med hjälp av stora avviksgränser härleder vi distributionsoberoende (ε, δ)-PML-garantier och presenterar en optimal binär mekanism. Dessutom visar vi att mekanismdesign under osäker à-priorifördelning kan reduceras till ett konvext optimeringsproblem med linjära begränsningar och tillämpar våra metoder för att analysera läckageegenskaper hos standardmekanismer såsom Laplace- och Gaussmekanismerna. Avslutningsvis undersöker vi sambandet mellan PML och starka databehandlingsolikheter (SDPI) för Rényi- och Hellingerdivergenser. Vi tillhandahåller villkor under vilka databehandlingsolikheten för Rényidivergenser uppfylls med likhet och analyserar kontraktionsegenskaper hos begränsade mängder av à-priorifördelningar via f-divergensolikheter. I synnerhet härleder vi en förbättrad version av Pinskers olikhet med hjälp av den gemensamma bildmengd tekniken, och utökar Binettes optimala omvända Pinskers olikhet till en tvärkanalsinställning, vilket möjliggör att förfina SDPI:er till specifika indatafördelningar. Vi använder dessa resultat för att kvantifiera förstärkningen av lokal differentiell dataintegritet för en kanal som uppfyller ett PML-villkor, men inte nödvändigtvis något villkor för lokal differentiell dataintegritet.

Data publishing under privacy constraints can be achieved with mechanisms that add randomness to data points when released to an untrusted party, thereby decreasing the data's utility. In this paper, we analyze this privacy-utility tradeoff for the pointwise maximal leakage (PML) privacy measure and provide optimal privacy mechanisms for a general class of convex utility functions. PML was recently proposed as an operationally meaningful privacy measure based on two equivalent threat models: An adversary guessing a randomized function and an adversary aiming to maximize a general gain function. We prove a cardinality bound, showing that output alphabets of optimal mechanisms in this context need not to be larger than the size of their inputs. Then, we characterize the optimization region as a (convex) polytope. We derive closed-form optimal privacy mechanisms for arbitrary priors in the high privacy regime (when the privacy parameter is sufficiently small) and uniform priors for all ranges of the privacy parameter using tools from convex analysis. Furthermore, we present a linear program that can compute optimal mechanisms for PML in a general setting. We conclude by demonstrating the performance of the closed-form mechanisms through numerical simulations.

We examine the relationship between privacy metrics that utilize information density to measure information leakage between a private and a disclosed random variable. Firstly, we prove that bounding the information density from above or below in turn implies a lower or upper bound on the information density, respectively. Using this result, we establish new relationships between local information privacy, asymmetric local information privacy, pointwise maximal leakage and local differential privacy. We further provide applications of these relations to privacy mechanism design. Secondly, we provide equivalence statements of lower bounds on information density and risk-averse adversaries. More specifically, we prove an equivalence between a guessing framework and a cost-function framework that both result in the same lower bound on the information density.