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.

This paper introduces a paradigm shift in the way privacy is defined, driven by a novel interpretation of the fundamental result of Dwork and Naor about the impossibility of absolute disclosure prevention. We propose a general model of utility and privacy in which utility is achieved by disclosing the value of low-entropy features of a secret X, while privacy is maintained by hiding the value of high-entropy features of X. Adopting this model, we prove that, contrary to popular opinion, it is possible to provide meaningful inferential privacy guarantees. These guarantees are given in terms of an operationally-meaningful information measure called pointwise maximal leakage (PML) and prevent privacy breaches against a large class of adversaries regardless of their prior beliefs about X. We show that PML-based privacy is compatible with and provides insights into existing notions such as differential privacy. We also argue that our new framework enables highly flexible mechanism designs, where the randomness of a mechanism can be adjusted to the entropy of the data, ultimately, leading to higher utility.

Data-driven advancements significantly contribute to societal progress, yet they also pose substantial risks to privacy. In this landscape, differential privacy (DP) has become a cornerstone in privacy preservation efforts. However, the adequacy of DP in scenarios involving correlated datasets has sometimes been questioned and multiple studies have hinted at potential vulnerabilities. In this work, we delve into the nuances of applying DP to correlated datasets by leveraging the concept of pointwise maximal leakage (PML) for a quantitative assessment of information leakage. Our investigation reveals that DP’s guarantees can be arbitrarily weak for correlated databases when assessed through the lens of PML. More precisely, we prove the existence of a pure DP mechanism with PML levels arbitrarily close to that of a mechanism which releases individual entries from a database without any perturbation. By shedding light on the limitations of DP on correlated datasets, our work aims to foster a deeper understanding of subtle privacy risks and highlight the need for the development of more effective privacy-preserving mechanisms tailored to diverse scenarios.

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.

For several decades now, safeguarding sensitive information from disclosure has been a key focus in computer science and information theory. Especially, in the past two decades, the subject of privacy has received significant attention due to the widespread collection and processing of data in various facets of society. A central question in this area is "What can be inferred about individuals from the data collected from them?"

This doctoral thesis delves into a foundational and application-agnostic exploration of the theory of privacy. The overarching objective is to construct a comprehensive framework for evaluating and designing privacy-preserving data processing systems that adhere to three essential criteria:

• Explainability. The notion of information leakage (or privacy loss) employed in this framework should be operationally meaningful. That is, it should naturally emerge from the analysis of adversarial attack scenarios. Privacy guarantees within this framework should be comprehensible to stakeholders and the associated privacy parameters should be meaningful and interpretable. 

• Robustness. The notion of information leakage employed should demonstrate resilience against a diverse array of potential adversaries, accommodating a broad range of attack scenarios while refraining from making restrictive assumptions about adversarial capabilities.

• Flexibility. The framework should offer value in a variety of contexts, catering to both highly privacy-sensitive applications and those with more relaxed privacy requirements. The notion of information leakage employed should also be applicable to various data types.

The privacy notion proposed in this thesis that aligns with all the above criteria is called pointwise maximal leakage (PML). PML is a random variable that measures the amount of information leaking about a secret random variable X to a publicly available related random variable Y. We first develop PML for finite random variables by studying two seemingly different but mathematically equivalent adversarial setups: the randomized function model and the gain function model. We then extend the gain function model to random variables on arbitrary probability spaces to obtain a more general form of PML. Furthermore, we study the properties of PML in terms of pre and post-processing inequalities and composition, define various privacy guarantees, and compare PML with existing privacy notions from the literature including differential privacy and its local variant. 

PML, by definition, is an inferential privacy measure in the sense that it compares an adversary's posterior knowledge about X with her prior knowledge. However, a prevalent misconception in the area suggests that meaningful inferential privacy guarantees are unattainable, due to an over-interpretation of a result called the impossibility of absolute disclosure prevention. Through a pivotal shift in perspective, we characterize precisely the types of disclosures that can be prevented through privacy guarantees and those that remain inevitable. In this way, we argue in favor of inferential privacy measures. 

