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.