arXiv:2605.26465v1 [cs.CR] 26 May 2026
Beyond Epsilon: A Principled QIF Framework for Local Differential Privacy Ramon G. Gonze‡
Natasha Fernandes‡
Héber H. Arcolezi¶
Institut Polytechnique de Paris Universidade Federal de Minas Gerais Paris, France – Belo Horizonte, Brazil [email protected]
Macquarie University Sydney, NSW Australia [email protected]
ÉTS Montréal, Montréal, Canada Inria, Grenoble, France [email protected]
Catuscia Palamidessi
Nataliia Bielova
Inria, Institut Polytechnique de Paris Paris, France [email protected]
Inria Centre at University Côte d’Azur Sophia Antipolis, France [email protected]
Abstract—Local Differential Privacy (LDP) has become the de facto standard for privacy-preserving data collection in large-scale systems, in particular for the purpose of estimating frequencies. However, the current research landscape lacks a systematic and principled way to compare LDP protocols. The parameter ε of LDP is considered the measure of privacy, but it only bounds worst-case distinguishability. Other comparisons rely on utility-driven analyses, where mechanisms are ranked based on their ability to preserve data utility for a given privacy budget ε. Both such kinds of comparisons fail to account for the strength of protocols against diverse attacker models. In this paper, we propose a framework for analyzing LDP frequency estimation protocols through the lens of Quantitative Information Flow (QIF). By modeling LDP mechanisms as probabilistic channels, we leverage the concept of refinement (Blackwell ordering) to establish more principled classifications. This approach allows us to determine when one protocol is intrinsically superior to another for all possible adversaries, and to discuss the implications for utility. In particular, our analysis uncovers cases where protocols previously deemed “optimal” are, in fact, incomparable with, or strictly dominated by, other protocols. We provide a formal QIF-based treatment of seven state-of-the-art LDP protocols, including Generalized Randomized Response (GRR), Subset Selection (SS), local hashing variants (BLH, OLH), unary encoding schemes (SUE, OUE), and Thresholding with Histogram Encoding (THE). This perspective bridges the gap between the LDP and formal methods communities and enables principled, adversary-aware reasoning about locally private systems. Index Terms—Local Differential Privacy, Quantitative Information Flow, Information Leakage, Channel Refinement.
I. I NTRODUCTION As the demand for privacy-preserving data collection continues to grow, Local Differential Privacy (LDP) [1] has emerged as a robust technique for safeguarding individual privacy. Unlike traditional differential privacy [2], which requires a trusted aggregator, LDP enables users to independently perturb their data before transmission. This ensures that sensitive information remains protected, even if the data ‡ These authors contributed equally to this work. ¶ Work done while at Inria.
collector is compromised. As a result, LDP has been widely adopted in large-scale frequency monitoring systems such as the Google Chrome browser [3], Apple iOS/macOS [4], Google Gboard [5], and Windows 10 operating system [6]. Frequency estimation protocols [7] constitute a core building block of many LDP deployments. As a result, their comparative evaluation plays a central role in the design and selection of LDP mechanisms1 . However, current evaluation approaches fall short of comparing the strength of the various LDP mechanisms against different kinds of attackers. Indeed, they consider the LDP parameter ε as the only measure of privacy, and rank protocols on the basis of their utility–in this case, the precision of the frequency estimate, evaluated in terms of error-based metrics–for the same privacy budget ε. While such classifications are valuable from a statistical perspective, they provide only a partial and utility-dependent view of privacy protection, consequently leading to misleading comparisons of the privacy-utility trade-offs: As a matter of fact, ε only bounds the worst-case distinguishability between data points, and two protocols satisfying the same ε-LDP guarantee may exhibit significantly different leakage behaviors under realistic inference attacks, such as data reconstruction [8] or re-identification [9]. Therefore, from a privacy standpoint, this raises a fundamental question: What does it mean for one LDP protocol to be strictly more private than another? To address this gap, we advocate for a Quantitative Information Flow (QIF) [10] perspective on LDP. QIF provides a principled framework for measuring information leakage of LDP protocols by representing randomized systems as information-theoretic channels and quantifying the attacker’s expected gain for a wide range of threat models. Crucially, QIF 1 “LDP mechanisms” denotes the obfuscation methods, whereas “frequency estimation protocols” refers to these LDP mechanisms together with any postprocessing technique to recover frequencies or histograms from the obfuscated data. Since postprocessing does not weaken privacy guarantees, we often use these two terms interchangeably throughout this paper.
supports refinement relations, where one channel is deemed strictly more private than another if it minimizes the potential gain for any attacker, regardless of their prior knowledge or specific objectives. This refinement-based approach offers a more robust and comprehensive framework for evaluating protocol superiority than traditional comparisons limited to ε and utility metrics. As a result, we are able to uncover settings in which protocols commonly regarded as “optimal” under error-based metrics are in fact incomparable to, or even strictly dominated by, other protocols. In this paper, we present a formal QIF-based analysis of widely used LDP frequency estimation protocols, including Generalized Randomized Response (GRR) [11], Subset Selection (SS) [12], [13], Binary Local Hashing (BLH) [14], Optimized Local Hashing (OLH) [7], Symmetric Unary Encoding (SUE) [3], Optimized Unary Encoding (OUE) [7], and Thresholding with Histogram Encoding (THE) [7]. These mechanisms form the core of many real-world LDP deployments. For instance, SUE underlies Google’s RAPPOR [3] and Microsoft’s dBitFlipPM [6] telemetry-based systems, while SS has been recently integrated into Google’s Gboard [5]. Similarly, Apple’s Count Mean Sketch mechanism [4] relies on data structures closely related to local hashing techniques, such as BLH and OLH. Finally, THE builds on the widely used Laplace mechanism [2], a building block of practical differential privacy systems (e.g., LinkedIn API [15]). For each of the above protocols, we derive the exact channel matrix induced by the local randomization procedure and analyze its leakage properties using standard QIF vulnerability measures. To support this analysis, we adopt f -differential privacy (f -DP) [16], which characterizes privacy guarantees in terms of hypothesis testing, and supports comparison of privacy mechanisms using trade-off functions derived from the most powerful hypothesis tests via the celebrated NeymanPearson lemma. This provides a unifying abstraction that aligns naturally with QIF-based refinement [17]. Within this framework, ε-LDP appears as a coarse worst-case bound, while QIF-based refinement relations expose finer-grained distinctions between protocols that ε alone cannot capture. A. Contribution The main contributions of our paper are as follows: • We provide a unified QIF-based framework for analyzing and comparing LDP frequency estimation protocols through channel matrices and refinement relations, enabling metric-independent privacy comparisons across adversaries and utility functions. • We formally bridge the LDP and QIF literatures by showing that data reconstruction attacks studied in prior work [8], [9] coincide with standard QIF notions of vulnerability. In particular, we demonstrate that the expected success of such attacks corresponds to the Bayes vulnerability induced by the LDP channel. • Leveraging this channel-based formulation, we revisit the analysis of Local Hashing (LH) protocols, including BLH and OLH. We identify and correct an error in the expected
data reconstruction attack analysis reported by [8], and derive the correct Bayes risk for LH-based protocols via averaged vulnerability. • We study refinement relations between LDP protocols, uncovering new refinements, which are experimentally corroborated on real-world datasets. II. R ELATED W ORK Utility-driven LDP protocol design. A variety of LDPbased frequency estimation protocols have been introduced, all aiming to enhance the privacy-utility trade-off [7], [3], [13], [12], [18]. In these works, as well as in most of the differential privacy literature, privacy is characterized by the parameter ε, while utility is evaluated through estimation error, commonly using mean squared error or l1 and l2 distances [11]. Within this framework, notions of optimality are inherently metricdependent. While these analyses provide valuable insights into estimation accuracy, they do not offer a comparison of privacy leakage across protocols, nor do they induce an ordering that is independent of the chosen utility metric. Inference attacks on LDP protocols. Beyond utility analysis, more recently, a few works [8], [9], [19], [20] have analyzed LDP mechanisms through an adversarial lens. For instance, data reconstruction attacks [8], [19] aim to infer individual user values from locally perturbed reports, while re-identification attacks [9] attempt to link anonymised or perturbed records back to individuals. These attacks reveal that two mechanisms satisfying the same ε-LDP guarantee can exhibit significantly different levels of privacy violations. However, existing attack analyses typically focus on specific adversarial objectives and threat models, such as maximumlikelihood reconstruction or linkage success rates. As a result, they provide valuable empirical or analytical evidence of leakage, but remain tied to particular attack strategies. Consequently, these approaches do not yield a general, attackerindependent ordering of LDP protocols, nor do they explain how different attacks relate to one another from a privacy perspective. Relation between DP/LDP and QIF. There have been several works exploring the connection between differential privacy (DP) and QIF by modeling randomized mechanisms as information-theoretic channels and interpreting privacy as a bound on information leakage. Early results showed that εDP implies general, prior-independent upper bounds on minentropy and Rényi-based leakage measures, thus relating DP guarantees to worst-case QIF notions of leakage [21], [22]. This perspective was further developed by explicitly studying DP mechanisms through the dual lenses of information leakage and utility within a unified channel framework [23]. More recently, refinement-based approaches from QIF have been applied to DP, providing order-theoretic characterizations of worst-case leakage and enabling systematic comparisons between mechanisms [24]. LDP mechanisms have similarly been analyzed as constrained channels, and QIF measures such as maximal leakage have been used to derive capacitystyle interpretations and worst-case leakage bounds [25], [26].
One specific example of an LDP mechanism analyzed using constrained channels is Randomized Response (or GRR), for which the authors in [27] measured the privacy amplification achieved via shuffling. None of the above works, however, uses a QIF approach to compare LDP mechanisms.
gain over all possible observations. Leakage is measured as the (multiplicative) difference between the adversary’s prior and posterior knowledge. Formally, the adversary’s prior expected gain is given by X Vg (π) = max πx g(w, x). (4) w
III. BACKGROUND AND P RELIMINARIES Throughout the paper, let [n] = {1, 2, . . . , n} denote a set of integers, X be the input space with finite domain of size k = |X |, and Y the set of (perturbed) outputs of a protocol. A. Local Differential Privacy
y
Local Differential Privacy (LDP) [1] formalizes the idea that a single user can protect her data before it ever leaves her device. Let X be a finite input domain of size k=|X | and let Y be the (finite) output domain of a randomized mechanism M:X→Y. We denote the random variables of interest by X ∈ X and Y =M(X) ∈ Y. Definition 1 (ε-Local Differential Privacy). M is said to satisfy ε-local differential privacy (ε-LDP) if, for every pair of inputs x, x′∈X and for every output y∈Y, Pr M(x) = y ≤ eε Pr M(x′ ) = y . (1) Inequality (1) upper-bounds how much more likely any particular output can be under one input than under another. The smaller ε is, the closer the two probabilities are forced to be, and hence the stronger the privacy guarantee. B. Quantitative Information Flow (QIF) QIF is a framework for modeling Bayesian attacks against systems represented as information-theoretic channels. These attacks give rise to metrics that quantify how much the channel reveals about a secret. In our setting, the channel is the LDP mechanism M, whose behavior is fully captured by the rowstochastic channel matrix
x
This is also called the vulnerability of the secret. The adversary’s posterior expected gain is X X Vg (π, C) = max πx Cx,y g(w, x), (5) w
x
with expected leakage Lg (π, C) =
Vg (π, C) . Vg (π)
In the max-case, the prior gain is 2 VgMAX (π) = max πx g(w, x), w,x
x ∈ X , y ∈ Y.
Given a prior distribution π over X , the induced joint distribution of the input X and the output Y is PrX,Y [x, y] = πx Cx,y .
(2)
The marginal of Y is obtained by summing (2) over all inputs: X PrY [y] = πx Cx,y . (3) x∈X
When the prior is uniform, πx = 1/k, P so PrX,Y [x, y] = Cx,y /k and (3) simplifies to PrY [y] = k1 x Cx,y . Our adversarial model is that of a Bayesian adversary with some prior knowledge π : DX represented as a distribution over secrets X , a gain function g : W×X → R describing their gain on taking action w ∈ W when the secret has value x ∈ X , and who has knowledge of the mechanism C. We consider 2 classes of adversaries: the average-case adversary, whose success is measured as their expected gain after making an observation from the system; and the maxcase adversary, whose success is measured as the maximum
(7)
and the posterior max-case gain is VgMAX (π, C) = max πx Cx,y g(w, x), y,x,w
(8)
with max-case leakage LMAX (π, C) = g
VgMAX (π, C) . VgMAX (π)
(9)
We also make use of two robust notions from QIF: 1) Capacity which measures the maximum leakage of a system, quantified over all priors and all possible adversaries (within some class). In particular, we note the following. • Average-case capacity, also known as Bayes capacity is given by [10] X ML(C) = max Lg (π, C) = max Cx,y . (10) π,g
Cx,y = PrY |X [y | x],
(6)
y
x
The Bayes capacity is a tight upper bound on all averagecase g-leakage measures, i.e., it strictly bounds the leakage for any gain function and prior of the adversary (“Miracle Theorem” [28]). One benefit of the Bayes capacity is that it is easy to calculate. In fact, it equals the sum of the maximum values in each column of the channel [29]. • Max-case capacity is given by [30] MLMAX (C) = max LMAX (π, C) = eε , g π,g
(11)
where ε is the minimum LDP guarantee for channel C. The max-case capacity is a tight upper bound on all average-case and max-case g-leakage measures [30]. 2) Refinement which is a binary relation and partial order on channels; we say A refines B, written B ⊑ A, if A leaks no more than B to any average-case adversary for any prior; 2 Note here we are using the g-leakage version of max-case, which is slightly different from the max-case vulnerability normally defined in QIF, but which we choose for its relevance to the study of LDP.
equivalently, B ⊑ A if there exists a channel W such that B·W = A where · is matrix multiplication. We recall that average-case refinement is stronger than max-case: [24] A ⊑ B =⇒ A ⊑
MAX
B
(12)
where ⊑MAX is the max-case equivalent refinement. 3 We will also make use of a result from [17] showing that, in the case of binary channels, refinement is equivalent to the f -differential privacy ordering between channels. a) f-Differential Privacy: Introduced in [16], f differential privacy (f -DP) is a recent privacy definition allowing more nuanced privacy loss assessments and analyses than traditional differential privacy. f -DP models secrets (adjacent datasets) as hypotheses H0 , H1 , and defines indistinguishability of secrets using the Type-I (α) and Type-II (β) error rates for the most powerful test at various significance levels α (as defined in the Neyman-Pearson lemma). This gives rise to a trade-off function TM (α) = β describing this relationship for a particular mechanism M . These trade-off functions can be compared: if TM ≤ TN pointwise, for mechanisms M, N then N is more private than M . It was shown in [17] that this is exactly equivalent to the QIF notion of refinement. That is, TM ≤ TN ⇐⇒ M ⊑ N .
(13)
In the case of 2x2 channels, the construction of the tradeoff function is trivial: by swapping columns if necessary 4 , the channel C should be put into the form: 1−α α (14) β 1−β where β ≤ 1 − α. Then the trade-off function TC is the piecewise linear function joining (0, 1), (α, β) and (1, 0). In this paper, we will use trade-off functions to compare channels on 2 secrets under refinement.
We equip our adversary with a uniform prior πx = 1/|X | = 1/k. 5 Bayes’ rule shows that PrX|Y [x | y] =
so the Bayes-optimal (risk-minimizing) decision rule is the posterior maximum. That is, x b(y) = arg max PrX|Y [x | y] = arg max Cx,y . x∈X
x∈X
A. Attack Model and Leakage for Data Reconstruction As well as reasoning about general safety properties using QIF, we wish to also reason about a particular threat of relevance to our setting: the data reconstruction attack, a onetry attack by an adversary wishing to guess the secret exactly. We model the LDP mechanism as a noisy channel with matrix entries Cx,y =PrY |X [y | x]. Our adversary makes a single observation Y = y from the mechanism, and outputs a guess x b ∈ X with the goal of recovering the true input X = x. 3 This holds for both the g-leakage definition and the traditional definition
of max-case. 4 We note that swapping columns does not change the information leakage semantics of the channel.
(15)
Remark: We only consider finite X in this paper, so the above (uniform prior, argmax) is well-defined. We can now define the Adversarial Success Rate [8] (or, data reconstruction attack [19]), which measures the ratio of clients whose true value is correctly predicted by the adversary. b =x Definition 2 (Adversarial Success Rate (ASR)). Let X b(Y ) be the random variable defined by the rule (15). The Adversarial Success Rate is computed as h i b =X |Y ] ASR(C) = E PrX|Y [X X (16) = PrY [y] max PrX|Y [x | y]. x∈X
y∈Y
where C is the channel in (15). Connection to QIF. The 0/1-gain function (also known as Bayes gain function), defined g(w, x) = 1 if w = x else 0 for w ∈ W = X 6 , represents the gain of an adversary whose goal is to guess the secret in 1 try. The posterior vulnerability of a channel C under this gain function is given by X X V1 (π, C) = max πx Cx,y g(w, x) y∈Y
=
X y∈Y
=
X y∈Y
IV. L EAKAGE M EASURES In this section, we introduce some leakage measures used in the LDP literature and identify their relationship to QIF measures. This will guide our choice of leakage measures to study in this paper.
πx Cx,y ∝ Cx,y , PrY [y]
=
X y∈Y
w
x∈X
max πx Cx,y x∈X
max Pr[y] x∈X
πx Cx,y Pr[y]
Pr[y] max Pr[x | y] x∈X
which is exactly the ASR given in Eqn (16). We therefore have the identity ASR(C) = V1 (π, C) .
(17)
This tells us that the adversarial success rate measures the maximum posterior vulnerability of the system with regard to an attacker who is trying to guess the secret in 1 try from a single observation. Since our attacker is equipped with a uniform prior, we then have a direct connection with the average-case capacity. That is, ASR(C) = ML(C)/k .
(18)
5 The uniform prior maximizes the attacker’s uncertainty; any non-uniform prior only makes reconstruction easier. This result comes from Bayes capacity, presented in Eq. (18), proposed in [28]. 6 Throughout the paper, we may refer to the vulnerabilities induced by the Bayes gain function as “1” instead of explicitly using g.
B. Information-Theoretic Leakage Measure A number of commonly used leakage measures are derived from information-theoretic quantities and are sometimes employed to assess leakage in DP mechanisms. One such measure is min-entropy leakage, which extends Rényi min-entropy to a measure of information leakage and is defined as follows. Definition 3 (Min-entropy leakage). Let X, Y be random variables taking values in finite sets X , Y respectively. Then the min-entropy leakage of X given Y is defined L∞ (X|Y ) = H∞ (X) − H∞ (X|Y ) ,
(19)
where ∞ (X) = log maxx PrX [x] HP H∞ (X|Y ) = log y PrY [y] maxx PrX|Y [x|y] .
and
Connection to QIF. It was shown in [28] that for a channel C : X → Y and uniform prior on X , we have: L∞ (X|Y ) = log(ML(C)) .
(20)
We can transfer the definitions of random variables X and Y to elements of QIF. Let X be the set of secrets (space of X) and π the prior distribution on X . Let C be a channel that provides the conditional probability Cx,y = PrY |X [y | x] for the set of outputs Y (space of Y ). Setting a uniform prior πx = 1/|X | = 1/k, and the Bayes gain function, defined as g(w, x) = 1 if w = x else 0 for w ∈ W = X , we have that L∞ (X|Y ) = − log max PrX [x] x
! + log
X
PrY [y] max PrX|Y [x|y]
y
the literature [7]) and concentrates on the information leakage induced by the local randomization. We derive the corresponding information-channel representations and provide an initial analysis of their leakage properties. In later sections, these channel representations are used to analyze refinement relations between the mechanisms. A. Generalized Randomized Response (GRR) Generalized Randomized Response (GRR) [11] is a mechanism where each input is reported truthfully with probability p and as any other possible value with probability 1 − p. Definition 4 (GRR). Let X = {x1 , x2 , . . . , xk } and Y = {y1 , y2 , . . . , yk } be finite domains, with Y = X and |X | = k, k ≥ 2. Then the GRR mechanism for ε ≥ 0 is constructed as ( eε if y = x, p = eε +k−1 (21) Pr[GRR(x) = y] = 1 q = eε +k−1 if y ̸= x, where y ∈ Y is the perturbed value sent to the server. Channel Matrix: The channel matrix Rε for GRR is defined ( p if i = j, Rεij = q if i ̸= j. Example. For instance, the channel matrix for GRR with k = 3 and ε = ln 2: 1/2 1/4 1/4 p q q Rln 2 = q p q = 1/4 1/2 1/4 . 1/4 1/4 1/2 q q p
x
= − log Vg (π) + log Vg (π, C)
= − log(1/k) + log(ML(C)/k) = log(ML(C)).
Summary of Leakage Measures. Due to the strong connection between several of the measures identified in this section, we can limit our attention to 2 leakages: 1) the Bayes capacity (ML), which upper bounds all average-case leakages; and 2) the Max-case capacity (MLMAX ), corresponding to the ε of LDP, which upper bounds all average-case and maxcase leakages. We note the relationship, for all channels C, that MLMAX (C) ≥ ML(C). However, as has previously been shown [24], this ordering does not imply an ordering between channels. That is, it can be that MLMAX (A) > MLMAX (B) but ML(A) < ML(B). V. LDP P ROTOCOLS AND THEIR L EAKAGES In this section, we present the ε-LDP protocols under study, focusing on their local perturbation mechanisms. Proofs can be found in the appendix. While these protocols are typically paired with unbiased frequency estimators, our analysis deliberately abstracts away from the estimation step (known in
Leakage Analysis using Bayes capacity: Since p > q it is easy to see that every column maximum is p and so we have ML(Rε ) = pk = B. Subset Selection (SS)
keε eε + k − 1
(22)
Subset Selection (SS) [12], [13] is a protocol that selects a subset of values from the input space and reports it. The subset size ω is determined by ε and k; it is the value that minimizes the variance. Definition 5 (SS). Let X = {x1 , xj2 , . . . ,m xk } be a finite k domain, let ε ≥ 0 and let ω = max 1, eε +1 . 7 Then, given x ∈ X , an output y of the SS mechanism is constructed as follows: ε 1) Add the true value x to y with probability p = ωeεωe +k−ω . 2) If x was added, then ω − 1 values are sampled from X \ {x} uniformly at random (without replacement) and are added to y. 3) If x was not added, then ω values are sampled from X \ {x} uniformly at random (without replacement) and are added to y. The subset y is then sent to the server. 7 The notation ⌊x⌉ denotes the closest integer value to x.
Channel Matrix: The channel matrix SS ε for SS reflects the probability of each input value being included in the reported subset. For input xi and subset yj : 1 p · k−1 if xi ∈ yj , (ω−1) ε SS i,j = 1 (1 − p) · k−1 if xi ∈ / yj . ( ω )
Channel Matrix: The channel matrix LHε for Local Hashing reflects the probability of a pair (the hash function and the perturbed encoded value) being released. The set of inputs is X = {x1 , . . . , xk } = [k] and the channel’s set of output pairs is Y = {(yh , yp ) | yh ∈ H and yp ∈ [g]}. For input x and pair y:
Example. For instance, the channel matrix for SS with k = 3 and ω = 2 is: X y∈ = {{0, 1}, {0, 2}, {1, 2}}. 2
X = {0, 1, 2},
p·
1
(21)
p · 12 SS ε = (1) (1 − p) · 12 (2)
p·
1
(21) (1 − p) · 12 (2) p · 12 (1)
2 = 1, 2
p=
1 (22) p · 12 (1) . 1 p· 2 (1)
(1 − p) ·
2eε . 2eε + 3 − 2
w−1
Otherwise we have 1
ML(C) = k(1 − p)· k−1 w
C. Local Hashing (LH) LH protocols [7], [14] use hash functions to map the input data x ∈ X to a new domain [g], and then obfuscate the hash value with GRR. There are two variations of LH mechanisms: (i) Binary LH (BLH) [14] that just sets g = 2, and (ii) Optimized LH (OLH) [7] that selects g = ⌊eε + 1⌉ to minimize the variance. Definition 6 (LH). Let X = {x1 , x2 , . . . , xk } be the set of input values and let H be a universal hash function family such that each h ∈ H hashes a value x ∈ X into [g], i.e., h : [k] → [g], for k, g ≥ 2. Given an input x, an output y = (yh , yp ) of LH is constructed as follows: 1) Encoding step: A hash function yh ∈ H is chosen uniformly at random, and applied to x to produce the encoded value ye = yh (x). 2) Perturbation step: Given the encoded value ye , we now perturb it using GRR mechanism, thus producing GRR(ye ) = yp . Finally the output consists of the pair (yh , yp ) of the hash function yh and the perturbed encoded value yp . if ye = i, if ye ̸= i.
, if yh (x) = yp , if yh (x) ̸= yp .
(24)
A0LH is a random choice x̂ = Uniform ([k]), if 1LH = ∅; 1 • ALH is a random choice x̂ = Uniform (1LH ), otherwise.
•
Leakage Analysis using Bayes capacity: The Bayes capacity for the SS protocol depends on whether 1 1 p· k−1 > (1 − p)· k−1 . If this is true, then pk > w and we (w−1) (w) have 1 ML(C) = kp· k−1
( eε p = eε +g−1 , ∀i ∈ [g], Pr[yp = i] = 1 q = eε +g−1 ,
ε 1 · e g k eε +g−1 1 1 · g k eε +g−1
Leakage Analysis using Bayes capacity: We start by reasoning about ASR of LH, and following the equivalence of Eqn (18), we obtain ML(LHε ) by multiplying ASR by k. For each reported pair (yh , yp ), the support set for LH protocols consists of all values x ∈ X that hash to yp and remain equal to yp after the application of GRR. This support set is denoted by 1LH = {x | yh (x) = yp }. Based on the support set derived from each user’s report, the adversary can employ one of two possible attack strategies, denoted by ALH [8], [9].
Where: 2 = 2, 1
( LHεx,y =
(23)
The expected ASR of LH protocols was derived in [8] as eε (eε + g − 1) · max
n
o.
k g,1
(25)
However, this expression does not hold in general. In particular, for small domain sizes (e.g., k = 2), Eq. (25) did not match our experimental evaluations. Using the definition of the LH channel in Eqn (24), we obtained the following result that matches experimental evaluations for any value of k. Proposition 1. [ASR of Local Hashing] Let LHε be the channel defined in Eqn (24). Then ASR(LHε ) =
eε g k + (g − 1)k (1 − eε ) . (eε + g − 1)(kg k−1 )
(26)
In Section VII, we present an empirical evaluation comparing Equations (25) and (26). From Eqn (26), we derive the Bayes capacity: ML(LHε ) =
eε g k + (g − 1)k (1 − eε ) . (eε + g − 1)g k−1
(27)
D. Unary Encoding Protocols Unary Encoding (UE) protocols encode the input value i as a one-hot k-dimensional vector (in which the i-th bit is 1) and output a k-dimensional bit vector by obfuscating each bit of the input independently. Definition 7 (UE). Let X = {x1 , x2 , . . . , xk }, where each xi is a one-hot encoded vector of length k in which the bit at position i is set to 1, and the remaining bits are 0. Given
an input x, an output vector y from a Unary Encoding (UE) protocol is constructed as follows: ( p, if x[i] = 1, ∀i ∈ [k] : Pr[y[i] = 1] = q, if x[i] = 0. The output y is sent to the server. ε Channel Matrix: Each entry Cij in the channel matrix for UE protocols represents the probability of obtaining the output yj given the input xi . Formally, for each bit in the input vector xi , we can compute:
Pr[yj [m] = 1|xi [m] = 1] = p Pr[yj [m] = 0|xi [m] = 1] = 1 − p
Summing these gives: k X k k−i+1 i−1 ML(SUE ε ) = ( p q ) + pk−1 q i i=1 k X k k−i i p = ( p q × ) + pk−1 q q i i=1 k X k k p k k−i i p = ( p × p q × ) + pk−1 q − q 0 q i i=0 = (p + q)k + pk−1 q − pk+1 q −1 q p = (p + q)k + pk ( − ) p q Recalling that p + q = 1 this simplifies to
Pr[yj [m] = 1|xi [m] = 0] = q
ML(SUE ε ) = 1 + pk ((1 − p)2 − p2 )/(p(1 − p))
Pr[yj [m] = 0|xi [m] = 0] = 1 − q
= 1 + pk−1 (1 − 2p)/(1 − p)
Thus, the probability of obtaining output yj given input xi is: ε Cij = Pr[yj |xi ] =
k Y
Bayes capacity for OUE: The mechanism for OUE operating on bits has the form
Pr[yj [m]|xi [m]]
The following two variations of UE protocols have been studied. 1) SUE: The Symmetric UE protocol (SUE) [3] assigns eε/2 p = eε/2 and q = eε/21 +1 in Definition 7 so that p + q = 1. +1 For example, the SUE mechanism for k = 2 has a channel matrix 00 01 102 11 01 pq p2 q pq 10 pq q 2 p2 pq 2) OUE: The Optimal UE protocol (OUE) [7] was introduced to minimize the variance of the unbiased frequency estimator under ε-LDP among UE protocols. To achieve this objective, OUE assigns p = 12 and q = eε1+1 in Definition 7. For example, the OUE mechanism for k = 2 has a channel matrix 00 01 (1 − p)(1 − q) 10 (1 − p)(1 − q)
0 0 1−q 1 1/2
m=1
01 p(1 − q) (1 − p)q
10 q(1 − p) p(1 − q)
11 pq pq
Leakage Analysis using Bayes capacity for SUE: Notice that the mechanism for SUE operating on bits has the form 0 1 0 p q 1 q p Thus, given that p > q, the Bayes capacity for SUE can be computed using the closest input one-hot vector (in Manhattan distance) to the output vector. This yields k−1 • y all 0’s: maximum posterior is p q • y containing i 1’s and k − i 0’s: maximum posterior is pk−i+1 q i−1 and there are ki such outputs
1 q 1/2
Given 1−q ≥ 1/2, we can again compute the Bayes capacity using the closest input vector to the observed output. This yields: 1 k−1 • y containing all 0’s: maximum posterior is 2 (1 − q) • y containing i 1’s and k − i 0’s: maximum posterior is 1 i−1 (1 − q)k−i and there are ki such outputs. 2q Summing these yields: k 1 1 X k i−1 ML(OUE ε ) = (1 − q)k−1 + q (1 − q)k−i 2 2 i=1 i k 1 X k i 1 k−1 + q (1 − q)k−i = (1 − q) 2 2q i=0 i −
1 (1 − q)k 2q
1 q(1 − q)k−1 + 1 − (1 − q)k 2q 1 = (1 − q)k−1 (2q − 1) + 1 . 2q =
E. Thresholding with Histogram Encoding (THE) Like the UE protocols, Thresholding with Histogram Encoding (THE) [7] encodes the input value i as a one-hot kdimensional vector, x = [0, 0, . . . , 1, 0, . . . , 0], in which only the i-th component is 1. It outputs a k-dimensional bit vector by independently perturbing each input bit. Definition 8 (THE). Let X = {x1 , x2 , . . . , xk }, where each xi is a one-hot encoded vector of length k in which the bit at position i is set to 1, and the remaining bits are 0. Given an input x and a threshold θ ∈ (0.5, 1), an output vector y from a THE protocol is constructed as follows:
1) For each i ∈ [k], y[i] := x[i] + Z, where Z ∼ Lap( 2ε ) is a random variable drawn from a Laplace distribution with mean 0 and scale 2ε . ( 1, if y[i] > θ 2) For each i ∈ [k], y[i] = 0, if y[i] ≤ θ The resulting output vector y is a binary vector in {0, 1}k , which satisfies the following for all i ∈ [k] [7]: 1 ε(θ−1) Pr[y[i] = 1 | x[i] = 1] = 1 − e 2 =p 2 1 εθ Pr[y[i] = 1 | x[i] = 0] = e− 2 =q 2 Channel Matrix: Each entry Tijε of the THE channel matrix represents the probability of obtaining the output vector yj given the input vector xi and is given by: Tijε =
k Y m=1
Pr(yj [m] | xi [m]).
Example The channel matrix of THE for k = 2 is: T ε=
(1 − p)(1 − q) (1 − p)(1 − q)
(1 − p)q p(1 − q)
p(1 − q) (1 − p)q
pq pq
Leakage Analysis using Bayes capacity: Observe that the mechanism operating on bits has the form 1−q q 1−p p where p > q. As with the UE mechanisms, we can compute the Bayes capacity using the closest input one-hot vector to the observed (output) vector. This gives k−1 • y all 0’s: maximum posterior is (1 − p)(1 − q) • y containing i 1’s and k − i 0’s: maximum posterior is pq i−1 (1 − q)k−i and there are ki such outputs. Summing these gives: k X k i−1 ε k−1 ML(T ) = (1 − p)(1 − q) +p q (1 − q)k−i i i=1 k pX k i q (1 − q)k−i = (1 − p)(1 − q)k−1 + q i=1 i p p = (1 − p)(1 − q)k−1 + − (1 − q)k q q p p k−1 = (1 − q) 1− + . q q VI. F ORMAL A NALYSIS OF LDP P ROTOCOLS All proofs for this section can be found in the appendix. A. Refinement Families In this section, we study the relationship between LDP protocols represented as channels from the perspective of refinement. Recall that the refinement relation ⊑ tells us whether one channel is safer than another against any adversary (average
or max-case), regardless of their prior knowledge. We begin by considering channels within the same “family”. Definition 9 (ε-family). Let Mε : X → Y be a mechanism parametrized by ε so that for every ε ≥ 0 we have that Mε is ε-DP. We call the set of mechanisms Mε an ε-family and denote it by FM . Definition 10 (Refinement family). Let FM be an ε-family of mechanisms. We call FM a refinement family if ε ≥ ε′ ⇐⇒ Mε ⊑ Mε′ We note that for Def 10 to hold, it is sufficient to show the forward direction only, since the reverse direction is already known to hold in general [24]. Refinement families are important for managing the privacyutility trade-off. Theorem 1. [Monotonicity of utility] Let FM be a refinement family of mechanisms. Let U(M ) be a utility function that measures the expected loss of the mechanism M to an analyst who observes a value y and makes an optimal guess ŷ. Then the utility function U(M ) is monotonic on ε. That is, ε ≥ ε′ ⇐⇒ U(Mε ) ≥ U(Mε′ ) . Proof. This follows directly from refinement, since A ⊑ B ⇐⇒ U(A) ≥ U(B) for all utility functions U expressible using loss functions under expectation. We also recall Eqn (14) describing the 2x2 channel in terms of α and β, which we use in the following manner: Definition 11. Let C be a 2x2 channel written as: 1−α α C= β 1−β where β ≤ 1 − α. Then the trade-off function TC is characterized by the point (α, β) which we call the trade-off point for C. We now show how trade-off points relate to refinement. Lemma 1. Let C, D be 2x2 channels with trade-off points (αC , βC ) and (αD , βD ) respectively. Then the following statements are equivalent: 1) C ⊑ D 2) The posteriors of D under a uniform prior are inside the convex hull of the posteriors of C βC βD 1−βD C 3) 1−α ≤ 1−α and 1−β αC ≥ αD . C D The following sufficiency condition will simplify some of the proofs. Lemma 2. Let C, D be 2x2 channels with trade-off points (αC , βC ) and (αD , βD ) respectively. Then αC ≤ αD and βC ≤ βD implies that C ⊑ D. We are now ready to study the refinement properties of the LDP protocols considered in this paper.
1.0
Similarly, we find that SUE mechanisms also form a refinement family.
fT,θ
0.8
fT0,θ
Lemma 7. The family FSUE of SUE mechanisms is a refinement family.
β
0.6 0.4 0.2 0.0 0.0
0.2
0.4
0.6
0.8
1.0
α
Fig. 1: Example showing ordering between f -privacy trade-off functions for THE mechanisms when α, β values are ordered, i.e. α > α′ and β > β ′ .
1) The GRR Mechanism: The refinement order of the GRR mechanism parametrized by ε was studied in [24] in which the following was shown: Lemma 3. [24] The family FGRR of GRR mechanisms is a refinement family. 2) UE and THE Mechanisms: These mechanisms are derived from 2x2 mechanisms operating on bits. The following construction will be helpful in proving some properties of these mechanisms. 1) Start with a 2x2 mechanism B which takes a bit in {0, 1} to a bit in {0, 1}. 2) Construct the k-wise Kronecker product B ⊗k which takes a k-bit vector to a k-bit vector. Note that the domain of B ⊗k is the set of all k-bit vectors. 3) Delete from B ⊗k all rows other than those that corre⊗k spond to one-hot vectors. Call this mechanism Bhot . ⊗k Notice that Bhot is a channel. The above construction has some nice properties with respect to refinement. Lemma 4. Let A, B be bitwise channels and let A ⊑ B. Then ⊗k A⊗k ⊑ B ⊗k and A⊗k hot ⊑ Bhot .
Proof. The proof follows similarly to the proof for THE mechanisms given in Lemma 5. Consider first the bitwise mechanism for SUE, given by: " ε/2 # Sε =
e eε/2 +1 1 eε/2 +1
1 eε/2 +1 ε/2 e eε/2 +1
Observe that eε/2 ≥ 1 and so, using the Neyman-Pearson lemma, we have that the most powerful test at significance 1 eε/2 has power eε/2 . That is, we have α = β = eε/21 +1 . eε/2 +1 +1 ′ Next, if ε ≤ ε then α ≥ α′ and β ≥ β ′ which gives a pointwise ordering on trade-off functions for Sε , Sε′ . This implies that Sε′ ⊑ Sε . The result follows from Lemma 4. Finally, for the OUE mechanisms: Lemma 8. The family FOUE of OUE mechanisms is a refinement family. Proof. As for the THE and SUE mechanisms, consider the bitwise OUE mechanism given by eε 1 eε +1
eε +1
1/2
1/2
ε
Notice that eεe+1 ≥ 1/2 and therefore from Neyman-Pearson we have α = eε1+1 and β = 1/2. Now, given ε ≤ ε′ we find that α ≥ α′ but β = β ′ = 1/2. This gives an ordering on tradeoff functions so that fOε ≥ fOε′ (from Lemma 2) and thus Oε′ ⊑ Oε . The result follows from Lemma 4. 3) SS and LH Mechanisms: We did not find an obvious refinement relation for these mechanisms, so we leave a more in-depth study of them to future work.
This tells us that it is sufficient to prove refinement on bitwise channels for the UE and THE mechanisms in order to have refinement on the overall channels. We first consider the set of THE mechanisms. Recall that the THE bitwise mechanism is defined " # −εθ 1 −εθ 1 − 12 e 2 e 2 2 Tε,θ = ε(θ−1) 1 ε(θ−1) 2 1 − 21 e 2 2e
B. Comparing Mechanisms
for θ ∈ (0.5, 1). We have the following:
e The SUE (symmetric UE) protocol chooses p = eε/2 +1 ε and q = 1 − p. So the SUE channel is 2 -DP. Interestingly, it is universally optimal among the 2ε -DP mechanisms on 2 secrets (as shown in [31]). This means that it leaks the most information compared with any other mechanism; in QIF terms, it is the unique minimal element in the anti-refinement chain for 2ε -DP mechanisms. However, this unique optimality does not transfer through to the SUE mechanism defined on one-hot vectors for two reasons: firstly, (as shown in [31]), there are no unique optimal
Lemma 5. Let θ ∈ (0.5, 1), and let ε, ε′ ≥ 0 with ε ≤ ε′ . Then Tε′ ,θ ⊑ Tε,θ . We give an example of such THE mechanisms in Figure 1. This now gives our main result for THE mechanisms. Lemma 6. The family FTHE of THE mechanisms is a refinement family. Proof. Immediate from Lemma 5 and Lemma 4.
In this section, we study the relationship between the different refinement families identified in the previous section. Firstly, notice that the UE and THE mechanisms have the same form: they perturb each bit of the secret independently, using a mechanism of the form: (1 − q) q B = (1 − p) p ε/2
DP mechanisms on > 2 secrets (where refinement is not a lattice); and secondly, because the other bitwise mechanisms we study here (OUE, THE) are not 2ε -DP on bits (and therefore the result of [31] does not apply). On the other hand, refinement between bitwise mechanisms does transfer through to refinement on one-hot vector domains (Lemma 4). Thus, we will continue by examining refinement relationships between the bitwise mechanisms, noting that this is sufficient but not necessary for refinement on the full mechanism. OUE and SUE mechanisms We first remark (continuing from above) that the bitwise OUE mechanism has a different DP guarantee than the bitwise SUE mechanism. This is why we cannot use a simple “universal optimality” argument to show that the SUE is always better (for utility) than the OUE. In fact, we have the following: Lemma 9. Let Sε , Oε be the bitwise mechanisms for the SUE and OUE protocols, respectively, both parametrized by some ε > 0. Then Sε ̸⊑ Oε and Oε ̸⊑ Sε . Proof (Sketch). We use the f -privacy trade-off functions to compare Oε and Sε , this time using Lemma 1 since the condition for Lemma 2 does not hold. The result follows. Note that this only means that neither bitwise mechanism is better than the other (in terms of utility). Importantly, this does not mean that one mechanism is never better than the other for any utility measure; failure of refinement here means we cannot prove that for all utility measures one mechanism is universally better than the other. 8 THE and OUE mechanisms 1.0 0.8
f O
0.8
f T
f T
To give some intuition for what this means, we remark that for θ = 0.5, refinement never holds, and for θ = 1, refinement always √ holds. In between these values (actually above θ = 1/ 2), θ is an increasing function of ε, and so refinement holds for small ε values but fails to hold when ε goes above a threshold. For example, setting ε = 0.8 in the above inequality produces θ ≥ 0.8. Conversely, this means that for θ = 0.8, refinement holds for ε ≤ 0.8 and breaks for ε > 0.8. An example is depicted in Figure 2. From Lemma 4 it follows that the corresponding one-hot mechanisms are also in refinement when θ satisfies the above. Corollary 1. Let Tε,θ , Oε be bitwise mechanisms for THE, OUE respectively and let θ satisfy the inequality in Lemma 10. ⊗k ⊗k Then the corresponding one-hot mechanisms Thot , Ohot satisfy ⊗k ⊗k Ohot ⊑ Thot . THE and SUE mechanisms Here we find that there is always a refinement, regardless of the value taken by θ for the THE mechanism. Lemma 11. Let Tε,θ , Sε be bitwise mechanisms for THE, SUE, respectively. Then Sε ⊑ Tε,θ for any θ ∈ (0.5, 1).
β
0.6
0.4
0.4
0.2
0.2
0.0 0.0
0.2
0.4
0.6 α
0.8
1.0
0.0 0.0
1.0 f O f S
0.8
0.2
0.4
0.6
0.8
1.0
α
Fig. 2: Refinement relation between OUE and THE mechanisms for θ = 0.95. The left figure shows refinement for ε = 3 and the right shows non-refinement for ε = 5. Recall that the THE mechanism is parametrized by both ε and θ ∈ (1/2, 1). We find that the value of θ plays a role in the refinement relation between THE and OUE, as given in the following. Lemma 10. Let Tε,θ , Oε be bitwise mechanisms for THE, OUE, respectively. Then Oε ⊑ Tε,θ exactly when √ 2 ln(eε + 1 + (eε/2 − 1)( eε + 1)) − ε − 2 ln 2 θ≥ ε 8 Also note that the comparison on bitwise mechanisms is only a sufficiency condition for refinement.
f (α)
β
0.6
Proof. (Sketch) We make use of Lemma 1 (3). The second inequality always holds, but the first inequality only holds for the value of θ shown above. Since it is √ undefined at ε = 0, we can take limits to get the value of 1/ 2.
Remarks On 2 secrets, refinement is a lattice [17], meaning that there is a minimal element that is a refinement of both OUE and SUE mechanisms, and a maximal element that is an anti-refinement of both OUE and SUE.
1.0 f O
√ for ε > 0 and θ ≥ 1/ 2 at ε = 0.
fmin(O,S)
0.6 0.4 0.2 0.0 0.0
0.2
0.4
0.6
0.8
1.0
α
Fig. 3: OUE and SUE mechanisms are not in refinement, but there is an element given by min(O, S) (green dotted line) which is the maximum element refined by both OUE and SUE. An example of the latter is given in Figure 3. The intuition behind the min of SUE and OUE is that it is the most private mechanism that is at least as useful as SUE and OUE (for all utility functions). The construction of the min in general has been shown [17], and we formulate it here as follows.
Lemma 12. Let Sε , Oε be bitwise SUE and OUE mechanisms, respectively, parametrized by ε ≥ 0. Then the mechanism Mε = Sε min Oε , defined " ε/2 # 1 e 1 1 ε/2 +1 ε/2 +1 − eε +1 eε +1 e e Mε = , 1 eε/2 1 − 12 2 eε/2 +1 eε/2 +1 is the maximum element in the refinement order that is an anti-refinement of both Sε and Oε . We leave the study of this mechanism to future work. Max-case refinement We may wonder if average-case refinement is too strong, and max-case refinement could be a better measure of security, especially given that ε describes a worst-case attack. In fact, the following result is immediate from Lemma 1. Corollary 2. On 2x2 channels, average-case refinement and max-case refinement coincide. 9 Proof. Lemma 1 (2) is exactly the condition for max-case refinement, and we have shown that on 2x2 channels it coincides with average-case refinement. From this, it is also immediate that max-case refinement is preserved for the full mechanisms (defined on one-hot vectors). Corollary 3. Let C, D be 2x2 channels with C ⊑MAX D. Then ⊗k MAX ⊗k C ⊗k ⊑MAX D⊗k and Chot ⊑ Dhot . Proof. From Cor. 2, C ⊑MAX D =⇒ C ⊑ D, and from Lemma ⊗k ⊗k 4 we have C ⊑ D =⇒ Chot ⊑ Dhot . Finally, we know that average-case is strictly stronger than max-case in general ⊗k ⊗k ⊗k MAX ⊗k ([24]) and so Chot ⊑ Dhot =⇒ Chot ⊑ Dhot . VII. E XPERIMENTAL R ESULTS In order to present an experimental evaluation of the theoretical results described in this work, we selected the Kosarak dataset [32], a click-stream dataset, i.e., sequences of actions (clicks) performed by users while browsing a website, from a Hungarian news portal. The dataset contains 41,270 distinct actions and approximately 8 million actions performed by 990,002 users. Due to computational constraints, we considered two subsets of the data. The first subset, used in Figure 4, consists of 10,000 actions drawn from the 10 most frequent actions. The second subset, used in Figure 5, consists of 10,000 actions selected uniformly at random. The code used in the experiments is available on GitHub 10 . A. Refinement of THE, OUE and SUE We start our analysis with a comparative study of information leakage among the THE, OUE, and SUE protocols. 9 Here we use the condition for traditional max-case refinement, noting that it subsumes max-case for the g-leakage version used in this paper. 10 https://github.com/ramongonze/ldp qif.
Fig. 4: Comparison of ASR of THE, OUE and SUE protocols. The threshold vertical line corresponds to the one defined in Lemma 10.
We notice in Figure 4 that when θ is above the threshold defined in Lemma 10, OUE leaks more than THE (a consequence of the refinement Oε ⊑ Tε,θ ). However, below the threshold, there is no refinement, and this fact can be observed in the graphs of ε = 8 and ε = 16, where THE is leaking more information than OUE. On the other hand, Lemma 11 says that, no matter the gain function, SUE always leaks more than THE, and this fact is confirmed in all four graphs of Figure 4. As a second example, we turn our attention to Figure 5. We observe that OUE is always more useful than SUE, and that SUE, in turn, is always more useful than THE, for the values of ε shown in the graphs. These experimental results corroborate the theoretical refinement relationships among THE, OUE, and SUE, as well as the results from [7]. Saying that a protocol A refines a protocol B means that B leaks at least as much information as A. In terms of utility, this corresponds to B being consistently more useful than A, but at the same time, less private. B. Comparing Bayes Capacity of all LDP protocols We begin the analysis of Bayes capacities by examining the OUE and SUE curves in Figure 6. As shown in Lemma 9, neither protocol refines the other, a fact reflected by the intersection of their curves at approximately ε = 7. In contrast, SUE refines THE for all values of ε, and therefore its Bayes capacity is always higher than that of THE. The binary version of Local Hashing (BLH) maps a domain [k] to a binary domain. Figure 6 shows that the Bayes capacity of BLH is very small for all computed values of ε, indicating that the protocol provides strong privacy. However, this comes
Fig. 7: Comparison between Gursoy’s [8] Eqn (25) and our Eqn (26). The graph presents the ASR for ε = 3 and ε = 5 over different values of k. The experimental evaluation was repeated over 1000 iterations, simulating a dataset containing 1000 users.
Fig. 5: Comparison of the Mean Squared Error (MSE) of an adversary estimating the frequency of values in the data (i.e., the histogram) under the THE, OUE, and SUE protocols. The vertical threshold line corresponds to the value defined in Lemma 10, and the shaded area around the empirical is the variance.
Figure 7 shows that for large values of k, the experimental evaluation closely matches both equations. For small k, however, Eqn (25) can deviate substantially from the experimental results. The larger the ε, the larger is the k for a good approximation of Eqn (25). In contrast, Eqn (26) matches the experimental evaluation for all values of ε.
VIII. C ONCLUSION at the cost of utility, since most of the information is lost when the domain is reduced to a binary one. In our experimental evaluation, we observed convergences of Bayes capacities for the LDP protocols analyzed in this work. In summary, the Bayes capacities of GRR, SS, and THE converge to k as ε increases; SUE converges to a value slightly higher than k; BLH converges to 2 (because of g = 2); and OLH and OUE converge to approximately k/2.
Fig. 6: Comparison of the Bayes capacity of all protocols for k = 50. For THE, θ = 3/4, for BLH g = 2, and all other protocol-specific parameters are set to their optimal values. C. Analysis of Local Hashing We present now a comparison between Eqn (25), provided in [8], and our new formulation in Eqn (26).
In this paper, we have presented a principled and robust framework for the analysis and comparison of Local Differential Privacy (LDP) protocols through the lens of Quantitative Information Flow (QIF). By modeling LDP mechanisms as information-theoretic channels, we move beyond the traditional reliance on the single parameter ε and utility-specific metrics, which often fail to capture the nuances of privacy protection against diverse adversarial models. Our main contributions include the formal bridging of the LDP and QIF literatures, demonstrating that common inference attacks, such as data reconstruction, directly coincide with standard QIF notions of Bayes vulnerability. Furthermore, by leveraging the theory of channel refinement and Blackwell ordering, we have established a partial order that allows for metric-independent comparisons of protocols. This refinementbased approach has allowed us to uncover significant discrepancies in current LDP classifications; specifically, we have identified instances where protocols previously characterized as “optimal” in terms of estimation error are, in fact, strictly dominated by, or incomparable to, alternative mechanisms when viewed through a rigorous privacy-leakage lens. Additionally, our channel-based treatment of seven stateof-the-art protocols enabled us to identify and correct analytical errors in existing literature [8] regarding the expected success rate of reconstruction attacks on Local Hashing (LH) mechanisms. The resulting QIF-based treatment provides the community with a more accurate understanding of the privacyutility trade-offs inherent in these widely deployed systems.
IX. P ERSPECTIVES FOR F UTURE R ESEARCH The intersection of QIF and LDP offers a fertile ground for several future research directions: Complex Data Collection Tasks: While this paper focuses on frequency estimation, there is a critical need to extend QIF analysis to more complex tasks such as heavy hitter discovery [14] and multidimensional data analysis [33], [34]. These tasks involve intricate secret spaces where the attacker’s objectives can be much more sophisticated. Compositional Analysis: A vital open question is the study of the compositional properties of refinement relations. Investigating whether the dominance of one protocol over another is preserved under sequential or adaptive composition is essential for real-world deployments where users contribute data across multiple rounds. Expansion to Metric-LDP: For applications involving location or numerical data, extending this framework to metricbased LDP [35] (e.g., Geo-indistinguishability [36]) would be highly beneficial. This requires a formal treatment of “closeness” between secrets within the QIF leakage metrics. Automated Formal Verification: To mitigate the risk of analytical errors in manual proofs, it would be valuable to develop automated verification tools, such as probabilistic model checking or symbolic execution, to provide formal certification of refinement relations. AUTHOR C ONTRIBUTIONS Natasha Fernandes and Ramon G. Gonze are the lead authors of this work and carried out the majority of the technical development. Nataliia Bielova and Héber H. Arcolezi initiated the project and developed the initial analyses, including the posterior-vulnerability formulation and the channel-matrix representations of LDP protocols. Natasha Fernandes formalized the analysis, establishing connections to f -DP, refinement relations, and Bayes capacity. Ramon G. Gonze developed the channel-matrix analysis for LH protocols, derived the corrected Bayes-capacity-based leakage analysis for LH protocols, and contributed to the implementation and experiments. Catuscia Palamidessi provided theoretical supervision and validated the formal results. All authors contributed to the writing and review of the paper. ACKNOWLEDGMENTS The work of Héber H. Arcolezi has been partially supported by the French National Research Agency (ANR), under contracts: “ANR-24-CE23-6239” and “ANR-23-IACL-0006”. The work of Catuscia Palamidessi has been partially supported by the project ELSA of the HORIZON EUROPE Framework Programme (project number 101070617). The collaboration between Natasha Fernandes and Catuscia Palamidessi has been supported by the project IDEAL of the Inria “Equipes Associées” program.
R EFERENCES [1] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith, “What can we learn privately?,” SIAM Journal on Computing, vol. 40, no. 3, pp. 793–826, 2011. [2] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in Theory of Cryptography, pp. 265– 284, Springer Berlin Heidelberg, 2006. [3] U. Erlingsson, V. Pihur, and A. Korolova, “RAPPOR: Randomized aggregatable privacy-preserving ordinal response,” in Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, (New York, NY, USA), pp. 1054–1067, ACM, 2014. [4] Apple Differential Privacy Team, “Learning with privacy at scale,” 2017. https://docs-assets.developer.apple.com/ml-research/papers/ learning-with-privacy-at-scale.pdf, (accessed January 2023). [5] Z. Sun, P. Kairouz, H. Sun, A. Gascon, and A. T. Suresh, “Private federated discovery of out-of-vocabulary words for gboard,” arXiv preprint arXiv:2404.11607, 2024. [6] B. Ding, J. Kulkarni, and S. Yekhanin, “Collecting telemetry data privately,” in Advances in Neural Information Processing Systems 30 (I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, eds.), pp. 3571–3580, Curran Associates, Inc., 2017. [7] T. Wang, J. Blocki, N. Li, and S. Jha, “Locally differentially private protocols for frequency estimation,” in 26th USENIX Security Symposium (USENIX Security 17), (Vancouver, BC), pp. 729–745, USENIX Association, Aug. 2017. [8] M. Emre Gursoy, L. Liu, K.-H. Chow, S. Truex, and W. Wei, “An adversarial approach to protocol analysis and selection in local differential privacy,” IEEE Transactions on Information Forensics and Security, vol. 17, pp. 1785–1799, 2022. [9] H. H. Arcolezi, S. Gambs, J.-F. Couchot, and C. Palamidessi, “On the risks of collecting multidimensional data under local differential privacy,” Proc. VLDB Endow., vol. 16, pp. 1126–1139, jan 2023. [10] M. S. Alvim, K. Chatzikokolakis, A. McIver, C. Morgan, C. Palamidessi, and G. Smith, The science of quantitative information flow. Springer, 2020. [11] P. Kairouz, K. Bonawitz, and D. Ramage, “Discrete distribution estimation under local privacy,” in International Conference on Machine Learning, pp. 2436–2444, PMLR, 2016. [12] M. Ye and A. Barg, “Optimal schemes for discrete distribution estimation under locally differential privacy,” IEEE Transactions on Information Theory, vol. 64, no. 8, pp. 5662–5676, 2018. [13] S. Wang, L. Huang, P. Wang, Y. Nie, H. Xu, W. Yang, X.-Y. Li, and C. Qiao, “Mutual information optimally local private discrete distribution estimation,” arXiv preprint arXiv:1607.08025, 2016. [14] R. Bassily and A. Smith, “Local, private, efficient protocols for succinct histograms,” in Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’15, (New York, NY, USA), pp. 127–135, Association for Computing Machinery, 2015. [15] R. Rogers, S. Subramaniam, S. Peng, D. Durfee, S. Lee, S. K. Kancha, S. Sahay, and P. Ahammad, “Linkedin’s audience engagements api: A privacy preserving data analytics system at scale,” Journal of Privacy and Confidentiality, vol. 11, no. 3, 2021. [16] J. Dong, A. Roth, and W. J. Su, “Gaussian differential privacy,” Journal of the Royal Statistical Society Series B: Statistical Methodology, vol. 84, pp. 3–37, 02 2022. [17] N. Fernandes, A. McIver, and P. Sadeghi, “Composition theorems for f-differential privacy,” arXiv preprint arXiv:2512.21358, 2025. [18] M. Pan, “Improving count-mean sketch as the leading locally differentially private frequency estimator for large dictionaries,” in 2025 IEEE 38th Computer Security Foundations Symposium (CSF), pp. 97–112, 2025. [19] H. H. Arcolezi and S. Gambs, “Revealing the true cost of locally differentially private protocols: An auditing perspective,” Proceedings on Privacy Enhancing Technologies, vol. 2024, no. 4, pp. 123–141, 2024. [20] B. K. Balioglu and E. Gursoy, “Budget inference attacks and countermeasures in locally differentially private data collection,” ACM Trans. Internet Technol., vol. 26, Jan. 2026. [21] M. S. Alvim, M. E. Andrés, K. Chatzikokolakis, P. Degano, and C. Palamidessi, “On the relation between differential privacy and quantitative information flow,” in Automata, Languages and Programming (ICALP 2011), vol. 6756 of Lecture Notes in Computer Science, pp. 60– 76, Springer, 2011.
A PPENDIX
[22] G. Barthe and B. Köpf, “Information-theoretic bounds for differential privacy,” in Proceedings of the 24th IEEE Computer Security Foundations Symposium (CSF), pp. 191–204, IEEE, 2011.
A. Leakage Analysis using Bayes Capacity
[23] M. S. Alvim, M. E. Andrés, K. Chatzikokolakis, P. Degano, and C. Palamidessi, “On the information leakage of differentially-private mechanisms,” Journal of Computer Security, vol. 23, no. 4, pp. 427–469, 2015.
After experimentally observing a difference of ASR given by Equations (25) and (26), we investigated the derivation of Eq. (25) in [8], and we found a mistake on it. The fraction
[24] K. Chatzikokolakis, N. Fernandes, and C. Palamidessi, “Comparing systems: Max-case refinement orders and application to differential privacy,” in 32nd IEEE Computer Security Foundations Symposium, CSF 2019, Hoboken, NJ, USA, June 25-28, 2019, pp. 442–457, IEEE, 2019. [25] 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, 2020. [26] M. Lopuhaä-Zwakenberg, B. Škorić, and N. Li, “Informationtheoretic metrics for local differential privacy protocols,” arXiv, vol. abs/1910.07826, 2019. [27] M. Jurado, R. G. Gonze, M. S. Alvim, and C. Palamidessi, “Analyzing the shuffle model through the lens of quantitative information flow,” in 2023 IEEE 36th Computer Security Foundations Symposium (CSF), pp. 423–438, IEEE, 2023.
h i E |UHℓ ,x′ℓ | − 1 h i E |UHℓ ,x′ℓ |
in Eq. (24) of the paper corresponds to: Given the true value and reported values are equal, and given the adversary will guess a random value from the subset UHℓ ,x′ℓ , this fraction is intended to be the adversary’s expected chance of guessing wrongly the true value. However, the correct way to write this expected chance is "
[28] M. S. Alvim, K. Chatzikokolakis, C. Palamidessi, and G. Smith, “Measuring information leakage using generalized gain functions,” in 2012 IEEE 25th Computer Security Foundations Symposium, pp. 265– 279, IEEE, 2012. [29] C. Braun, K. Chatzikokolakis, and C. Palamidessi, “Quantitative notions of leakage for one-try attacks,” in Proceedings of the 25th Conference on Mathematical Foundations of Programming Semantics, MFPS 2009, Oxford, UK, April 3-7, 2009 (S. Abramsky, M. W. Mislove, and C. Palamidessi, eds.), vol. 249 of Electronic Notes in Theoretical Computer Science, pp. 75–91, Elsevier, 2009.
E 1−
[32] “Kosarak dataset.” https://fimi.uantwerpen.be/data/. Mining Dataset Repository.
#
1 |UHℓ ,x′ℓ |
,
(29)
and we can see that Equations (28) and (29) are not equivalent. B. Additional Figures
1.0 f O
[30] N. Fernandes, A. McIver, and P. Sadeghi, “Explaining ϵ in local differential privacy through the lens of quantitative information flow,” in 2024 IEEE 37th Computer Security Foundations Symposium (CSF), pp. 419–432, 2024.
0.8
f O 0
0.6 β
[31] N. Fernandes, A. McIver, C. Palamidessi, and M. Ding, “Universal optimality and robust utility bounds for metric differential privacy,” in 35th IEEE Computer Security Foundations Symposium, CSF 2022, Haifa, Israel, August 7-10, 2022, pp. 348–363, IEEE, 2022.
(28)
0.4
Frequent Itemset
[33] H. H. Arcolezi, J.-F. Couchot, B. A. Bouna, and X. Xiao, “Improving the utility of locally differentially private protocols for longitudinal and multidimensional frequency estimates,” Digital Communications and Networks, vol. 10, no. 2, pp. 369–379, 2024. [34] J. S. Costa Filho and J. C. Machado, “Felip: A local differentially private approach to frequency estimation on multidimensional datasets,” in Proceedings of the 26th International Conference on Extending Database Technology, EDBT 2023, Ioannina, Greece, March 28 - March 31, 2023, pp. 671–683, OpenProceedings.org, 2023. [35] K. Chatzikokolakis, M. E. Andrés, N. E. Bordenabe, and C. Palamidessi, “Broadening the scope of differential privacy using metrics,” in Privacy Enhancing Technologies - 13th International Symposium, PETS 2013, Bloomington, IN, USA, July 10-12, 2013. Proceedings (E. D. Cristofaro and M. K. Wright, eds.), vol. 7981 of Lecture Notes in Computer Science, pp. 82–102, Springer, 2013. [36] M. E. Andrés, N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, “Geo-indistinguishability: differential privacy for location-based systems,” in 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS’13, Berlin, Germany, November 4-8, 2013 (A. Sadeghi, V. D. Gligor, and M. Yung, eds.), pp. 901–914, ACM, 2013. [37] M. S. Alvim, N. Fernandes, A. McIver, C. Morgan, and G. H. Nunes, “A novel analysis of utility in privacy pipelines, using kronecker products and quantitative information flow,” in Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS 2023, Copenhagen, Denmark, November 26-30, 2023 (W. Meng, C. D. Jensen, C. Cremers, and E. Kirda, eds.), pp. 1718–1731, ACM, 2023.
0.2 0.0 0.0
0.2
0.4
0.6
0.8
1.0
α Fig. 8: Example showing ordering between f -privacy trade-off functions for OUE mechanisms when α values are ordered, i.e. α > α′ but β = β ′ . C. Proofs omitted from the main body of the paper Lemma 1. Let C, D be 2x2 channels with trade-off points (αC , βC ) and (αD , βD ) respectively. Then the following statements are equivalent: 1) C ⊑ D 2) The posteriors of D under a uniform prior are inside the convex hull of the posteriors of C βD 1−βD βC C 3) 1−α ≤ 1−α and 1−β αC ≥ αD . C D Proof. It is already known that (1) implies (2) (see [10]). We will prove that (2) implies (1), (2) implies (3) and (3) implies (2).
(2) implies (1): For this, we need to prove a final requirement for refinement, that there exists an averaging that takes the posteriors of C onto the posteriors of D, averaged using the outer probabilities. We write u for the uniform prior. Note that we can write the posteriors of u ▷ C as: 1−αC
1−αC +βC δC1 = βC 1−αC +βC
αC
1+αC −βC δC2 = 1−βC 1+αC −βC
pC
qC
Similarly for D. Now, we are given that the posteriors are generated from a uniform prior, and therefore they must average to u. That is: pC ·δC1 + qC ·δC2 = u
pD ·δD1 + qD ·δD2 = u
(30) (31)
We are also given that the posteriors δD1 , δD2 lie inside the convex hull formed by δC1 , δC2 . Therefore there must exist non-negative values λ1 , λ2 , γ1 , γ2 such that: λ1 ·δC1 + λ2 ·δC2 = δD1 γ1 ·δC1 + γ2 ·δC2 = δD2
(32) (33)
λ1 + λ2 = 1
(34)
γ1 + γ 2 = 1
(35)
Multiplying eqns (32), (33) by pD , qD gives: (pD λ1 )·δC1 + (pD λ2 )·δC2 = pD δD1 (qD γ1 )·δC1 + (qD γ2 )·δC2 = qD δD2
As above, we write the posteriors of u ▷ C as: βC 1−αC +βC
(pD λ1 )·δC1 + (pD λ2 )·δC2 + (qD γ1 )·δC1 + (qD γ2 )·δC2 = pD ·δD1 + qD ·δD2 (from(30), (31))
= pC ·δC1 + qC ·δC2
Since δC1 , δC2 are linearly independent (as vectors), we must have that pD λ1 + qD γ1 = pC pD λ2 + qD γ2 = qC And from eqns (34), 35) we have that pD λ1 + qD λ2 = pD qD γ1 + qD γ2 = qD Therefore we have shown an averaging of vectors δC1 , δC2 onto vectors δD1 , δD2 , which is the additional requirement for refinement to hold. (2) implies (3):
1+αC −βC δC2 = 1−βC 1+αC −βC
pC
qC
and similarly for D. Since the posteriors of u ▷ D lie inside the convex hull of the posteriors of u ▷ C, and these posteriors lie on a straight line (the probability simplex on 2 secrets), then we must have: 1 − αD 1 − αC ≥ 1 − α C + βC 1 − α D + βD 1 − α C + βC 1 − α D + βD =⇒ ≤ 1 − αC 1 − αD βC βD =⇒ 1+ ≤1 + 1 − αC 1 − αD βC βD =⇒ ≤ 1 − αC 1 − αD
1−βD C By a similar argument it is easy to show that 1−β αC ≥ αD . (3) implies (2): This follows exactly the reverse argument of the above.
Lemma 2. Let C, D be 2x2 channels with trade-off points (αC , βC ) and (αD , βD ) respectively. Then αC ≤ αD and βC ≤ βD implies that C ⊑ D. Proof. Let αC ≤ αD and βC ≤ βD . Then βC βD ≤ 1 − α C 1 − αC βD ≤ 1 − αD
Similarly we have that: Summing gives:
αC
1−αC
1−αC +βC δC1 =
1 − βC 1 − βC ≥ αC αD 1 − βD ≥ αD
(Given βC ≤ βD ) (since
1 1 ≤ ) 1 − αC 1 − αD (Given αC ≤ αD )
(since 1 − βC ≥ 1 − βD )
The result follows from Lemma 1 (3). Lemma 4. Let A, B be bitwise channels and let A ⊑ B. Then ⊗k A⊗k ⊑ B ⊗k and A⊗k hot ⊑ Bhot .
Proof. That A ⊑ B implies A⊗k ⊑ B ⊗k was already shown in [37]. Now, A ⊑ B means Pthat there exists a witness W such that A·W = B. That is, y Ax,y Wy,z = Bx,z for every row x ′ and column Pz in B. But, if we remove row x from A, then we still have y Ax,y Wy,z = Bx,z for every row x in B except for row x′ which has been removed from A. Therefore, if we remove the corresponding row x′ from B then the equation P A y x,y Wy,z = Bx,z still holds for all x in A. In other words, we have refinement. And so we can conclude that A⊗k ⊑ B ⊗k ⊗k implies A⊗k hot ⊑ Bhot . Lemma 5. Let θ ∈ (0.5, 1), and let ε, ε′ ≥ 0 with ε ≤ ε′ . Then Tε′ ,θ ⊑ Tε,θ .
Proof. Given a 2x2 channel of the form 1−α α C= β 1−β with 1 − α > β, the Neyman-Pearson lemma gives that the most powerful test at significance level α has power 1 - β. Notice that this is true for Tε,θ by construction. That is, we ε(θ−1) −εθ have α = q = 12 e 2 and β = 1 − p = 12 e 2 . ′ Next, if ε ≤ ε then we can see that 1 −εθ 1 −ε′ θ e 2 ≥ e 2 2 2 and that 1 ε(θ−1) 1 −ε(1−θ) 1 −ε′ (1−θ) e 2 = e 2 ≥ e 2 . 2 2 2 And so by Lemma 2 we have that Tε′ ,θ ⊑ Tε,θ .
√ for ε > 0 and θ ≥ 1/ 2 at ε = 0. Proof. We make use of Lemma 1 (3). We first recall the bitwise mechanisms for Tε,θ and Oε : " Tε,θ =
−εθ
1 − 12 e 2 1 ε(θ−1) 2 2e
1 −εθ 2 2e 1 ε(θ−1) 1 − 2e 2
#
eε
eε +1
1 eε +1
1/2
1/2
Oε =
We note that these are in the right format to apply Defn 11 (by construction). We will label the tradeoff points (αT , βT ) and (αO , βO ) for Tε,θ and Oε respectively. Now, considering the second inequality, we have 1 eε + 1 1 − βO 2 = = ε αO 1/(e + 1) 2
(36)
1 − 12 e−ε(1−θ)/2 1 − βT = eεθ/2 (2 − e−ε(1−θ)/2 ) (37) = 1 −εθ/2 αT 2e
Lemma 9. Let Sε , Oε be the bitwise mechanisms for the SUE and OUE protocols, respectively, both parametrized by some ε > 0. Then Sε ̸⊑ Oε and Oε ̸⊑ Sε .
And so we deduce:
Proof. We use the f -privacy trade-off functions to compare Oϵ and Sϵ . This time we compare them using Lemma 1 since the condition for Lemma 2 does not hold. For Sϵ we have αS = βS = eϵ/21+1 and for Oϵ we have αO = eϵ1+1 , βO = 1/2. Therefore we have: βO 1 βS 1/2 − − = 1 − αO 1 − αS eϵ /(eϵ + 1) eϵ/2 eϵ + 1 1 = − ϵ/2 ϵ 2e e eϵ + 1 − 2eϵ/2 = 2eϵ ϵ/2 (e − 1)2 = 2eϵ ≥0
Now, let x = eεθ/2 . And so we continue, eε + 1 = e−ε/2 x2 − 2x + 2 eε + 1 −ε/2 2 ε/2 = e x − 2e x + eε/2 ( ) 2 eε + 1 = e−ε/2 (x − eε/2 )2 + eε/2 ( ) − eε 2 The quadratic term is always positive, so we consider the term on the RHS. Letting y = eε/2 we have that
βS βO ≥ 1−α . Next we have that: Thus 1−α O S
1 − βS 1 − βO 1/2 − = eϵ/2 − αS αO 1/(eϵ + 1 eϵ + 1 = eϵ/2 − 2 2eϵ/2 − eϵ − 1 = 2 −(eϵ/2 − 1)2 = 2 ≤0 1−βO S And so 1−β αS ≤ αO . Thus the condition in Lemma 1 (3) does not hold, and so refinement does not hold between Sϵ and Oϵ , except in the trivial case when equality holds, which means ϵ = 0, corresponding to the channel that leaks nothing.
Lemma 10. Let Tε,θ , Oε be bitwise mechanisms for THE, OUE, respectively. Then Oε ⊑ Tε,θ exactly when √ 2 ln(eε + 1 + (eε/2 − 1)( eε + 1)) − ε − 2 ln 2 θ≥ ε
eε + 1 − eεθ/2 (2 − e−ε(1−θ)/2 ) 2 eε + 1 = eεθ e−ε/2 − 2eεθ/2 + 2
(36) − (37) =
eε/2 (
y2 + 1 eε + 1 ) − eε = y( ) − y2 2 2 1 = (y 3 − 2y 2 + y) 2 1 = y(y − 1)2 2 ≥ 0 for y ≥ 0
And so we have shown that (36) − (37) ≥ 0, thus we have the second condition of Lemma 1 (3) that holds. We need now to check the first inequality. We begin: eε + 1 βO = 1 − αO 2eε
(38)
1 −ε(1−θ)/2 e βT = 2 1 −εθ/2 1 − αT 1 − 2e
e−ε(1−θ)/2 2 − e−εθ/2 eεθ e−ε/2 = 2eϵθ/2 − 1 x2 e−ε/2 = 2x − 1 =
(39)
where in the last line we set x = eεθ/2 . Then, βT βO x2 e−ε/2 eε + 1 − = − 1 − αT 1 − αO 2x − 1 2eε ε/2 2 2e x − x(2eε + 2) + (eε + 1) = 2eε (2x − 1)
This is ≥ 0 when the numerator is ≥ 0 (since the denominator is always positive). The numerator is quadratic in x, so solving gives p (2eε + 2) + (2eε + 2)2 − 8eε/2 (eε + 1) or x≥ ε/2 p4e (2eε + 2) − (2eε + 2)2 − 8eε/2 (eε + 1) x≤ 4eε/2 We simplify the expression inside the square root: (2eε + 2)2 − 8eε/2 (eε + 1)
= 4 + 4e2ε + 4eε − 8e3ε/2 − 8eε/2
= 4(1 + e2ε + eε − 2e3ε/2 − 2eε/2 = 4 (eε + 1)2 − 2eε/2 (eε + 1) = 4(eε + 1)(eε/2 − 1)2
And so, substituting x = eεθ/2 we have that √ eε + 1 + (eε/2 − 1) eε + 1 eεθ/2 ≥ 2eε/2 √ ε 2 ln (e + 1 + (eε/2 − 1) eε + 1) − ε − 2 ln 2 =⇒ θ ≥ ε and √ eε + 1 − (eε/2 − 1) eε + 1 εθ/2 e ≤ 2eε/2 √ 2 ln (eε + 1 − (eε/2 − 1) eε + 1) − ε − 2 ln 2 =⇒ θ ≤ ε Lemma 11. Let Tε,θ , Sε be bitwise mechanisms for THE, SUE, respectively. Then Sε ⊑ Tε,θ for any θ ∈ (0.5, 1). Proof. We make use of Lemma 1 (3). We have: βT βS 1/2e−ϵ(1−θ)/2 1 − = − ϵ/2 −ϵθ/2 1 − αT 1 − αS 1 − 1/2e e e−ϵ(1−θ)/2 1 = − ϵ/2 2 − e−ϵθ/2 e eϵ/2 (e−ϵ(1−θ)/2 ) − (2 − e−ϵθ/2 ) = eϵ/2 (2 − e−ϵθ/2 ) eϵθ/2 − 2 + e−ϵθ/2 = ϵ/2 e (2 − e−ϵθ/2 ) eϵθ − 2eϵθ/2 + 1 = ϵ(1−θ)/2 e (2 − e−ϵθ/2 ) ϵθ/2 (e − 1)2 = ϵ(1−θ)/2 e (2 − e−ϵθ/2 ) ≥0
And finally, 1 − βS 1 − βT 1 − 1/2e−ϵ(1−θ)/2 − = eϵ/2 − αS αT 1/2e−ϵθ/2 = eϵ/2 − eϵθ/2 (2 − e−ϵ(1−θ)/2 )
= eϵ/2 − 2eϵθ/2 + e−ϵ/2 eϵθ eϵθ − 2eϵθ/2 eϵ/2 + eϵ eϵ/2 ϵθ/2 (e − eϵ/2 )2 = eϵ/2 ≥0
=
And so by Lemma 1 we have that Sϵ ⊑ Tϵ,θ . Proposition 1. [ASR of Local Hashing] Let LHε be the channel defined in Eqn (24). Then ASR(LHε ) =
eε g k + (g − 1)k (1 − eε ) . (eε + g − 1)(kg k−1 )
(26)
Proof. We are going to derive the posterior vulnerability of the LH channel that corresponds exactly to the ASR. The channel LHε = EG can be decomposed in the cascade of channels E and G: 1) First encode x (channel E). 2) Apply GRR to the encoded value (channel G). Definition of E: The channel is defined as E : X → DY, where Y = {(yh , ye ) | yh ∈ H and ye ∈ [g]}. The channel receives a secret x ∈ X = [k] as input and outputs a pair y = (yh , ye ), where yh = {(1, wi ), . . . , (k, wk ) | wk ∈ [g]} is a hash function chosen uniformly at random from H and ye is the encoded value of x. The channel matrix is then defined as ( Ex,y = Pr[(yh , ye ) | x] =
1 gk
, if yh (x) = ye
0
, if yh (x) ̸= ye
(40)
Definition of G: The channel is defined as G : Y → DZ, where Z = Y. The channel receives a pair y = (yh , ye ) as input and outputs a pair z = (zh , zp ), where zh = yh is the hash function received as input and zp = GRR(ye ) is the output of GRR for the encoded value of x (aka perturbed version of ye ). The definition is as follows
Gεy,z =
eε eε +g−1 1 eε +g−1
0
, if yh = zh and ye = yz , if yh = zh and ye ̸= yz , if yh ̸= zh .
(41)
Definition of LHε : The channel is defined as a cascading LHε = EG, where X LHεx,z = Ex,y · Gεy,z y
( =
ε 1 · e g k eε +g−1 1 1 · g k eε +g−1
, if zh (x) = zp , if zh (x) ̸= zp .
In short, LHε is a channel that, given an input x ∈ X , maps it to a pair z = (zh , zp ) where zh is a hash function chosen randomly and zp = GRR(zh (x)). Posterior vulnerability: Let g be the Bayes gain function such that the set of actions W = X and g(w, x) = 1 if w = x or 0 otherwise. We have that Vg [π ▷ LHε ] =
X
max
X
w
z
x
πx · LHεx,z · g(w, x)
Given that g(w, x) ̸= 0 ⇐⇒ w = x, we can eliminate the inner sum: X 1 · LHεx,z Vg [π ▷ LHε ] = max x k z We can expand the sum on z by each element of the pair (zh , zp ): =
g 1 X X max LHεx,(zh ,zp ) x k z =1 p
zh ∈ H
Once there is a fixed zp , there are two possible values for max LHεx,(zh ,zp ) : gpk and gqk . The last one hapx pens when there is no x such that zh (x) = zp , so |{(1, e1 ), . . . , (k, ek )|ei ∈ [g]\ys }| = (g − 1)k . The first one happens when there is at least one x such that zh (x) = zp , thus |{(1, e1 ), . . . , (k, ek )|ei ∈ [g] and ∃j : ejP = zs }| = g k − (g−1)k . We can split the second summation zh among these two case as following:
g
1 X Vg [π ▷ LH ] = k z =1 ε
p
q p k (g − (g − 1)k ) + k (g − 1)k gk g g
p(g k − (g − 1)k ) + q(g − 1)k X = 1 kg k z =1 p
k
k
k
(pg − p(g − 1) + q(g − 1) )g kg k k k pg + (g − 1) (q − p) = kg k−1 ε k e g + (g − 1)k (1 − eε ) . = (eε + g − 1)(kg k−1 ) =