On the more application-oriented front, we examine a common machine learning framework for privacy-preserving learning called Private Aggregation of Teacher Ensembles (PATE) using an information-theoretic privacy measure. Specifically, we propose a conditional form of the notion of maximal leakage to quantify the amount of information leaking about individual data entries and prove that the leakage is Schur-concave when the injected noise has a log-concave probability density. The Schur-concavity of the leakage implies that increased classification accuracy improves privacy. We also derive upper bounds on the information leakage when the injected noise has Laplace distribution.

Finally, we design optimal privacy mechanisms that minimize Hamming distortion subject to maximal leakage constraints assuming that (i) the data-generating distribution (i.e., the prior) is known, or (ii) the prior belongs to a certain set of possible distributions. We prove that sets of priors that contain more "uniform" distributions generate larger distortion. We also prove that privacy mechanisms that distribute the privacy budget more uniformly over the outcomes create smaller worst-case distortion. 

Att skydda känslig information mot oavsiktligt avslöjande har varit ett viktigt forskningsmål inom datavetenskap och informationsteori under de senaste decennierna. I synnerhet under de senaste två decennierna har ämnet dataintegritet fått stor uppmärksamhet, inte minst på grund av den omfattande datainsamlingen som pågår i stora delar av samhället. En central fråga inom området är "Vilka slutsatser kan dras om individer från de data som samlas in från dem?"

Denna avhandling fördjupar sig i teorin bakom dataintegritet från ett fundamentalt och tillämpningsoberoende perspektiv. Det övergripande målet är att skapa ett allsidigt ramverk för att designa och utvärdera dataintegritetsbevarande databehandlingssystem som följer tre essentiella kriterier:

• Förklarbarhet. Definitionen av informationsläckage (eller minskningen av dataintegritet) i detta ramverk bör ha en operationell betydelse, det vill säga att definitionen uppkommer naturligt från en analys av potentiella fientliga attacker. Dataintegritetsgarantier inom detta ramverk bör också vara förståeliga för intressenter, och motsvarande dataintegritetsparametrar bör vara meningsfulla och tolkningsbara.
• Robusthet. Definitionen av informationsläckage bör uppvisa motståndskraft mot en mångfald av potentiella fientliga attacker: definitionen bör vara tillämpbar på ett brett spektrum av fientliga attacker och undvika att göra restriktiva antaganden om den fientliga förmågan.
• Flexibilitet. Ramverket bör vara användbart i ett brett spektrum av tillämpningar; både i situationer där dataintegritet är av yttersta vikt, och där kraven inte är lika strikta. Definitionen av informationsläckage bör också vara applicerbart på olika datatyper.

Definitionen av dataintegritet som presenteras i denna avhandling följer kriterierna ovan och kallas punktvist maximalt läckage (PML). PML är en stokastisk variabel som mäter mängden informationsläckage från en hemlig stokastisk variabel X till en relaterad, men publik, stokastisk variabel Y. Vi börjar med att definiera PML för diskreta stokastiska variabler genom studier av två till synes olika, men matematiskt ekvivalenta, attackscenarier: den slumpmässiga funktionsmodellen och vinstfunktionsmodellen. Vi vidareutvecklar vinstfunktionsmodellen till stokastiska variabler i godtyckliga sannolikhetsrum, vilket resulterar i en mer generell form av PML. Vidare studerar vi egenskaperna för PML före och efter databehandling och funktionskomposition; definierar flera dataintegritetsgarantier; samt jämför PML med existerande dataintegritetsdefinitioner, såsom differentiell dataintegritet och dess lokala variant.

Per definition är PML ett inferentiellt dataintegritetsmått, i bemärkelsen att det jämför en fiendes information om X före och efter databehandling. En vanlig missuppfattning inom forskningsfältet är dock att meningsfulla inferentiella dataintegritetsgarantier är ouppnåeliga. Detta beror på en övertolkning av ett resultat som kallas omöjligheten att helt förebygga informationsutlämnande. Genom en grundläggande perspektivförändring kan vi precist karaktärisera de typerna av informationsutlämnande som kan förebyggas genom dataintegritetsgarantier, och de som förblir oundvikliga. Med bakgrund av detta argumenterar vi för användandet av inferentiella dataintegritetsmått.

