arXiv:2605.21185v1 [cs.CR] 20 May 2026
Information Leakage Envelopes Sara Saeidian
Carlos Pinzón
Catuscia Palamidessi
Inria, Palaiseau, France KTH Royal Institute of Technology, Stockholm, Sweden [email protected]
Inria, École Polytechnique Palaiseau, France [email protected]
Inria, École Polytechnique Palaiseau, France [email protected]
Abstract—We study privacy guarantees in the framework of pointwise maximal leakage (PML) that satisfy two requirements: they are robust under post-processing and upper bound the failure probability, i.e., the probability that the information leakage exceeds a given threshold. We first examine two candidate definitions inspired by (approximate) differential privacy and show that neither one satisfies both requirements simultaneously. We then introduce the notion of the PML envelope, which quantifies the largest amount of information leakage about a secret after arbitrary post-processing of a mechanism’s output. By construction, the PML envelope satisfies both requirements. We discuss basic structural properties of the envelope, such as monotonicity, and derive general upper and lower bounds. We further analyze the envelope for two widely used privacy mechanisms: the PML-extremal mechanisms in the high-privacy regime and randomized response. Overall, this work establishes the PML envelope as a natural and operationally meaningful definition for providing privacy guarantees that are preserved under arbitrary downstream transformations.
I. I NTRODUCTION The introduction of differential privacy (DP) [1] marked a major advance in privacy-preserving technologies. Rather than focusing on defenses against specific privacy attacks, such as re-identification or attribute disclosure, DP frames privacy as an inherent property of a data-processing system. Central to this perspective is the concept of privacy loss [2], defined as Lx,x′ (Y ) := log
PY |X=x (Y ) , PY |X=x′ (Y )
where x and x′ denote two possible values of the sensitive input (the secret) and PY |X is the mechanism that produces the released information Y . The privacy loss random variable captures how much evidence an observation Y provides for distinguishing between x and x′ . The original formulation of DP, known as ε-DP, imposes a uniform upper bound on the privacy loss by a constant ε > 0 across all relevant pairs of inputs, that is, Lx,x′ (Y ) ≤ ε [1]. This strong guarantee often requires adding noise with Laplace or geometric distributions. While these mechanisms provide effective privacy protection, Gaussian noise is often more appealing from a statistical standpoint. The faster tail decay of the Gaussian distribution typically translates into improved utility, and properties such as closedness under convolution The work of Sara Saeidian was supported by the Swedish Research Council (VR) under grant 2024-06615. The work of Catuscia Palamidessi was supported by the ELSA project in the HORIZON EUROPE Framework Programme (project number 101070617).
simplify the theoretical analysis (since the sum of Gaussians remains Gaussian). These properties motivated the search for relaxations of ε-DP that allow the use of Gaussian noise. A natural way to relax ε-DP is to allow the privacy loss to exceed ε with a small probability. This idea led to the notion of probabilistic DP [3], which requires P{Lx,x′ (Y ) > ε} ≤ δ for some δ ∈ (0, 1). Despite its intuitive appeal, this definition did not gain widespread use due to a fundamental limitation: probabilistic DP is not closed under post-processing. That is, an adversary may apply a function to the output of a mechanism satisfying probabilistic DP (without access to the secret) to produce a new outcome that no longer satisfies the original guarantee. Closedness under post-processing is often treated as an axiom for privacy definitions and is motivated by the data-processing inequality in information theory [4]. Intuitively, more processing cannot increase the information available about the secret, and therefore should preserve privacy guarantees. As a result, probabilistic DP was largely set aside in favor of approximate differential privacy (ADP), also known as (ε, δ)-DP. A mechanism satisfies (ε, δ)-DP if PY |X=x (A) ≤ eε PY |X=x′ (A) + δ,
(1)
for all (measurable) sets A. This definition is closed under post-processing, accommodates the use of Gaussian noise, and also enables advanced composition [5]. The parameter δ ∈ (0, 1) in approximate differential privacy is often informally interpreted as restricting the failure probability at level ε, i.e., P{Lx,x′ (Y ) > ε}. This interpretation is, however, somewhat loose. One can show that δ merely provides a lower bound on this probability, and in fact, [6] constructed an example in which P{Lx,x′ (Y ) > ε} was much larger than the δ in ADP. Instead, the parameter δ in ADP upper bounds the failure probability at larger thresholds, such as 2ε or, more generally, kε (see (4) for the precise statement). Note that while a constant-factor increase in δ is generally harmless (since δ is chosen to be cryptographically small), a constant-factor increase in ε exponentially weakens the privacy guarantee as (1) depends on eε . Interestingly, the difficulties associated with defining relaxed privacy guarantees based on a probability of failure are not unique to DP, but have been observed in a different framework based on a privacy measure called pointwise maximal leakage (PML) [7]. PML is a measure with several attractive
properties. Privacy guarantees based on PML allow the release of population-level features of the data while protecting its nuanced and instance-dependent features [8]. Moreover, connections between PML-based privacy and DP have been established: ε-DP is equivalent to bounding the PML of every record in a database under all product distributions, i.e., distributions under which records are independent [8]. The PML framework is built around a central random quantity, the information leakage random variable, which can be expressed as ℓ(X → Y ) = log max x
PX|Y (x | Y ) , PX (x)
where PX|Y is the posterior distribution of X given Y . Different notions of privacy correspond to placing different restrictions on this quantity. In particular, the guarantee known as ε-PML imposes a uniform upper bound on the information leakage, in direct analogy with ε-DP. In [7], the authors proposed a relaxation of ε-PML based on bounding the failure probability at level ε, that is P{ℓ(X → Y ) > ε}. However, it turns out that much like probabilistic DP, this relaxation is not closed under post-processing. To address this issue, the authors introduced an alternative privacy guarantee based on bounding the information leaked to events (i.e., subsets of the output space). This notion, however, is not directly comparable to the failure probability: depending on the setup, either quantity may dominate the other [7]. In this paper, we undertake the task of defining a relaxation of ε-PML that satisfies two desirable properties: (i) the slack parameter δ should provide an upper bound on the failure probability at level ε, and (ii) the resulting privacy guarantee should be closed under post-processing. As the preceding discussion illustrates, existing relaxations typically satisfy one of these properties, and achieving both properties simultaneously appears to be non-trivial. A. Contributions We first examine two relaxations of ε-PML inspired by ADP. Although ADP itself does not satisfy property (i), this investigation is nevertheless informative, as it reveals the types of PML-based definitions that arise when one follows the ADP design philosophy. Of the two candidate definitions, the first again fails to be post-processing safe (Theorem 1). The second is post-processing safe, but does not admit a clear or consistent relationship with the failure probability. Consequently, neither definition satisfies both properties (i) and (ii). Our main contribution is introducing the concept of the PML envelope. The key idea is to evaluate the failure probability after all possible downstream transformations, instead of just at the original output Y ; in other words, to “close” the failure probability. First, we define δc (ε) := sup P{ℓ(X → Z) > ε}, Z
ε > 0,
where the supremum is over all deterministic and randomized functions Z of Y . This quantity represents the largest probability that the information leakage exceeds ε after arbitrary post-processing. The PML envelope is then defined as εc (δ) := inf{ε > 0 : δc (ε) ≤ δ},
δ ∈ (0, 1),
that is, the smallest leakage threshold ε for which the closed failure probability is at most δ. By definition, the PML envelope satisfies both properties (i) and (ii) above. We provide equivalent characterizations of εc (δ) in terms of the cumulative distribution function (CDF) of the information leakage random variable ℓ(X → Y ) (Theorem 2). We also establish basic properties of εc , including monotonicity and lower semicontinuity (Lemma 1). In general, computing the PML envelope exactly may be difficult. For this reason, we derive general upper and lower bounds on εc . The upper bound (Theorem 3) is expressed in terms of the multiplicative Bayes capacity [9] (also known as maximal leakage [10]), which is a well-studied quantity in the quantitative information flow literature [11]. Lower bounds are obtained by restricting the class of admissible post-processings. In particular, we derive a lower bound based on binary post-processings, which is simple and efficiently computable. This lower bound coincides with the event-based privacy guarantee introduced in [7]; we discuss this connection in detail in Appendix C. Finally, we illustrate how the PML envelope can be computed and bounded by analyzing two canonical mechanisms. The first is the class of PML-extremal mechanisms in the high-privacy regime [12]. These mechanisms are the utilityoptimal solutions to a broad class of optimization problems under the ε-PML constraint with sufficiently small ε > 0. For these mechanisms, we characterize the envelope exactly (Theorem 4) and show that εc (δ) = ε for all δ ∈ (0, 1). The second is the randomized response mechanism [13], a standard and widely used tool for guaranteeing local differential privacy [14]. Randomized response is a natural benchmark due to its simplicity, in particular, its symmetric structure, as well as its widespread use. For this mechanism, we derive upper and lower bounds on the PML envelope (Theorem 5). Comparing these bounds to the corresponding ADP guarantees of randomized response shows that the two frameworks can behave quite differently, with no consistent relationship in general. This is not surprising because in the PML envelope, δ represents the failure probability, whereas in ADP it appears as an additive slack parameter. II. BACKGROUND A. Notation Uppercase letters denote random variables, lowercase letters denote their realizations, and calligraphic letters denote sets. All sets are assumed to be finite. We use X to denote a random variable containing sensitive information, also referred to as the secret. Its probability distribution is denoted by PX , and its domain by X . A privacy mechanism (or simply, a mechanism) is specified by a conditional probability distribution PY |X ,
which takes X as input and produces an output Y with domain Y and (marginal) distribution PY . The joint distribution of (X, Y ) is denoted by PXY . Random variables X, Y , and Z are said to form a Markov chain X − Y − Z if X and Z are conditionally independent given Y , that is, PXZ|Y = PX|Y × PZ|Y . We write PZ|X = PZ|Y ◦ PY |X to denote marginalization, meaning that X PZ|X=x (z) = PZ|Y =y (z) PY |X=x (y), x ∈ X , z ∈ Z.
Then, PY |X satisfies (ε, δ)-DP for all δ ∗ (ε) ≤ δ < 1. It is not difficult to see that δ ∗ can also be expressed in the following more intuitive form [19, Lemma 2.8]:
For a set E, 1E denotes its indicator function. For a positive integer k, we write [k] = {1, . . . , k}.
Intuitively, the term
y∈Y
δ ∗ (ε, PY |X ) = max′ EY ∼PY |X=x max 0, 1 −
exp(ε) (3) x,x exp(Lx,x′ (Y )) exp(ε) = max′ EY ∼PY |X=x 1{L ′ >ε} (Y ) 1 − . x,x x,x exp(Lx,x′ (Y ))
1−
B. Differential Privacy The original definition of DP states that an adversary should not be able to distinguish between neighboring datasets, i.e., databases that differ in a single record, based on the statistics released from each [1, 2]. Later, DP was extended to decentralized settings, where data is perturbed before collection. This variant is known as local differential privacy (LDP) [15, 16]. In this work, we adopt the local model for all DP definitions. This choice is made without loss of generality, since switching between the two models amounts to redefining what it means for two inputs to be “neighbors.” By working in the local model, we abstract away the structure of the secret and instead focus on our main objective: to analyze how various definitions behave under post-processing. Given x, x′ ∈ X , let Lx,x′ (Y ) := log
PY |X=x (Y ) , PY |X=x′ (Y )
denote the privacy loss random variable of DP [2]. The simplest DP definition imposes a uniform bound on this loss. Definition 1 (Pure DP [1]). Let ε > 0. A privacy mechanism PY |X is said to satisfy ε-DP if Lx,x′ (y) ≤ ε for all x, x′ ∈ X and all y ∈ Y. A standard relaxation of pure DP, known as approximate DP (ADP) [17], allows an additive slack δ ∈ (0, 1) in the event-wise comparison of the conditional distributions. Definition 2 (Approximate DP [2]). Let ε > 0 and δ ∈ (0, 1). A privacy mechanism PY |X is said to satisfy (ε, δ)-DP if for all x, x′ ∈ X and all sets E ⊂ Y we have PY |X=x (E) ≤ eε PY |X=x′ (E) + δ.
(2)
The common interpretation of (ε, δ)-DP is that it allows the privacy guarantees of ε-DP to fail with probability δ. However, as pointed out in [6], this interpretation is misleading: the parameter δ is, in fact, a lower bound on the worst-case failure probability. To demonstrate this, we find the smallest δ that satisfies (2) for a fixed ε. This function, called the privacy profile [18] and denoted by δ ∗ (ε, PY |X ), can be expressed as ε ′ (E) . δ ∗ (ε, PY |X ) = max max P (E) − e P Y |X=x Y |X=x ′ x,x ∈X E⊂Y
exp(ε) , exp(Lx,x′ (y))
is a penalty applied to outcomes y with privacy loss larger than ε. The greater the deviation of privacy loss from ε, the larger this penalty becomes, reflecting that such outcomes contribute more significantly to the overall privacy risk. Observe that exp(ε) ≤ 1 on the set {Lx,x′ > ε}, so we have 0 ≤ 1 − exp(L x,x′ (y)) h i δ ∗ (ε, PY |X ) ≤ max E 1 (Y ) Y ∼P Y |X=x L >ε ′ { } ′ x,x ∈X
x,x
= max PY |X=x {Lx,x′ (Y ) > ε} . ′ x,x ∈X
The quantity maxx,x′ PY |X=x {Lx,x′ (Y ) > ε} represents the worst-case failure probability of DP, that is, the (maximum) probability that the privacy loss exceeds ε. Hence, the above derivation shows that the value of δ in ADP merely lower bounds this quantity. It is nevertheless true that (ε, δ)-DP implies the weaker tail bound PY |X=x Lx,x′ (Y ) > 2ε ≤
δ , 1 − e−ε
for all x, x′ [20, Lemma 3.3] (see also [21]). More generally, (ε, δ)-DP implies max′ PY |X=x Lx,x′ (Y ) > kε ≤ x,x
δ 1 − e−(k−1)ε
,
(4)
for all integers k ≥ 2. While some recent works have taken care to be more precise in their description of ADP, for instance, by stating that ADP restricts the failure probability up to a scaling of the parameters, the misconception remains widespread, especially in more applied contexts where the focus is not on the theoretical nuances. The above discussion naturally raises the question of whether we could define a DP variant by explicitly upper bounding the failure probability. Such a definition was, in fact, proposed by Machanavajjhala et al. [3] and is known as probabilistic DP. Definition 3 (Probabilistic DP [3]). Let ε > 0 and δ ∈ (0, 1). A privacy mechanism PY |X is said to satisfy (ε, δ)-probabilistic DP if for all x, x′ ∈ X we have PY |X=x {Lx,x′ (Y ) > ε} ≤ δ. While probabilistic DP is arguably more intuitive than ADP, it is rarely used in practice. This is primarily because
probabilistic DP may not be preserved after post-processing [6, 22], in contrast to ADP, which is post-processing safe [2]. This property has contributed to ADP becoming the de facto standard in the literature. In the following section, we discuss similar challenges in the framework of pointwise maximal leakage.
the subscript and write i(x; y) for information density and ℓ(X → y) or simply ℓ(y) for PML. The joint distribution PXY is said to satisfy ε-PML with ε > 0 if ℓ(X → y) ≤ ε for all y ∈ Y. In [7], the authors also introduced a relaxation of ε-PML by imposing an upper bound on the tail of ℓ(X → Y ).1
C. Pointwise Maximal Leakage
Definition 5 (Probabilistic PML). Let ε > 0 and δ ∈ (0, 1). The joint distribution PXY is said to satisfy (ε, δ)-probabilistic PML if PY {ℓ(X → Y ) > ε} ≤ δ.
PML [7] is a recent notion of privacy defined using concepts from quantitative information flow [11]. PML quantifies the inference risk posed by a broad class of adversaries. Its threat model can be described as follows: consider an adversary who seeks to maximize a non-negative gain function g by producing a guess W of the private variable X. The gain function encodes the adversary’s objective and can capture a wide range of privacy attacks, including membership and attribute inference [7]. For an output y ∈ Y, PML measures information leakage as the ratio between the adversary’s expected gain after observing y and the expected gain before observing y. Then, to obtain a robust and attack-agnostic notion of leakage, this ratio is maximized over all nonnegative gain functions. Formalizing this idea leads to the following definition for PML. Definition 4 (PML [7]). Suppose X ∼ PX and let Y be the random variable induced by the mechanism PY |X . The pointwise maximal leakage from X to y ∈ Y is defined as ℓPXY (X → y) := log sup g
sup E[g(X, W ) | Y = y]
PW |Y
maxw′ ∈W E[g(X, w′ )]
, (5)
where PW |Y is the conditional distribution of the adversary’s guess W given Y . The supremum is over all non-negative measurable functions g. In this work, both X and Y are assumed to be finite-valued. Under this assumption, it was shown in [7] that PML takes the simpler form PX|Y =y (x) PY |X=x (y) = log max , x∈X x∈X PX (x) PY (y)
ℓPXY (X → y) = log max
where PX|Y denotes the posterior distribution of X given Y . It is straightforward to see that PML satisfies the bounds 0 ≤ ℓPXY (X → y) ≤ log
1 , minx∈X PX (x)
(6)
for all y ∈ Y. In the information theory literature, the quantity PXY (x, y) iPXY (x; y) = log , PX (x)PY (y)
x ∈ X , y ∈ Y,
is commonly referred to as the information density of PXY . PML can also be expressed as ℓPXY (X → y) = max iPXY (x; y). x∈X
Note that, unlike DP, PML depends on the prior distribution PX and is therefore a property of the joint distribution PXY . When the joint distribution is clear from context, we omit
Much like probabilistic LDP, probabilistic PML is not closed under post-processing. To illustrate this, below we give an example similar to [7, Example 7]. Example 1. Let X be uniformly distributed on X = [4]. Consider the privacy mechanism 0 0 0.5 0.5 0 0.5 0.5 0 , (7) PY |X = 0 0.2 0.4 0.4 0.2
0
0.4
0.4
where (PY |X )ij = PY |X=i (j). The outcomes have information leakage ℓPXY (X → 1) = ℓPXY (X → 2) = log 4, 10 ℓPXY (X → 3) = ℓPXY (X → 4) = log . 9 1 Since PY (1) = PY (2) = 20 , PXY satisfies (log 10 9 , 0.1)probabilistic PML. Now, let Z = h(Y ), where ( 1 if y ∈ {1, 3}, h(y) = 2 if y ∈ {2, 4},
The outcomes of Z are equiprobable and have information leakage ℓPXZ (X → 1) = ℓPXZ (X → 2) = log 65 . Since 6 10 5 > 9 , PXZ = PZ|Y ◦ PXY does not satisfy the original guarantee of (log 10 9 , 0.1)-probabilistic PML. In light of Example 1, we ask: What alternative definitions can reconcile PML-based privacy guarantees with the postprocessing requirement? We explore answers to this question in the subsequent sections. III. T WO C ANDIDATE D EFINITIONS OF A PPROXIMATE PML As a first step, we examine two candidate definitions of approximate PML, inspired by ADP. In particular, we define analogues of (3) by replacing the DP privacy loss with either the information leakage random variable or the information density. Given ε > 0, define exp(ε) := ψ1 (ε, PXY ) EY ∼PY max 0, 1 − exp(ℓ(Y )) 1 The function ℓ(X → y) is defined pointwise for each y ∈ Y. Consequently, ℓ(X → Y ) is a random variable induced by Y .
= EY ∼PY 1{ℓ>ε} (Y ) 1 −
exp(ε) exp(ℓ(Y ))
,
and := max EY ∼PY |X=x max 0, 1 −
exp(ε) x exp(i(x; Y )) exp(ε) = max EY ∼PY |X=x 1{i(x;·)>ε} (Y ) 1 − . x exp(i(x; Y )) Both definitions follow the same general pattern: they assign a penalty to outcomes where the information leakage ℓ(y) or the information density i(x; y) exceeds the threshold ε. Note exp(ε) ≤ 1 when ℓ(y) > ε, so ψ1 lower bounds that 0 ≤ 1 − exp(ℓ(y)) the PML failure probability PY {ℓ(Y ) > ε}. Despite the parallelism in their expressions, these two definitions behave differently under post-processing: ψ1 is not post-processing safe, whereas ψ2 is. Theorem 1. Let ε > 0. (i) There exist random variables X, Y, Z satisfying the Markov chain X − Y − Z such that ψ1 (ε, PZ|Y ◦ PXY ) > ψ1 (ε, PXY ). (ii) For all random variables X, Y, Z satisfying the Markov chain X − Y − Z we have ψ2 (ε, PZ|Y ◦ PXY ) ≤ ψ2 (ε, PXY ). Proof: (i) It suffices to construct an example where ψ1 (ε, PZ|Y ◦ PXY ) > ψ1 (ε, PXY ). Recall the setup of Example 1. Setting ε = log 10 9 , a direct calculation yields 13 2 ψ1 (ε, PXY ) = < = ψ1 (ε, PXZ ). 180 27 Hence, ψ1 can increase under post-processing. (ii) Our argument mirrors the standard proof of postprocessing for ADP. Consider the Markov chain X − Y − Z. Fix an arbitrary x ∈ X and observe that exp(ε) EZ∼PZ|X=x 1{i(x;·)>ε} (Z) 1 − exp(i(x; Z)) X exp(ε) = 1− PZ|X=x (z) exp(i(x; z)) z:i(x;z)>ε
X z:i(x;z)>ε
PZ|X=x (z) − eε
X
PZ (z)
z:i(x;z)>ε
= PZ|X=x {z : i(x; z) > ε} − eε PZ {z : i(x; z) > ε}. Thus, to prove that ψ2 does not increase under postprocessing, it suffices to show that PZ|X=x (A) − eε PZ (A) ≤ ψ2 (ε, PXY ), for all x ∈ X and arbitrary sets A ⊆ Z. Indeed, for each set A ⊆ Z we have PZ|X=x (A) − eε PZ (A)
X y∈Y
≤
ψ2 (ε, PXY )
=
=
≤
PZ|Y =y (A) PY |X=x (y) − eε PY (y)
X y: i(x;y)>ε
X y: i(x;y)>ε
PZ|Y =y (A) PY |X=x (y) − eε PY (y) PY |X=x (y) − eε PY (y)
exp(ε) = 1− PY |X=x (y) exp(i(x; y)) y: i(x;y)>ε exp(ε) = EY ∼PY |X=x 1{i(x;·)>ε} (Y ) 1 − exp(i(x; Y )) X
≤ ψ2 (ε, PXY ). Thus, Theorem 1 establishes that ε-PML can be relaxed with an additive parameter such that the resulting definition is closed under post-processing. It is straightforward to see that ψ2 can be written as ψ2 (ε, PXY ) = max max PY |X=x (E) − eε PY (E) . x∈X E⊂Y
Although ψ2 is closed under post-processing, it does not provide a suitable proxy for the failure probability PY {ℓ(Y ) > ε}, since neither quantity bounds the other one in general. To illustrate this, consider again the mechanism PY |X in (7). We have PY {ℓ(Y ) > log 10 9 } = PY {ℓ(Y ) > log 3} = 0.1, while at the same time, 13 = ψ2 log 10 9 , PXY . 90 In the next sections, we take a different approach and focus on directly “closing” the tail probability PY {ℓ(Y ) > ε}. ψ2 (log 3, PXY ) = 0.05 < 0.1 <
IV. C LOSING THE P ROBABILITY OF FAILURE AND THE PML E NVELOPE We now turn to a natural approach to the post-processing question, one that directly addresses the core issue of probabilistic PML. Instead of defining an additive relaxation or adjusting penalties, we examine the worst-case probability of failure across all possible post-processing mechanisms. Formally, given a joint distribution PXY and ε > 0, define δc (ε) :=
sup Z:X−Y −Z
P{ℓ(Z) > ε},
(8)
where the supremum is taken over all finite random variables Z satisfying the Markov chain X − Y − Z, alternatively, all conditional distributions PZ|Y . Observe that δc quantifies the largest probability that PML exceeds ε under any downstream transformation, so by definition, it is post-processing safe. In (8), we fix ε and find the largest failure probability. Alternatively, we could fix δ ∈ (0, 1) and find the smallest ε that holds with probability at least 1 − δ after arbitrary postprocessing. Let Z denote a (possibly randomized) function of
denote the cumulative distribution function (CDF) of ℓ(Z), and for s ∈ (0, 1), define Quant← Z (s) := inf t ≥ 0 : CZ (t) ≥ s . to be the left-continuous quantile function of ℓ(Z) at level s. Then, for δ ∈ (0, 1), we define εZ (δ) := Quant← Z (1−δ) = inf t ≥ 0 : CZ (t) ≥ 1−δ , (9) which captures the smallest threshold t such that PML is bounded by t with probability at least 1 − δ. Observe that the mapping s 7→ Quant← Z (s) is non-decreasing and leftcontinuous. Consequently, δ 7→ εZ (δ) is non-increasing and right-continuous. The function εZ (δ) also admits the equivalent, and somewhat more explicit formulation εZ (δ) =
min
δ ∈ (0, 1).
max ℓ(z),
A⊂Z z∈A PZ (A)≥1−δ
(10)
That is, εZ (δ) tells us how small we can make the worst-case leakage, up to ignoring a set of probability δ. The equivalence between (9) and (10) is proved in Lemma 2 in Appendix A for completeness. Note that PXY satisfies (ε, δ)-probabilistic PML if and only if εY (δ) ≤ ε. We now define the PML envelope of PXY , denoted by εc , as the supremum of εZ over all post-processings of Y , i.e., εc (δ) :=
sup Z:X−Y −Z
εZ (δ),
δ ∈ (0, 1).
In words, εc (δ) captures the tightest privacy guarantee that survives arbitrary downstream transformations, up to a failure probability of δ. By definition, the map δ 7→ εc (δ) is non-increasing. It is also easy to show that εc (δ) is lower semi-continuous: εZ is lower semi-continuous because it is non-increasing and rightcontinuous, and the supremum of an arbitrary family of lower semi-continuous functions is itself lower semi-continuous. We therefore obtain the following result. Lemma 1. The PML envelope εc is non-increasing and lower semi-continuous on (0, 1). Before we characterize and compute the PML envelope, let us first express it in an alternative form. Given a random variable Z and s ∈ (0, 1), let Quant→ Z (s) := sup t ≥ 0 : CZ (t) ≤ s , 2
be the right-continuous quantile function of ℓ(Z) at level s. Then, for δ ∈ (0, 1) define ε̄Z (δ) := Quant→ Z (1 − δ) = sup{t ≥ 0 : CZ (t) ≤ 1 − δ} =
max
min ℓ(z).
A⊂Z z∈A PZ (A)≥δ
2 See [23, 24] for a review of generalized inverses and quantile functions.
1.0 1 − δ = 0.9
0.8
CY (t)
Y , and consider its corresponding leakage random variable ℓ(Z). Let CZ (t) = P{ℓ(Z) ≤ t}, t ≥ 0,
0.6 0.4 CDF εY (δ) = log( 10 9 )
0.2
εY (δ) = log(4) 00 0.105
0.5
1.0
1.39
t
Fig. 1: An example of the CDF CY (t) together with εY (δ) and ε̄Y (δ) at δ = 0.1. Since CY is not strictly increasing, there is a gap between εY (δ) and ε̄Y (δ). Observe that the mapping δ 7→ ε̄Z (δ) is non-increasing and left-continuous. Heuristically, the difference between ε̄Z (δ) and εZ (δ) can be understood as follows: εZ (δ) is the smallest upper bound on the worst-case PML over all the “good” sets of outputs (i.e., sets with probability at least 1 − δ). In contrast, ε̄Z (δ) is the largest lower bound on the worst-case PML over all “bad” sets of outputs (i.e., sets with probability at least δ). If CZ is strictly increasing, then εZ (δ) = ε̄Z (δ) for all δ ∈ (0, 1), since in that case the inverse of CZ is well defined and coincides with both the left-continuous and right-continuous quantile functions. More generally, we have ε̄Z (δ) ≥ εZ (δ) for all δ ∈ (0, 1) and the inequality may be strict, particularly when Z is a discrete random variable. The difference between εZ and ε̄Z is further illustrated in the following example. Example 2. Recall X and Y from Example 1, and fix δ = 0.1. The leakage random variable ℓ(Y ) takes on two distinct values: a low leakage value of log(10/9) with probability 0.9, and a high leakage value of log(4) with probability 0.1. For this distribution, we have εY (δ) = log(10/9), while ε̄Y (δ) = log 4. Figure 1 shows the distribution function CY of ℓ(Y ), together with two vertical lines marking εY (δ) and ε̄Y (δ). Below, we show that maximizing over all post-processings of Y eliminates the gap between ε̄Z (δ) and εZ (δ). Thus, both quantities can be used to define the PML envelope. Theorem 2. Suppose X and Y are finite random variables. For all δ ∈ (0, 1), we have εc (δ) =
sup Z:X−Y −Z
εZ (δ) =
sup Z:X−Y −Z
ε̄Z (δ).
Proof: See Appendix B. Importantly, Theorem 2 explains why probabilistic PML is not closed under post-processing. It states that the idea of simply ignoring a small “bad” set does not work because,
through post-processing, an adversary can increase the information leakage all the way up to the smallest value in the bad set. To illustrate this, let us revisit Example 1. For δ = 0.1, the good set consists of two outcomes with PML log(10/9) and the bad set consists of two outcomes with PML log(4). By Theorem 2, the adversary can increase the leakage from log(10/9) all the way up to log(4). Note that by (6), log(4) is the largest amount of information any mechanism can leak about a uniformly distributed quaternary secret X. As δ 7→ εc (δ) is non-increasing, it follows that εc (δ) = log(4) for all δ ∈ (0, 0.1]. In the following sections, we characterize and bound εc . Our analysis frequently relies on Theorem 2 and on studying ε̄Z for different choices of Z instead of εZ . We refer to ε̄Z (δ) as the PML δ-quantile of Z.
εY (δ) = ε̄Y (δ) = max ℓ(X → y), y∈Y
(iii) the post-processing inequality for PML [7, Lemma 1] states that if the Markov chain X − Y − Z holds, then max ℓPXZ (X → z) ≤ max ℓPXY (X → y), z∈Z
Computing the PML envelope is, in general, a challenging task, since it involves a maximization over all possible postprocessings of Y . This motivates us to derive bounds on the envelope. Below, we present a general upper bound. Theorem 3. Suppose the joint distribution PXY satisfies εPML with ε > 0. Then, for all δ ∈ (0, 1) we have 1 (11) εc (δ) ≤ min L(X → Y ) + log , ε , δ where X L(X → Y ) = log E eℓ(Y ) = log max PY |X=x (y),
εc (δ) ≤ sup εc (δ ′ ) = δ ′ ∈(0,1)
sup
sup
n o P{ℓ(Z) > t} = P eℓ(Z) > et ≤ E eℓ(Z) e−t ≤ E eℓ(Y ) e−t ,
y∈Y
≤ ε. We make a few remarks on Theorem 3. First, when X is finite, (6) implies that PML is uniformly bounded for all outcomes y ∈ Y. Therefore, regardless of the mechanism PY |X , the joint distribution PXY satisfies ε-PML for some finite ε, yielding a valid bound on the envelope. Second, the maximal leakage bound is useful for characterizing the PML envelope under adaptive composition. In particular, suppose we run two mechanisms on X, producing outputs Y1 and Y2 . Then, using [10, Corollary 2] we have εc (δ) ≤ L(X → Y1 , Y2 ) + log
(12b)
where (12a) is due to Markov’s inequality and (12b) is due to the data-processing inequality for maximal leakage [10, Lemma 1]. Thus, n o {t ≥ 0 : P{ℓ(Z) > t} ≥ δ} ⊆ t ≥ 0 : E eℓ(Y ) e−t ≥ δ , which implies that ε̄Z (δ) = sup {t ≥ 0 : P{ℓ(Z) > t} ≥ δ} n o ≤ sup t ≥ 0 : E eℓ(Y ) e−t ≥ δ 1 . = L(X → Y ) + log δ To prove the second term, we use the following four facts: (i) PXY satisfies ε-PML if max ℓ(X → y) ≤ ε,
1 δ
1 ≤ L(X → Y1 ) + L(X → Y2 | Y1 ) + log , δ
where L(X → Y2 | Y1 ) = X max log y :
(12a)
ε̄Z (δ ′ )
max ℓPXZ (X → z) ≤ max ℓPXY (X → y)
x∈X
Proof: To prove the first term of the bound, fix some Z satisfying the Markov chain X − Y − Z, and t ≥ 0. We write
sup
Z:X−Y −Z δ ′ ∈(0,1)
Z:X−Y −Z z∈Z
denotes (the logarithm of) multiplicative Bayes capacity [9], also known as maximal leakage [10].
y∈Y
y∈Y
and (iv) ε̄Z (δ), εZ (δ), and εc (δ) are all non-increasing in δ. Thus, for all δ ∈ (0, 1), it holds that
=
A. Upper Bounding the PML envelope
y∈Y
(ii) when Y is a finite set, there exists δ0 > 0 such that for all 0 < δ ≤ δ0 we have
1
PY1 (y1 )>0
max
x: y2 PX|Y1 =y1 (x)>0
PY2 |X=x,Y1 =y1 (y2 ),
is the conditional form of maximal leakage [10, Thm. 6]. When the composition is non-adaptive, the mechanism releasing Y2 does not depend on Y1 , so PY2 |X,Y1 = PY2 |X . In that case, L(X → Y2 | Y1 ) ≤ L(X → Y2 ) and the composition bound simplifies to 1 εc (δ) ≤ L(X → Y1 ) + L(X → Y2 ) + log . δ By induction, if we adaptively run n mechanisms on X and obtain outputs Y n = (Y1 , . . . , Yn ), then we have εc (δ) ≤ L(X → Y n ) + log ≤
n X
1 δ
1 L(X → Yi | Y i−1 ) + log . δ i=1
Third, both terms of the upper bound are themselves robust under post-processing.
B. Lower Bounding the PML envelope
Algorithm 1 Computing εb (δ) for a joint distribution PXY
To obtain lower bounds on εc , we may restrict attention to specific classes of post-processings and compute the PML δ-quantile of the resulting outputs. This can be viewed as restricting the computational power of the adversary. In general, the choice of post-processings used to derive lower bounds is mechanism dependent (see Section V-B for an illustration). Nevertheless, it is instructive to consider two simple and broadly applicable instances: (i) taking Z = Y , i.e., no postprocessing, which yields ε̄Y ; and (ii) restricting attention to binary post-processings of Y . Let
Require: PY |X , PX and δ ∈ (0, 1) Ensure: εb (δ) 1: Compute the marginal PY = PY |X ◦ PX 2: Initialize M ← 0 3: for all x ∈ X do 4: for all y ∈ Y do P (y) 5: sx (y) ← YP|X=x Y (y) 6: end for 7: Sort Y as (y1 , . . . , y|Y| ) so that
εb (δ) :=
sup
ε̄Z (δ),
Z:X−Y −Z, Z={0,1}
δ ∈ (0, 1),
(13)
denote the binary envelope of PXY . Then, for all δ ∈ (0, 1), we have the lower bound εc (δ) ≥ max ε̄Y (δ), εb (δ) . (14) One may obtain sharper lower bounds by extending the bound to ternary, quaternary, and other higher-order k-ary postprocessings. As we will see below, the advantage of εb is that it is simple to compute. The quantity εb previously appeared in the work of Saeidian et al. [7] (in a slightly different form) as a stand-alone privacy definition. In contrast, here, we use εb only as a lower bound on the PML envelope. Algorithm 1 provides a procedure for computing εb based on the proof of [7, Thm. 3]. The main idea underlying both this proof and Algorithm 1 is to generalize the notion of PML from individual outcomes to events. In particular, given an event E ⊆ Y with PY (E) > 0, and Z = 1E (Y ), we may define event-wise leakage as ℓPXY (X → E) := ℓPXZ (X → 1). Technically, this is not a new concept since event-wise leakage is simply the PML of the affirmative outcome of an indicator function. Nevertheless, it provides a convenient shorthand for reasoning about post-processing. Note that extending PML to events is natural in this context, since any binary postprocessing corresponds to selecting an event in Y and revealing whether or not the outcome Y lies in that event. Heuristically, Algorithm 1 works as follows: For each x ∈ X , we compute the largest value of PY |X=x (E) , PY (E) over events E ⊆ Y with PY (E) = δ (with possible randomization at the boundary).3 The quantity εb is then obtained by taking the logarithm of the maximum of this value over all x ∈ X . Further discussion about the information leakage of events and their connection to post-processing is provided in Appendix C. 3 Here, we use the term “event” in a generalized sense that allows random-
ization. In particular, each outcome y ∈ Y may be in the set E with a certain probability. See Appendix C for details.
8: 9: 10: 11:
sx (y1 ) ≥ sx (y2 ) ≥ · · · ≥ sx (y|Y| ) Pk⋆ Find the smallest index k ⋆ such that j=1 PY (yj ) ≥ δ Pk⋆ −1 p ← j=1 PY (yj ) ζ ← PYδ−p k⋆ ) (y Pk⋆ −1 1 ⋆ v← δ j=1 PY |X=x (yj ) + ζPY |X=x (yk )
12: M ← max(M, v) 13: end for 14: return εb ← log M
Finally, we emphasize that both terms ε̄Y and εb must be included in the lower bound (14). Depending on the setup, either term may yield the tighter bound. V. A PPLICATIONS We now calculate and bound the PML envelope in two canonical settings. These are: the PML–extremal mechanisms in the high-privacy regime [12] and the randomized response mechanism [13, 14]. A. PML-extremal Mechanisms In [12], Grosse et al. studied the design of optimal privacy mechanisms under the ε–PML constraint for a broad class of convex utility functions. The resulting mechanisms were termed PML–extremal mechanisms. Fix a prior distribution PX on X = [k] with k ≥ 2. Grosse et al. [12] showed that in the high-privacy regime, corresponding to 1 0 < ε < log , 1 − minx∈X PX (x) the optimal mechanism has the form ( 1 − eε 1 − PX (i) , ∗ PY |X=i (j) = eε PX (j),
if i = j, if i ̸= j,
where Y = X , and i, j ∈ [k]. Note that the outcomes of this mechanism have the PML ℓ(X → j) = ε for all j ∈ [k]. Theorem 4. Let PX be a distribution on X = [k], and fix 0 < ε < − log (1 − minx∈X PX (x)). Let PY∗ |X denote the PML-extremal mechanism. Then, for all δ ∈ (0, 1), the PML envelope is εc (δ) = ε.
Proof: By Theorem 3, any mechanism satisfying ε-PML has εc (δ) ≤ ε for all δ ∈ (0, 1). We argue that PY∗ |X achieves this upper bound. Let A ⊂ Y be an arbitrary set with probability PY (A) ≥ δ. Since every j ∈ Y has leakage ε, we have minj∈A ℓ(X → j) = ε. Using (14) we have
Then, the PML envelope admits the lower bound εc (δ) ≥ hδ (θ), where ℓ(X → N − 1) hδ (θ) = log (N −1)α+θβ δ ℓ(X → N )
εc (δ) ≥ ε̄Y (δ) = max min ℓ(X → j) E⊂Y j∈E PY (E)≥δ
≥ min ℓ(X → j) = ε. j∈A
Combining this with the upper bound establishes the claim. The proof of Theorem 4 shows that if ℓ(X → y) = ε for all y, then the PML envelope is constant in δ. We state this in the following corollary. Corollary 1. Suppose ℓ(X → y) = ε for all outcomes y ∈ Y with ε > 0. Then, the PML envelope satisfies εc (δ) = ε for all δ ∈ (0, 1). B. Randomized Response Mechanism Given an integer k ≥ 2, let X = Y = [k]. The k-randomized response (k-RR) mechanism with parameter εr > 0 is defined as ( e εr eεr +k−1 , j = i, i, j ∈ [k]. (15) PY |X=i (j) = 1 eεr +k−1 , j ̸= i,
The k-RR mechanism satisfies εr -LDP. For simplicity, let e εr , α := εr e +k−1 1 β := εr , e +k−1 pi := PX (i), i ∈ [k], qj := PY (j), j ∈ [k],
and observe that qi = β+(α−β)pi for all i ∈ [k]. Furthermore, each outcome of the mechanism has the PML α ℓ(X → j) = log , j ∈ [k]. qj Without loss of generality, let us assume that p1 ≤ p2 ≤ · · · ≤ pk , which implies that q1 ≤ q2 ≤ · · · ≤ qk and ℓ(X → 1) ≥ ℓ(X → 2) ≥ · · · ≥ ℓ(X → k). Theorem 5. Let PX be a distribution on X = [k] and let PY |X be the k-RR mechanism. The PML envelope satisfies the following: (i) If δ ∈ (0, q1 ], then εc (δ) = log qα1 . (ii) For δ ∈ (q1 , 1), the PML envelope admits the upper bound kα α εc (δ) ≤ min log , log . δ q1 (iii) For δ ∈ (q1 , 1),Plet N ∈ {2, . . . P , k} be the unique N −1 N index such that q < δ ≤ j=1 j j=1 qj . Let θ := δ−
PN −1 j=1
qN
qj
∈ (0, 1], and suppose the prior satisfies PN −1 α j=1 pj + β pN ≤ . (N − 2)α + β
if 0 < θ ≤ θ1 , if θ1 < θ ≤ θ2 , if θ2 < θ ≤ 1,
and θ1 =
PN −2 α (N − 2)qN −1 − j=1 qj αqN − βqN −1 PN −1 α (N − 1)qN − j=1 qj
,
θ2 =
qN (α − β)
.
Proof: (i) The k-RR mechanism satisfies log qα1 -PML, so we have εc (δ) ≤ log qα1 which holds for all δ ∈ (0, 1). Suppose δ ∈ (0, q1 ], and let A = {1} which satisfies PY (A) = q1 . Then, we have εc (δ) ≥ ε̄Y (δ) = max min ℓ(X → j) j∈E E⊂Y PY (E)≥δ
≥ min ℓ(X → j) = log j∈A
α . q1
(ii) We use Theorem 3 and calculate the maximal leakage of the k-RR mechanism: X L(X → Y ) = log max PY |X=i (j) = log(kα). j∈[k]
i∈[k]
This yields the upper bound εc (δ) ≤ L(X → Y ) + log
kα 1 = log . δ δ
(iii) First, observe that (14) yields εc (δ) ≥ ε̄Y (δ) = log
α = ℓ(X → N ), qN
PN −1 PN for j=1 qj < δ ≤ j=1 qj . Below, we construct a post-processing Z and tighten the lower bound to εc (δ) ≥ max{ε̄Y (δ), ε̄Z (δ)}. Let Z = [N ] and η = (η1 , . . . , ηN ) be a tuple satisfying ηz ≥ 0,
N −1 X z=1
for all z ∈ [N ],
ηz = θ,
ηN = 1 − θ.
Define 1, if j ∈ [N − 1] and z = j, ηz , if j = N and z ∈ [N ], PZ|Y =j (z) = 1, if j > N and z = N, 0, otherwise.
(16)
In words, each k-RR outcome j ∈ [N − 1] is deterministically mapped to z ∈ [N − 1], all j > N are mapped to a single catch-all symbol z = N , and j = N is split across z = 1, . . . , N with weights η1 , . . . , ηN . Consider the event B = [N − 1] of outcomes of Z, and note that by construction, we have PZ (B) = = =
N −1 X z=1 N −1 X z=1 N −1 X
PZ (z)
α α + ηi∗ β = ⇐⇒ qi + ηi∗ qN qN −1 α(qN −1 − qi ) ≥ 0, i = 1, . . . , N − 2, ηi∗ = αqN − βqN −1 Mi (ηi∗ ) =
qz + ηz qN qz + θqN = δ.
z=1
Thus, we may use the set B to obtain lower bounds on the PML envelope: εc (δ) = ε̄Z (δ) ≥ min ℓPXZ (X → z). z∈B
Our goal is to optimize the weights {ηi }N i=1
in order to obtain the tightest possible lower bound. Note that if N = 2, then (16) forces η1 = θ, so PZ|Y is fully specified. Therefore, for the rest of the proof assume that N > 2. We begin by calculating the PML for symbols in the set B. For each i ∈ [N − 1], using the structure of the k-RR mechanism and PZ|Y , we observe that max PZ|X (i | x) = PZ|X (i | i) = α + ηi β, x
PZ (i) = qi + ηi qN . Hence, the PML is ℓPXZ (X → i) = log
since q1 ≤ · · · ≤ qk . This bound is achievable at θ = 0 since η1 = · · · = ηN −1 = 0 is feasible at this point.4 Next, we argue that there exists θ1 ≥ 0 such that the upper bound in (17) is achievable for θ ∈ (0, θ1 ]. This is because in order to achieve qNα−1 , all we need is to have ηN −1 = 0 and Mi (ηi ) ≥ qNα−1 for i = 1, . . . , N − 2. Let ηi∗ be such that Mi (ηi∗ ) = qNα−1 , that is,
max PZ|X (i | x) x
PZ (i)
= log
α + ηi β , qi + ηi qN
∗ and also ηN −1 = 0. This choice of the parameters yields PN −2 N −1 α (N − 2)qN −1 − i=1 qi X θ1 = ηi∗ = ≥ 0. αqN − βqN −1 i=1
Therefore, assuming that θ1 > 0, for θ ∈ (0, min{θ1 , 1}], we have the first piece of the lower bound εc (δ) ≥ min ℓPXZ (X → z) z∈A
= min log Mi (ηi∗ ) = log i∈[N −1]
Note that in this regime, we use the lower bound obtained from Z and not Y itself, since qNα−1 ≥ qαN .
Second regime. Next, suppose θ1 < 1 and θ > θ1 . In the second regime, we are forced to increase at least one ηi beyond ηi∗ , so the objective falls below qNα−1 . Let {η̃i } denote the optimal parameters. There exists a α common threshold τ ∈ [ q1α+β +qN , qN −1 ] such that Mi (η̃i ) =
Let α + ηi β , i = 1, . . . , N − 1, qi + ηi qN and consider the optimization problem: Mi (ηi ) :=
max
min Mi (ηi ),
η1 ,...,ηN −1 i∈[N −1]
subject to
N −1 X
ηi = θ,
i=1
ηi ≥ 0, i = 1, . . . , N − 1.
It is easy to verify that Mi′′ (ηi ) ≥ 0, so Mi is convex. Thus, the above optimization problem is not a convex one (since the minimum of a collection of convex functions need not be convex). Nevertheless, we can solve it by inspection. First regime. Let us start by noting that Mi′ (ηi ) < 0 for ηi ≥ 0, implying that Mi (ηi ) ≤ Mi (0) = qαi for all i ∈ [N −1]. This yields the upper bound on the objective α α max min Mi (ηi ) ≤ min = , η1 ,...,ηN −1 ≥0 i∈[N −1] qN −1 i∈[N −1] qi (17)
α . qN −1
α + η̃i β α − τ qi > 0, = τ ⇐⇒ η̃i (τ ) = qi + η̃i qN τ qN − β
for i = 1, . . . , N − 1.5 Hence, θ can be expressed as PN −1 N −1 X (N − 1)α − τ i=1 qi θ(τ ) = η̃i (τ ) = . τ qN − β i=1 Solving for τ gives (N − 1)α + θβ (N − 1)α + θβ = , τ (θ) = PN −1 δ i=1 qi + θqN
θ > θ1 .
Therefore, for θ ∈ (θ1 , θ2 ] (with θ2 specified below), we get the middle piece of the lower bound εc (δ) ≥ min log Mi (η̃i ) = log i∈[N −1]
(N − 1)α + θβ . δ (18)
4 Technically, we assume that θ > 0, but we may consider the limiting value of the objective as θ ↓ 0 since the Mi ’s are continuous. 5 Note that each M is continuous and strictly decreasing. Therefore, if i Mi (ηi ) > Mj (ηj ), then there exists ζ > 0 such that Mj (ηj ) < Mj (ηj − ζ) = Mi (ηi + ζ). Thus, the optimal parameters must yield a common value for all Mi ’s.
Third regime. The point θ2 is the value where any further increase in θ would make the lower bound in (18) drop below ε̄Y (δ), i.e., PN −1 α (N − 1)qN − i=1 qi α τ (θ2 ) = ⇐⇒ θ2 = . qN qN (α − β) Thus, in the third regime θ ∈ (θ2 , 1] we use α εc (δ) ≥ ε̄Y (δ) = log . qN
Finally, we find the condition on the prior distribution ensuring that θ2 ≤ 1. Two conditions need to be satisfied for this: We require θ1 ≤ 1 (ensuring that we enter the second regime) and also τ (1) ≤ qαN (ensuring that we enter the third regime). By using qi = β +(α−β)pi , and after some algebra, we obtain the following conditions: PN α i=1 pi + β pN −1 ≤ , (19) (N − 1)α + β PN −1 α i=1 pi + β pN ≤ . (20) (N − 2)α + β
Observe that (20) can be written in the form PN −1 α i=1 pi + β (N − 2)α + β ≤ , pN
which implies that PN PN α i=1 pi + β α i=1 pi + β ≥ = pN ≥ pN −1 , P −1 α N (N − 1)α + β i=1 pi +β α+ pN
so if (20) is satisfied, (19) is also automatically satisfied. The lower bounds in Theorem 5 are stated under the assumption that 0 < θ1 < θ2 . The following degenerate cases are handled by interpreting the piecewise expression in the natural way: (i) If N = 2 or q1 = · · · = qN −1 , then θ1 = 0, so the first regime is vacuous and omitted; (ii) If qN −1 = qN , then θ1 = θ2 , so the second regime is vacuous and omitted. In this case, the bound equals ℓ(X → N − 1) = ℓ(X → N ) for all θ ∈ (0, 1]. Note that if PX is uniformly distributed, then ℓ(X → j) = log(kα) for all j ∈ [k], and applying Corollary 1 gives εc (δ) = log(kα) for all δ ∈ (0, 1). The condition on the prior in Theorem 5 ensures that all three segments of hδ can be active, i.e., it guarantees that θ2 ≤ 1. We conjecture that under this condition, hδ coincides with εc , that is, the construction used in the proof of Theorem 5 is in fact optimal. Establishing this conjecture would require either proving the optimality of the construction or deriving a matching upper bound. We leave this as an open problem for future work. Figure 2 illustrates the bounds in Theorem 5. For comparison, we also plot εb and the ADP curve of the k-RR mechanism. Recall from [25, Thm. 2] that, for fixed δ ∈ (0, 1), the k-RR mechanism satisfies (εDP (δ), δ)-DP with α−δ εDP (δ) = max log ,0 . β
Moreover, for δ ∈ (q1 , 1), the binary envelope εb (δ) is derived in Appendix C-B and is given by α + (N − 2 + θ)β . δ Here, we consider the k-RR mechanism with εr = 1.0 for k ∈ {3, 5, 12, 20} under various prior distributions. To simplify the specification of priors over larger alphabets, we use a fourlevel construction obtained by partitioning the alphabet into four blocks of equal size (assuming k is divisible by 4). Fix ρ ∈ (0, 1/3) and define εb (δ) = log
m0 = 1 − 3ρ,
m1 = 1 − ρ,
m2 = 1 + ρ,
m3 = 1 + 3ρ.
Then, set mr(i) , pi = k
4(i − 1) r(i) := , k
for i ∈ [k]. With this construction, PX is constant on blocks Pk of size k4 , and satisfies i=1 pi = 1. We make the following observations from Figure 2. First, the binary envelope εb (δ) overlaps with the lower bound in Theorem 5 when δ is slightly above q1 , i.e., when N = 2 and θ ≤ θ2 (assuming that q1 < q2 ). Outside this regime, εb (δ) can be a significantly looser lower bound than hδ , with the gap becoming more pronounced as k increases. Second, when δ is small, log(α/q1 ) is the tighter upper bound on εc but as δ increases, the maximal-leakage upper bound log(kα/δ) becomes tighter. Third, as k grows, the gap between the upper and lower bounds in Theorem 5 shrinks. Finally, the PML envelope is qualitatively and quantitatively different from ADP. As δ varies from 0 to 1, εDP (δ) ranges from εr down to 0. In contrast, εc (δ) equals log(α/q1 ) as δ → 0 (which is strictly smaller than εr ) and can remain bounded away from 0 as δ → 1. We also observe that as k increases, εDP (δ) decreases more quickly in δ, implying that k-RR provides strong DP guarantees even for small δ. This behavior is not observed for the PML envelope: even for large k, εc (δ) may decrease only mildly with δ. We emphasize that all PML quantities depend on the prior PX , whereas the ADP curve depends only on k and εr . VI. OTHER R ELATED W ORKS While the PML envelope has an information-theoretic flavor, it is most closely related to works proposing DP definitions, where post-processing robustness is treated as an axiom. Since the introduction of ADP, several other DP notions have been proposed, primarily to provide more convenient machinery for composition. Notable examples include Rényi DP [26], concentrated DP [27], and Gaussian DP [28]. It is worth emphasizing that while modern systems often rely on these frameworks for privacy accounting (i.e., computing composition bounds during the internal calculations of an algorithm), the resulting guarantees are typically converted back to (ε, δ)-DP for reporting and comparison purposes. The work closest in spirit to ours is that of Balle et al. [18, 25] introducing privacy profiles. The privacy profile is
1.0
0.6
0.4
0.8
Privacy parameter ε
Thm. 5 LB on εc (δ) ADP εb
0.8
Privacy parameter ε
1.0
Thm. 5 UB on εc (δ)
0.6 Thm. 5 UB on εc (δ) Thm. 5 LB on εc (δ) ADP εb
0.4
0.2
0.2
0.0
0.0 0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
δ
1.0
1.0
0.8
0.8
0.6 Thm. 5 UB on εc (δ) Thm. 5 LB on εc (δ) ADP εb
0.4
Thm. 5 UB on εc (δ)
0.0
0.0 0.6
0.8
1.0
δ
(c) k = 12 and PX is the four-level prior with ρ = 0.1.
Thm. 5 LB on εc (δ) ADP εb
0.4
0.2
0.4
1.0
0.6
0.2
0.2
0.8
(b) k = 5 and PX = (0.1, 0.2, 0.2, 0.2, 0.3).
Privacy parameter ε
Privacy parameter ε
(a) k = 3 and PX = (0.2, 0.3, 0.5).
0.0
0.6
δ
0.0
0.2
0.4
0.6
0.8
1.0
δ
(d) k = 20 and PX is the four-level prior with ρ = 0.1.
Fig. 2: PML envelope upper bounds (UBs), lower bounds (LBs), εb , and (εDP (δ), δ)-DP guarantees for the k-RR mechanism with εr = 1.0. Each sub-figure illustrates a different alphabet size k and prior PX . a function that precisely captures the tradeoff between ε and δ, similar to the PML envelope. Nonetheless, as explained in Section II, δ in the privacy profile corresponds to an additive slack parameter, whereas in our setting it captures the worstcase failure probability. VII. C ONCLUSIONS AND F UTURE W ORK We introduced the PML envelope as a meaningful and robust privacy guarantee that captures the tradeoff between information leakage and failure probability under arbitrary post-processing. The present work focused on settings in which both the secret and the observable outcomes take values in finite probability spaces. This assumption provides a simple and mathematically convenient context for introducing the PML envelope. The two classes of mechanisms studied here (PML-extremal and k-RR) illustrate the different roles of the upper bounds in Theorem 3. In finite-alphabet settings, the second term is often the tighter one, especially when δ is small, since the maximal-leakage bound includes an additive log(1/δ)
term. The tightness of the second term is also discussed in Corollary 1. Still, the maximal-leakage bound has two useful features. First, it remains applicable in settings where the secret does not have finite support, where uniform ε-PML bounds usually do not exist. Second, maximal leakage is always bounded by log |Y|, independently of the mechanism and the prior on the secret, and therefore yields the general bound |Y| εc (δ) ≤ log , δ ∈ (0, 1). δ This provides a simple and meaningful privacy guarantee that holds for any secret and any computation with a finite output alphabet, even when no randomness is involved. Such bounds can be useful, for example, in statistical settings that involve deterministic recoding or quantization of the input data. The systematic study of these consequences is left for future work. Another direction concerns the behavior of εc under composition. Establishing sequential or adaptive composition results for the PML envelope beyond the maximal-leakage bounds remains an important topic for future work.
A PPENDIX A E QUIVALENCE OF (9) AND (10)
Next, we prove the opposite inequality, i.e., sup
Lemma 2. For all δ ∈ (0, 1), it holds that inf{t ≥ 0 : CZ (t) ≥ 1 − δ} =
min
Z:X−Y −Z
max ℓ(z).
A⊂Z z∈A PZ (A)≥1−δ
min
max ℓ(z),
A⊂Z z∈A PZ (A)≥1−δ
r2 := inf{t ≥ 0 : PZ {z : ℓ(z) ≤ t} ≥ 1 − δ}. Given r ≥ 0, let Jr = z : ℓ(z) ≤ r , and note that maxz∈Jr ℓ(z) = r. By definition, if r < r2 , then PZ (Jr ) < 1 − δ, therefore PZ (Jr ) ≥ 1 − δ for all r ≥ r2 . Therefore, we have r1 = ≤
min
max ℓ(z)
A⊂Z z∈A PZ (A)≥1−δ
inf
max ℓ(z)
Jr :r≥r2 z∈Jr
≤ inf r = r2 . r≥r2
Next, we argue that the strict inequality r1 < r2 would lead to a contradiction. To see this, suppose r1 < r2 . This means that there exists a set E ⊂ Z with PZ (E) ≥ 1 − δ such that r1 ≤ r3 = maxz∈E ℓ(z) < r2 . On the other hand, note that E ⊆ z : ℓ(z) ≤ r3 , therefore, PZ z : ℓ(z) ≤ r3 ≥ PZ (E) ≥ 1 − δ. Hence, r2 = inf{t ≥ 0 : PZ {z : ℓ(z) ≤ t} ≥ 1 − δ} ≤ r3 , which is a contradiction. We conclude that r1 = r2 . A PPENDIX B P ROOF OF T HEOREM 2 It is well-known that the right-continuous quantile function upper bounds the left-continuous quantile function. Nevertheless, we include a proof for completeness. Fix some random variable Z with PML ℓ(Z), and δ ∈ (0, 1). Let 0 ≤ α < εZ (δ) and consider the set Bα = {z ∈ Z : ℓ(z) ≥ α}. Then, PZ (Bα ) > δ,6 and we get ε̄Z (δ) =
max
A⊂Z: PZ (A)≥δ
min ℓ(z) ≥ min ℓ(z) ≥ α. z∈A
ε̄Z (δ) ≥ εZ (δ). 6 This can be shown by contradiction: If P (B ) ≤ δ, then the set B c = α Z α c ) ≥ 1 − δ and also satisfies max c ℓ(z) ≤ Z \ Bα has probability PZ (Bα z∈Bα
α < εZ (δ). This contradicts the definition of εZ (δ) as the smallest upper bound on the PML of all sets with probability at least 1 − δ.
ε̄Z (δ).
c = εY (δ) < ε̄Y (δ) = c̄, where c̄, c > 0. This happens if and only if there exists a subset B ⊂ Y with probability PY (B) ≥ δ and miny∈B ℓ(y) = c̄ and G = Y \ B and maxy∈G ℓ(y) = c. Therefore, there exist outcomes y1 ∈ B, y2 ∈ G such that ℓ(X → y1 ) ≥ c̄,
ℓ(X → y2 ) ≤ c.
(21)
Fix a parameter η ∈ (0, 1) and let B ∼ Bernoulli(η) be independent of (X, Y ). Define Z = hη (Y, B) where ⊥, if Y = y1 , ⊥, if Y = y and B = 1, 2 hη (Y, B) = ⋄, if Y = y2 and B = 0, Y, otherwise. Note that Z is a randomized function of Y since it also depends on B. Now, observe that PZ (⊥) = PY (y1 ) + ηPY (y2 ), PZ|X=x (⊥) = PY |X=x (y1 ) + ηPY |X=x (y2 ). Then, for fixed x we have PZ|X=x (⊥) PY |X=x (y1 ) + ηPY |X=x (y2 ) = PZ (⊥) PY (y1 ) + ηPY (y2 ) PY |X=x (y1 ) PY |X=x (y2 ) PY (y2 ) + η PY (y1 ) PY (y2 ) PY (y1 ) = PY (y2 ) 1 + η PY (y1 ) ! PY |X=x (y2 ) PY (y2 ) · · = PY (y2 ) PY (y1 ) PY (y2 ) 1−η + O(η 2 ) PY (y1 ) PY |X=x (y1 ) PY (y2 ) = −η · PY (y1 ) PY (y1 ) PY |X=x (y1 ) PY |X=x (y2 ) − + O(η 2 ). PY (y1 ) PY (y2 ) PY |X=x (y1 ) +η PY (y1 )
Taking the logarithm and maximum over x ∈ X on both sides gives
z∈Bα
Letting α → εZ (δ) yields
sup Z:X−Y −Z
Fix δ ∈ (0, 1) and suppose
Proof: Let r1 :=
εZ (δ) ≥
PZ|X=x (⊥) x PZ (⊥) PY |X=x (y1 ) PY (y2 ) −η · PY (y1 ) PY (y1 ) ! PY |X=x (y1 ) PY |X=x (y2 ) 2 − + O(η ) PY (y1 ) PY (y2 )
ℓPXZ (X → ⊥) = log max = log max x
PY |X=x (y1 ) PY (y2 ) ≥ log max −η · x PY (y1 ) PY (y1 ) ! PY |X=x′ (y1 ) PY |X=x′ (y2 ) 2 max − + O(η ) , x′ PY (y1 ) PY (y2 ) ≥ log ec̄ − ηβ + O(η 2 ) = c̄ + log 1 − ηβe
−c̄
2
+ O(η ) ,
(22)
where β=
PY (y2 ) PY (y1 )
max ′ x
PY |X=x′ (y1 ) PY |X=x′ (y2 ) − PY (y1 ) PY (y2 )
.
Note that β > 0 because PY |X=x′ (y1 ) PY |X=x′ (y2 ) − max x′ PY (y1 ) PY (y2 ) PY |X=x′ (y1 ) PY |X=x (y2 ) ≥ max − max x x′ PY (y1 ) PY (y2 ) ≥ exp(c̄) − exp(c) > 0. Now, using the elementary bound log(1 − t) ≥ −t − t2 for 0 < t < 12 in (22) yields ℓPXZ (X → ⊥) ≥ c̄ − ηβe−c̄ + O(η 2 ) = c̄ − ηγ + O(η 2 ), with γ = βe−c̄ . Thus, by taking η → 0, we can bring ℓPXZ (X → ⊥) arbitrarily close to c̄. The final step is to argue that εZ (δ) ≥ c̄. To show this, let B ′ = B \ {y1 } and G ′ = G \ {y2 } so that the alphabet of Z can be represented by Z = B ′ ∪ G ′ ∪ {⊥, ⋄}. Let A be an arbitrary subset of Z with probability PZ (A) ≥ 1 − δ. Since PZ (G ′ ∪ {⋄}) = PY (G) − ηPY (y2 ) < 1 − δ, any such set A either intersects with B ′ or contains ⊥. If A contains elements from B ′ , then max ℓPXZ (X → z) ≥ min′ ℓPXZ (X → z) ≥ c̄, z∈A
z∈B
and if ⊥ ∈ A, then max ℓPXZ (X → z) ≥ ℓPXZ (X → ⊥) ≥ c̄ − ηγ + O(η 2 ), z∈A
and taking η → 0 yields maxz∈A ℓPXZ (X → z) ≥ c̄. Hence, we have proved that εZ (δ) =
min
max ℓ(X → z) ≥ c̄ = ε̄Y (δ).
A:PZ (A)≥1−δ z∈A
This, in turn, implies that sup Z:X−Y −Z
εZ (δ) ≥
sup Z:X−Y −Z
ε̄Z (δ),
This definition is motivated by the observation that both deterministic and randomized post-processings can be naturally expressed in terms of indicator functions. For deterministic mappings, this is immediate: If Z = h(Y ) and z ∈ Z, then ℓPXZ (X → z) = ℓPXY (X → Ez ), where Ez = {y ∈ Y : h(y) = z} denotes the pre-image of z under h. We can also cast randomized mappings as deterministic ones by adopting a few formalisms from [29] and [7]. Given a privacy mechanism PY |X , we say that two outcomes y, y ′ are similar if there exists a constant c > 0 such that PY |X=x (y) = cPY |X=x (y ′ ) for all x ∈ X . Similar outcomes have the same information density i(x; y) = i(x; y ′ ) for all x ∈ X , and induce the same posterior distributions PX|Y =y = PX|Y =y′ . Consequently, “merging” similar outcomes (i.e., mapping similar outcomes to the same symbol) does not alter the distribution of ℓ(X → Y ). In [29], the mechanism obtained by merging all similar outcomes is called the reduced mechanism. As an example, for the mechanism PY |X in (7), outcomes 3 and 4 are similar, and its reduced form is 0 0 1 0 1 0 . PYr |X = 0 0.2 0.8 0.2
0
0.8
Next, we define an equivalence relation that unifies all mechanisms with the same reduced form. Let [PY |X ] denote the equivalence class of PY |X . A key advantage of introducing such equivalence classes is that a randomized post-processing applied to the outputs of PY |X can alternatively be viewed as a deterministic post-processing applied to some mechanism in [PY |X ]. While this idea can be established formally, we illustrate it with a simple example that readily extends to a general proof. Fix a mechanism PY |X with binary output alphabet Y = {0, 1}, and consider a randomized post-processing PZ|Y of the form " # α 1−α PZ|Y = , 1−β β with 0 < α, β < 1 and Z = {0, 1}. Define a mechanism PỸ |X with the output space Ỹ = {00, 01, 10, 11} by PỸ |X=x (00) = αPY |X=x (0), PỸ |X=x (01) = (1 − α)PY |X=x (0), PỸ |X=x (10) = (1 − β)PY |X=x (1),
as desired. A PPENDIX C M EASURING THE I NFORMATION L EAKED TO E VENTS Given an event E ⊆ Y with PY (E) > 0 and a random variable Z = 1E (Y ), we define ℓPXY (X → E) := ℓPXZ (X → 1).
PỸ |X=x (11) = βPY |X=x (1),
for all x. Then, PỸ |X ∈ [PY |X ] and we have ℓPXZ (X → 0) = ℓPX Ỹ (X → {00, 10}), ℓPXZ (X → 1) = ℓPX Ỹ (X → {01, 11}),
that is, Z is a deterministic function of Ỹ . Extending this construction to general post-processings shows that any randomized post-processing of Y can be treated as a deterministic mapping applied to some mechanism in the equivalence class [PY |X ]. Moreover, using equivalent classes, we interpret “events” in the generalized sense of applying an indicator function to some Ỹ induced by a mechanism PỸ |X ∈ [PY |X ]. Concretely, we extend the notation by defining ℓPXY (X → E) := ℓPXZ (X → 1),
(23)
where Z = 1E (Ỹ ) for E ⊆ Ỹ and PỸ |X ∈ [PY |X ]. Below, we establish some elementary properties of the map E 7→ ℓPXY (X → E). As a preliminary step, let us express ℓPXY (X → E) in terms of the information density: PY |X=x (E) ℓPXY (X → E) = log max x∈X PY (E) P P (y) Y |X=x y∈E = log max x∈X PY (E) P y∈E exp i(x; y) PY (y) = log max x∈X P (E) h Y i = log max EY ∼QE exp i(x; Y ) ,
(24)
Lemma 3. The function ℓ(X → E) satisfies the following properties: (i) 0 ≤ ℓ(X → E) ≤ log PY1(E) for all E ⊆ Y. (ii) ℓ(X → Y) = 0. (iii) If E ∩ E ′ = ∅, then n o ℓ(X → E ∪ E ′ ) ≤ max ℓ(X → E), ℓ(X → E ′ ) . (iv) Suppose PY (E) = θ > 0. For each 0 < θ′ < θ, there exists an event E ′ ⊂ E with probability PY (E ′ ) = θ′ such that ℓ(X → E ′ ) ≥ ℓ(X → E). Proof: (i) These bounds follow immediately from the definition of ℓ(X → E) and were also noted in [7]. (ii) PY |X=x (Y) 1 = log = 0. PY (Y) 1
(iii) Suppose E ∩ E ′ = ∅. We have
PY |X=x (E) = ℓ(X → E). PY (E)
Choose τ > 0 so that PY {y ∈ E : exp i(x; y) > τ } ≤ θ′
≤ PY {y ∈ E : exp i(x; y) ≥ τ }. Let A = {y ∈ E : exp i(x; y) > τ }. If PY (A) < θ′ , choose a set B ⊆ {y ∈ E : exp i(x; y) = τ } so that PY (A) + PY (B) = θ′ and let E ′ = A ∪ B.7 If PY (A) = θ′ , then let E ′ = A. By construction, we have exp i(x; y) ≥ τ, y ∈ E ′ , exp i(x; y) ≤ τ, y ∈ E \ E ′ . PY |X=x (E) PY (E) ′ PY |X=x (E ) + PY |X=x (E \ E ′ ) = log PY (E ′ ) + PY (E \ E ′ ) nP ′ ′ o Y |X=x (E ) PY |X=x (E \ E ) ≤ log max , ′ ′ PY (E ) PY (E \ E ) = log
PY |X=x (E ′ ) PY (E ′ )
(25a)
≤ ℓ(X → E ′ ), where (25a) follows because h i PY |X=x (E ′ ) = E exp i(x; Y ) ≥ τ, Y ∼Q E′ PY (E ′ ) h i PY |X=x (E \ E ′ ) = E exp i(x; Y ) ≤ τ. Y ∼Q ′ E\E PY (E \ E ′ ) We make some further remarks about the event-wise leakage. First, in general, the reverse of Lemma 3(iii) need not ′ hold,ni.e., one cannot claim that o ℓ(X → E ∪ E ) upper bounds min ℓ(X → E), ℓ(X → E ′ ) .
Example 3. Let X be an unbiased Bernoulli random variable, and let Y = {1, 2, 3}. Consider the mechanism 0.9 0 0.1 PY |X = , 0 0.9 0.1 which induces the marginal distribution PY with PY (1) = 0.45,
′
PY |X=x (E ∪ E ) x PY (E ∪ E ′ ) PY |X=x (E) + PY |X=x (E ′ ) = log max x PY (E) + PY (E ′ ) nP ′ o Y |X=x (E) PY |X=x (E ) ≤ log max max , x PY (E) PY (E ′ )
ℓ(X → E ∪ E ′ ) = log max
log
ℓ(X → E) = log
where QE is the conditional distribution of Y given E, that is, PY (y) if y ∈ E, PY (E) QE (y) = 0 otherwise.
x∈X
(iv) Fix x ∈ X satisfying
Now, we can write
x∈X
ℓPXY (X → Y) = log max
n o = max ℓ(X → E), ℓ(X → E ′ ) .
PY (2) = 0.45,
PY (3) = 0.1.
′
Let E = {1} and E = {2}. Then, we have ℓ(X → E) = ℓ(X → E ′ )
PY |X=x ({1}) PY ({1}) x∈{0,1}
= log max
7 To select such B, we might need to use some other mechanism in [P
Y |X ].
0.9 0.45 = log 2.
where ζ ∈ (0, 1] is chosen so that PY (Fk⋆ −1 )+ζPY (yk⋆ ) = δ. Finally, the binary envelope is obtained as
= log
εb (δ) = log max κ(x).
However, for their union E ∪ E ′ = {1, 2} we have
x∈X
PY |X=x ({1, 2}) = log 1 = 0. PY ({1, 2}) x∈{0,1}
ℓ(X → E ∪ E ′ ) = log max ′
′
Thus, ℓ(X → E ∪ E ) = 0 < min{ℓ(X → E), ℓ(X → E )} = log 2. Second, the event-wise leakage is, in general, not monotone. That is, given events E ⊂ E ′ , either ℓ(X → E) or ℓ(X → E ′ ) can be larger. Example 4. Recall the setup of Example 3. Let E = {3} and E ′ = {1, 3}, so that E ⊂ E ′ . Then, we have PY |X=x ({3}) 0.1 = log = 0, ℓ(X → E) = log max x PY ({3}) 0.1 whereas ℓ(X → E ′ ) = log max x
Algorithm 1 formalizes this procedure. B. Binary Envelope of Randomized Response Recall that PY (y) = qy for y ∈ [k], q1 ≤ q2 ≤ · · · ≤ qk , and N −1 X y=1
while, as computed above, ℓ(X → F ′ ) = log
1 0.55
Z:X−Y −Z z∈Z:PZ (z)≥δ
ℓPXZ (X → z).
over all (possibly randomized) events E satisfying PY (E) ≥ δ. Note that by Lemma 3(iv), we can restrict attention to events with probability exactly δ. Fix x ∈ [k] and write X PY |X=x (E) = wy PY |X=x (y), y∈[k]
PY (E) =
sup
ℓPXY (X → E),
X
wy PY (y),
y∈[k]
where wy ∈ [0, 1] denotes the probability that outcome y is included in the event E. This yields the optimization problem X max max wy PY |X=x (y), x∈[k] w∈[0,1]k
y∈[k]
subject to
(26)
X
wy qy = δ.
y∈[k]
Then, they showed that (26) admits the equivalent formulation E⊆Y:PY (E)≥δ
qy + θqN = δ,
y=1
PY |X=x (E) , PY (E) x∈[k]
< log 2.
The binary envelope and the procedure in Algorithm 1 are closely related to a privacy guarantee studied in [7]. In particular, Saeidian et al. [7] introduced a guarantee based on the worst-case PML of post-processed outcomes with probability at least δ, namely the quantity max
y=1
ℓPXY (X → E) = log max
A. Connection to Prior Work and Derivation of Algorithm 1
sup
N −1 X
qy ,
where δ ∈ (q1 , 1) and N ≥ 2. To compute εb for the k-RR mechanism, we use the equivalent formulation (27), which leads to a simpler argument than applying Algorithm 1. Our goal is to compute the largest value of
PY |X=x ({1, 3}) 1 = log > 0. PY ({1, 3}) 0.55
Now, let F = {1} and F ′ = {1, 3}, so that F ⊂ F ′ . We have ℓ(X → F) = log 2,
N X
qy < δ ≤
(27)
where the supremum is over all events in the generalized sense described above [7, Thm. 3]. It follows immediately from (23) that both (26) and (27) coincide with the binary PML envelope εb defined in (13). Saeidian et al. [7] also characterized the solution to (26) and (27). Fix x ∈ X and order the outputs y ∈ Y in decreasing information density i(x; y). Let Fk denote the set consisting of the first k outputs in this ordering, and let k ⋆ be the smallest index such that PY (Fk⋆ ) ≥ δ. If PY (Fk⋆ ) > δ, the optimal construction uses randomization at the boundary output so that the selected event has probability exactly δ. For each x ∈ X , this yields the value 1 κ(x) = PY |X=x (Fk⋆ −1 ) + ζ PY |X=x (yk⋆ ) , (28) δ
We next use the following claim to upper bound the objective; its proof is deferred to the end of this section. P Claim: For all w ∈ [0, 1]k satisfying y wy PY (y) = δ, we have X wy ≤ N − 1 + θ. y
Recall that PY |X=x (y) = α if y = x and PY |X=x (y) = β otherwise. Fixing x ∈ [k] and applying the claim, we obtain X X wy PY |X=x (y) = αwx + β wy y∈[k]
y̸=x
= (α − β)wx + β
X
wy
y∈[k]
≤ (α − β)wx + β(N − 1 + θ) ≤ α − β + β(N − 1 + θ) = α + β(N − 2 + θ).
Observe that this upper bound is achieved by taking x = 1 and choosing w1 = · · · = wN −1 = 1,
wN = θ,
R EFERENCES [1] [2]
which is feasible by construction. We therefore conclude that sup E:PY (E)≥δ
ℓPXY (X → E) = log max
x∈[k]
PY |X=x (E) PY (E)
α + β(N − 2 + θ) . δ The final piece is to prove the claim. Consider the optimization problem = log
max
k X
w∈[0,1]k
subject to
[4] [5]
[6]
wy
y=1
k X
[3]
[7]
qy wy = δ.
[8]
y=1
This is a linear program, hence it has an optimal solution at an extreme point of the feasible polytope. In particular, at an extreme point all but at most one coordinate of w is in {0, 1}. Since each coordinate wy contributes equally to the objecP tive, maximizing y wy amounts to setting as many wy ’s to 1 as possible. Because q1 ≤ q2 ≤ · · · ≤ qk , the optimal P strategy is to set w1 = 1, w2 = 1, . . . until the constraint y wy qy = δ is met. Thus, the choice w1 = · · · = wN −1 = 1,
wN = θ,
wN +1 = · · · = wk = 0,
[9]
[10] [11] [12]
is both feasible and optimal. Therefore, any feasible w satisfies k X y=1
as desired.
wy ≤ N − 1 + θ,
[13]
[14] [15] [16] [17]
[18]
[19] [20]
C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in Theory of cryptography conference, Springer, 2006, pp. 265–284. DOI: 10.1007/11681878 14 C. Dwork and A. Roth, “The Algorithmic Foundations of Differential Privacy,” Found. Trends Theor. Comput. Sci., vol. 9, no. 3-4, pp. 211– 407, Aug. 2014, ISSN: 1551-305X. DOI: 10.1561/0400000042 A. Machanavajjhala, D. Kifer, J. Abowd, J. Gehrke, and L. Vilhuber, “Privacy: Theory meets practice on the map,” in 2008 IEEE 24th international conference on data engineering, IEEE, 2008, pp. 277–286. D. Kifer and B.-R. Lin, “An axiomatic view of statistical privacy and utility,” Journal of Privacy and Confidentiality, vol. 4, no. 1, 2012. C. Dwork, G. N. Rothblum, and S. Vadhan, “Boosting and Differential Privacy,” in 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, Las Vegas, NV, USA: IEEE, Oct. 2010, pp. 51–60, ISBN : 978-1-4244-8525-3. DOI: 10.1109/FOCS.2010.12 S. Meiser, “Approximate and probabilistic differential privacy definitions,” Cryptology ePrint Archive, 2018. [Online]. Available: https : //eprint.iacr.org/2018/277 S. Saeidian, G. Cervia, T. J. Oechtering, and M. Skoglund, “Pointwise maximal leakage,” IEEE Transactions on Information Theory, vol. 69, no. 12, pp. 8054–8080, 2023. DOI: 10.1109/TIT.2023.3304378 S. Saeidian, G. Cervia, T. J. Oechtering, and M. Skoglund, “Rethinking disclosure prevention with pointwise maximal leakage,” Journal of Privacy and Confidentiality, vol. 15, no. 1, Mar. 2025. DOI: 10.29012/ jpc.893 M. S. Alvim, K. Chatzikokolakis, A. McIver, C. Morgan, C. Palamidessi, and G. Smith, “Additive and multiplicative notions of leakage, and their capacities,” in 2014 IEEE 27th Computer Security Foundations Symposium, 2014, pp. 308–322. DOI: 10.1109/CSF.2014. 29 I. Issa, A. B. Wagner, and S. Kamath, “An operational approach to information leakage,” IEEE Transactions on Information Theory, vol. 66, no. 3, pp. 1625–1657, 2019. DOI: 10.1109/TIT.2023.3341148 M. S. Alvim, K. Chatzikokolakis, A. McIver, C. Morgan, C. Palamidessi, and G. Smith, The Science of Quantitative Information Flow. Springer Cham, 2020. L. Grosse, S. Saeidian, and T. J. Oechtering, “Extremal Mechanisms for Pointwise Maximal Leakage,” IEEE Transactions on Information Forensics and Security, vol. 19, pp. 7952–7967, 2024, ISSN: 15566021. DOI: 10.1109/TIFS.2024.3449556 S. L. Warner, “Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias,” Journal of the American Statistical Association, vol. 60, no. 309, pp. 63–69, 1965, ISSN: 0162-1459. DOI: 10.2307/2283137 JSTOR: 2283137. P. Kairouz, S. Oh, and P. Viswanath, “Extremal mechanisms for local differential privacy,” Journal of Machine Learning Research, vol. 17, no. 1, pp. 492–542, Jan. 2016, ISSN: 1532-4435. S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith, “What can we learn privately?” In 49th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 531–540. J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy and statistical minimax rates,” in IEEE 54th Annual Symposium on Foundations of Computer Science, 2013, pp. 429–438. C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor, “Our data, ourselves: Privacy via distributed noise generation,” in Proceedings of the 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), vol. 4004, Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 486–503. DOI : 10.1007/11761679 29 B. Balle, G. Barthe, and M. Gaboardi, “Privacy amplification by subsampling: Tight analyses via couplings and divergences,” in Proceedings of the 32nd International Conference on Neural Information Processing Systems, ser. NIPS’18, Red Hook, NY, USA: Curran Associates Inc., 2018, pp. 6280–6290. C. L. Canonne, G. Kamath, and T. Steinke, “The Discrete Gaussian for Differential Privacy,” Journal of Privacy and Confidentiality, vol. 12, no. 1, 2022. DOI: 10.29012/jpc.784 S. P. Kasiviswanathan and A. Smith, “On the ’Semantics’ of Differential Privacy: A Bayesian Formulation,” Journal of Privacy and Confidentiality, vol. 6, no. 1, 2014, ISSN: 2575-8527. DOI: 10.29012/ jpc.v6i1.634
[21] [22] [23] [24] [25] [26]
[27]
[28]
[29]
S. Jonany, Correcting (ϵ, δ) misconception in differential privacy, 2022. [Online]. Available: https://medium.com/@sjonany/correcting-%CF% B5-%CE%B4-misconception-in-differential-privacy-e830dbdce0ab D. Kifer and B.-R. Lin, “An Axiomatic View of Statistical Privacy and Utility,” Journal of Privacy and Confidentiality, vol. 4, no. 1, Jul. 2012, ISSN: 2575-8527. DOI: 10.29012/jpc.v4i1.610 P. Embrechts and M. Hofert, “A note on generalized inverses,” Mathematical Methods of Operations Research, vol. 77, no. 3, pp. 423–432, 2013. J.-M. Dufour, “Distribution and quantile functions,” McGill University Report, 1995. B. Balle, G. Barthe, and M. Gaboardi, “Privacy Profiles and Amplification by Subsampling,” Journal of Privacy and Confidentiality, vol. 10, no. 1, 2020. DOI: 10.29012/jpc.726 I. Mironov, “Rényi Differential Privacy,” in 2017 IEEE 30th Computer Security Foundations Symposium (CSF), IEEE Computer Society, Aug. 2017, pp. 263–275, ISBN: 978-1-5386-3217-8. DOI: 10 . 1109 / CSF. 2017.11 M. Bun and T. Steinke, “Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds,” in Proceedings, Part I, of the 14th International Conference on Theory of Cryptography - Volume 9985, Berlin, Heidelberg: Springer-Verlag, Oct. 2016, pp. 635–658, ISBN : 978-3-662-53640-7. DOI: 10.1007/978-3-662-53641-4 24 J. Dong, A. Roth, and W. J. Su, “Gaussian Differential Privacy,” Journal of the Royal Statistical Society Series B: Statistical Methodology, vol. 84, no. 1, pp. 3–37, Feb. 2022, ISSN: 1369-7412. DOI: 10.1111/ rssb.12454 A. McIver, C. Morgan, G. Smith, B. Espinoza, and L. Meinicke, “Abstract Channels and Their Robust Information-Leakage Ordering,” in Principles of Security and Trust, Berlin, Heidelberg: Springer, 2014, pp. 83–102, ISBN: 978-3-642-54792-8. DOI: 10 . 1007 / 978 - 3 - 642 54792-8 5