En tillämpning vi undersöker är ett vanligt maskininlärningsramverk för dataintegritetsbevarande inlärning som kallas Privat Aggregation av Lärarensembler (eng: Private Aggregation of Teacher Ensambles (PATE)), genom ett informationsteoretiskt dataintegritetsmått. Specifikt föreslår vi en betingad form av maximalt läckage för att kvantifiera mängden informationsläckage från individuella datapunkter, och visar att läckaget är Schur-konkavt när det tillagda bruset har en log-konkav sannolikhetsfördelning. Läckagets Schur-konkavitet innebär att ökad klassificeringsprestanda stärker dataintegriteten. Vi härleder också övre gränser på informationsläckaget när det tillagda bruset följer en Laplacefördelning. 

Till sist designar vi optimala dataintegritetsmekanismer som minimerar Hammingdistorsionen i situationer där det maximala läckaget är begränsat, under antagande att (i) a-priori-fördelningen är känd, (ii) a-priori-fördelningen tillhör en given mängd av möjliga sannolikhetsfördelningar. Vi visar att de mängder av a-priori-fördelningar som innehåller fler uniforma sannolikhetsfördelningar genererar större distorsion. Vi visar också att dataintegritetsmekanismer som distribuerar dataintegritetsbudgeten mer uniformt över utfallen ger upphov till mindre distorsion i värsta fall.

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.

We introduce a privacy measure called pointwise maximal leakage, generalizing the pre-existing notion of maximal leakage, which quantifies the amount of information leaking about a secret X by disclosing a single outcome of a (randomized) function calculated on X. Pointwise maximal leakage is a robust and operationally meaningful privacy measure that captures the largest amount of information leaking about X to adversaries seeking to guess arbitrary (possibly randomized) functions of X, or equivalently, aiming to maximize arbitrary gain functions. We study several properties of pointwise maximal leakage, e.g., how it composes over multiple outcomes, how it is affected by pre and post-processing, etc. Furthermore, we propose to view information leakage as a random variable which, in turn, allows us to regard privacy guarantees as requirements imposed on different statistical properties of the information leakage random variable. We define several privacy guarantees and study how they behave under pre-processing, post-processing and composition. Finally, we examine the relationship between pointwise maximal leakage and other privacy notions such as local differential privacy, local information privacy, f-information, and so on. Overall, our paper constructs a robust and flexible framework for privacy risk assessment whose central notion has a strong operational meaning which can be adapted to a variety of applications and practical scenarios.

Pointwise maximal leakage (PML) is an operationally meaningful privacy measure that quantifies the amount of information leaking about a secret X to a single outcome of a related random variable Y. In this paper, we extend the notion of PML to random variables on arbitrary probability spaces. We develop two new definitions: First, we extend PML to countably infinite random variables by considering adversaries who aim to guess the value of discrete (finite or countably infinite) functions of X. Then, we consider adversaries who construct estimates of X that maximize the expected value of their corresponding gain functions. We use this latter setup to introduce a highly versatile form of PML that captures many scenarios of practical interest whose definition requires no assumptions about the underlying probability spaces.

Pointwise maximal leakage (PML) is a robust and operationally meaningful privacy measure that quantifies the amount of information leaking about a secret X by disclosing a single outcome of a (randomized) function calculated on X. In this paper, we define a new privacy measure called event maximal leakage (EML), which generalizes PML by quantifying the amount of information leaking about X to arbitrary events. Then, we use our new privacy measure to define a new probabilistic privacy guarantee called (ϵ, δ)-EML. We study the data-processing and composition properties of (ϵ, δ)-EML and other privacy guarantees, where our goal is to understand whether or not they are closed under pre- and post-processing, and how they change as a result of adaptively composing privacy mechanisms.