Dependency Triad: A Metric to Quantify the Dependencies Between Attributes for Local Differential Privacy

Dependency Triad: A Metric to Quantify the Dependencies Between Attributes for Local Differential Privacy Sandaru Jayawardana∗ , Sennur Ulukus† , Ming Ding‡ and Kanchana Thilakarathna∗ ∗ The University of Sydney, Australia † University of Maryland, USA

arXiv:2608.03737v1 [cs.CR] 4 Aug 2026

‡ Technology, CSIRO, Australia

Abstract—Collecting multidimensional user data is essential for extracting rich insights across various applications. Local Differential Privacy (LDP) has emerged as a de facto standard for mitigating privacy risks in such scenarios. A key challenge in privacy-preserving multidimensional data collection lies in interattribute dependencies, as they can inadvertently reveal correlated information and increase privacy vulnerabilities. Therefore, accurately measuring correlation-induced privacy leakage (CPL) is essential for privacy analysis and privacy-utility trade-off. However, existing CPL analysis solutions either require accurate prior knowledge or face scalability challenges for large numbers of attributes and high-cardinality attributes. These limit their practical applicability in real data. To address this research gap, we propose a novel metric, “Dependency Triad” (DT), which summarizes the pairwise dependency information relevant to CPL using three parameters and yields a constant-time conservative estimator of pairwise CPL. DT explicitly models uncertainty in prior distributional knowledge through its parameters, delivering robust leakage estimates. Moreover, its robustness to sparse distributions makes it particularly suitable for high-cardinality attributes, while the pairwise formulation serves as a tractable building block for assessing total leakage in multidimensional settings. Extensive experiments on both synthetic and real datasets demonstrate that DT consistently estimates CPL across diverse dependency regimes and prior uncertainties.

I. I NTRODUCTION In today’s information age, collecting multidimensional user records (i.e., records which contain multiple features/attributes) is crucial for applications such as personalized services [1], [2] and data crowd-sourcing [3], [4]. These records often include sensitive attributes—personally identifiable information (PII) [5], financial [6], and health [7]— creating substantial privacy risks. ε-local differential privacy (ε-LDP) [8] is the de facto standard to provide privacy when curators are untrusted, or users will not share raw data [9]. An LDP mechanism is a randomized algorithm that perturbs data to bound worst-case leakage by ε (≥ 0). Here, a smaller ε yields stronger privacy (more noise) but typically results in lower data utility (data accuracy); therefore, experts tune ε to trade off between data utility and privacy. LDP has been deployed at scale by industry leaders such as Google [1], Microsoft [10], and Apple [11]. Multidimensional data inherently contain interdependencies [12], [4], making privacy preservation challenging because correlation may reveal more

information [13], [14]. Studies have proposed various methods to apply LDP in multidimensional data—e.g., privacy budget splitting [15], random-sampling [16], joint perturbation [4], etc.—to overcome correlation-induced privacy leakage (CPL) impact. These approaches primarily assume that the prior knowledge of the attribute dependencies is unknown/unavailable. However, studies highlight that prior knowledge of such correlations is ubiquitous today; for example, through universal correlation information [17], publicly available datasets [18], and learning distributions from a subset of the population [19]. Therefore, when prior knowledge is available, leveraging it to analyze CPL enables more nuanced applications, including evaluating the privacy guarantee and calibrating the privacy budgets of the mechanisms [20], [14], [18]. Pioneer work [21] uses conventional correlation metrics— e.g., mutual information (MI) [22], Pearson correlation coefficient (PCC) [23]—to estimate CPL. However, recent studies [14], [20] claim that these conventional correlation metrics are unable to accurately characterize the CPL, even when ground-truth probability distributions between attributes are available. Recent studies propose algorithms to estimate CPL between attributes using probability distributions to address limitations of conventional correlation metrics. For instance, suppose we need to compute the CPL of an attribute Xk caused by a correlated attribute X̂. Let a and b be the alphabet sizes1 of Xk and X̂, respectively. Study [20] (ITS) and study [18] (CBP) quantify CPL only for special-case LDP mechanisms whose randomization can be parameterized by two perturbation-probability levels (e.g., k-RR [5], Unary encoding [24]), which limits applicability to more general mechanisms (e.g., staircase mechanism [25]). These algorithms have time complexities of O(ab) and O(2a ), respectively. A recent study [14] proposes two algorithms for estimating CPL. The first algorithm, HCC-1, estimates the actual CPL using the transition probabilities of the LDP mechanism and the joint probability distribution between attributes. The second algorithm, HCC-2, estimates the supremum value of the CPL for any LDP mechanism, using a privacy budget of ε and a joint probability distribution between attributes. These algorithms 1 We refer to the cardinality of attributes as alphabet size.

TABLE I: Comparison between different CPL computation metrics and algorithms. Algorithm/ Metric MI [22]/PCC [23] ITS [20] CBP [18] HCC-1 [14] HCC-2 [14] LTM [26]

Scalability ✓ ✗ ✗ ✗ ✗ ✗

Distribution Bias Incomparability ✗ ✗ ✗ ✗ ✗ ✗

Supporting Mechanisms N/A Two-level LDP GRR Simple LDP Any LDP Any LDP

have time complexities of O(a2 b2 ) and O(a2 b log b), respectively. Study [26] proposes a precompute-based approach (LTM) to solve a similar optimization as in [14], which uses piecewise functions to compute the solution in O(log ab). All these existing algorithms assume access to ground-truth distributional information about the data, which is typically unavailable, especially in local data perturbation settings like LDP. Known distribution (i.e., prior knowledge) might mismatch the actual distribution due to various reasons, such as outdated knowledge, demographic differences, and noisy data. Therefore, the estimated CPL may differ from the actual leakage, leading to potential privacy vulnerabilities. Furthermore, real-world applications, such as privacy budget calibration, typically require assessing CPL at various privacy budget levels to identify the optimal privacy budget (i.e., privacyutility trade-off) while keeping the entire distribution (e.g., in [14], [18], [20]) or piecewise functions (space complexity of O(ab) for two attributes). Therefore, these algorithms are not scalable well with larger alphabet sizes and datasets due to high time and space complexities. Therefore, their practical applicability is limited by the requirement of ground-truth distributional information and their high space and computational complexity. Table I summarizes the existing solutions for computing CPL. Problem Statement - In summary, although quantifying CPL is a promising solution to evaluate privacy guarantee and maximize privacy-utility trade-off in multidimensional data, existing metrics and algorithms have two key shortcomings that limit their practical usability on real-world data: • P1 - Limited to specific LDP mechanisms or scalability limitations. • P2 - Requires ground truth probability distributions between the attributes. Next, let us consider a motivational example.

Fig. 1: Motivational example. ε denotes the maximum privacy leakage allowed for each attribute collected. Motivation Example - Suppose we conduct a state-wise

household income survey in the United States under LDP. Data from an initial subset of states (e.g., five states) can be collected using correlation-agnostic baselines such as simple privacy–budget splitting (SPL) or random sampling [27]. As the survey progresses, we can estimate joint attribute dependencies from initially collected data and treat them as prior knowledge. This prior knowledge is then used to optimize attribute-wise privacy–budget allocation, thereby improving the privacy–utility trade-off (Figure 1). In this setting, distribution shifts primarily arise from demographic differences such as development level. Then, multiple sources (previously collected state data) provide the basis for learning distributions and their potential uncertainty. However, currently available CPL analysis algorithms cannot utilize this distributional uncertainty information for privacy leakage analysis, which could lead to privacy vulnerabilities due to incorrect privacy leakage estimates. Proposed Solution - We first generalize the optimization problems studied in [14], [26] to settings where the underlying data distribution is uncertain (Section III). In this regime, computing the optimal CPL is substantially more expensive— with worst-case exponential-time complexity—thereby motivating heuristic methods to estimate CPL. We then ask whether the probability distribution can be compressed into a lowdimensional summary that preserves the dependency structure relevant to CPL, enabling fast evaluation. Conceptually, this approach mirrors the use of conventional correlation metrics, but seeks to leverage their computational and storage advantages while mitigating their accuracy gaps. Our main finding is that the pairwise dependency information relevant to CPL assessment (including distribution uncertainty) can be captured by three parameters. Using these dependency statistics—(α, β, δ)–Dependency Triad (DT)—we construct a constant-time estimator (using computed parameters α, β and δ) that provides a tight upper bound on CPL for any privacy budget ε. Here, the nonnegative coefficients α and β quantify complementary aspects of dependence: intuitively, α governs leakage behavior in the low privacy regime (larger ε), while β governs the high privacy regime (smaller ε). The factor δ ∈ [0, 1) corrects for sparsity2 by capturing mass concentration in the distribution (We provide an empirical interpretation of the DT parameters in Section VI-D). Given DT, Algorithm 2 estimates CPL in constant time O(1). DT only occupies constant space O(1), in contrast to storing the full a×b joint distribution at O(ab) to keep dependency information. Therefore, constant time and space requirements address P1. Experts can calibrate (α, β, δ) from prior, potentially uncertain, distributional knowledge, enabling deployment in real-world LDP data collection and privacy analysis pipelines (addressing P2). Finally, we prove that the DT-based estimator is an upper bound on CPL, ensuring that reported leakage never understates the true privacy loss and thereby overcoming privacy vulnerabilities of existing methods. 2 Probability distributions become sparse when attribute alphabets increase [28], [29].

Our Contributions - Next, we summarize our key contributions in this paper as follows: • We show that the pairwise dependency information relevant to CPL assessment, including distributional uncertainty, can be summarised by three parameters. We propose this three-parameter representation, termed the Dependency Triad (DT), as a novel metric for modeling attribute dependencies in LDP privacy-leakage analysis. Rather than fully characterizing the underlying joint distribution, DT serves as a conservative surrogate for pairwise CPL, enabling tractable leakage assessment when the full distribution is unavailable or uncertain. We further use pairwise analysis as a practical building block to estimate total leakage in multidimensional data. To the best of our knowledge, DT is the first metric specifically designed to summarize dependencies for LDP privacy leakage analysis in this setting. • We theoretically prove that DT possesses several desirable properties—configurable tolerance to uncertainty in prior distributions, constant-time complexity, and compatibility with sparse probability distributions. • We validate the theoretical guarantees via extensive empirical evaluation on both synthetic and real datasets. Moreover, we demonstrate how to incorporate distributional uncertainties in privacy analysis and calibrate privacy budgets in real-world data collection scenarios, highlighting the potential practical applicability of DT. Paper Structure - The rest of the paper is organized as follows. First, we review related definitions and theorems in Section II. In Section III, we extend the current optimization problem to address distribution uncertainty and highlight the associated computational challenges. In Section IV, we explain the design steps of DT to quantify CPL. In Section V, we formally define DT and present algorithms to compute the DT, and CPL using DT. In Section VI, we evaluate the proposed DT using synthetic and real datasets. Finally, Section VII summarizes the related works and Section VIII concludes the paper. II. P RELIMINARIES First, we present the LDP definition in Section II-A. Section II-B defines the privacy leakages in correlated data and presents an existing algorithm to compute the CPL. Finally, we discuss and formulate potential distributional uncertainties in prior knowledge and their effects on CPL analysis in Section II-C. A. Local Differential Privacy ε-LDP definition appears in various forms in the literature. In this work, we adopt the definition proposed by Duchi et al. [8]. Definition II.1 (ε-Local Differential Privacy). Let the input alphabet be X and the output alphabet be Y. A mechanism Q is ε-locally differentially private if, Q(S|x) ≤ eε , (1) sup ′) ′ Q(S|x S⊆Y, x,x ∈X

where Q(S|x) = p(Y = yi , yi ∈ S | X = x) is the privatization mechanism. The function p(·) denotes the probability of an event. Here, x ∈ X , yi ∈ Y and ε ≥ 0. B. Privacy Leakages in Correlated Attributes Let X = {X1 , . . . , Xn } be n correlated attributes, and let Y = {Y1 , . . . , Yn } be perturbed versions of X which are obtained with M = {M1 , . . . , Mn } ε-LDP mechanisms respectively. Suppose X1 , . . . , Xn are alphabets of inputs and Y1 , . . . , Yn are alphabets of outputs respectively. Then, we can define “direct privacy leakage”, “correlation-induced privacy leakage”, and “total privacy leakage” terms [14]. 1) Direct Privacy Leakage (DPL): DPL is the extent to which an adversary can infer information about a user’s original data from its perturbed data (without correlated attributes’ perturbed data). Let any attribute Xk ∈ X be perturbed using an ε-LDP mechanism Mk ∈ M. Then, the DPL of attribute Xk is at most ε. 2) Correlation-Induced Privacy Leakage (CPL): CPL is defined as the privacy leakage of an attribute that is caused by correlated attributes. Let LZ→Xk denote the CPL experienced by any attribute Xk ∈ X due to a subset of other correlated attributes Z ⊆ X \ {Xk }. Let us take Yk ∈ Y as the perturbed output of Xk , and W ⊆ Y \ {Yk } is the perturbed output of Z, and W is the output alphabet of W . Then LZ→Xk can be calculated as LZ→Xk = ln

sup w∈W, x,x′ ∈Xk

p(w|x) . p(w|x′ )

(2)

Here, the function p(·) denotes the probability of an event. 3) Total Privacy Leakage (TPL): TPL refers to the privacy leakage of an attribute, including its DPL and CPL. Formally, let LXk denote the TPL of any attribute Xk ∈ X. Computing the exact TPL is challenging due to the curse of dimensionality. As an alternative, using the sequential composition theorem [30], we can compute an upper bound for LXk , LXk as X LXk = ε + Lx→Xk . (3) x∈X\{Xk }

Here, ε is the privacy budget of Mk mechanism. Therefore, we can compute the TPL in any system by using the CPLs between attribute pairs and the privacy budgets of the mechanisms. CPL caused by any attribute X̂ ∈ X about Xk is given by,  P u∈X̂ p(y|u)p(u|x) P . (4) LX̂→Xk = ln sup ′ v∈X̂ p(y|v)p(v|x ) y∈Ŷ, x,x′ ∈Xk Here, Ŷ is the alphabet of perturbed output of X̂. Next, let us analyze the CPL between two correlated attributes as we can estimate the TPL of any attribute using CPLs and privacy budgets as stated in (3). This is a tractable building block to compute total privacy leakage, which is commonly adopted by recent studies.

4) Calculating the CPL Between two Correlated Attributes: Study [14] shows that solving (4) is a maximization problem of a fraction of linear functions given by, ln

CT G . T ′ y∈Ŷ, x,x′ ∈Xk C G sup

(5)

Here, C = (p(y|x̂1 ), . . . , p(y|x̂b )), b = (p(x̂1 |x), . . . , G = (Gi )i=1 t p(x̂b |x)), G′ = (G′i )i=1 = (p(x̂1 |x′ ), . . . , p(x̂b |x′ )). The set X̂ = {x̂1 , . . . , x̂b } denotes the alphabet of the attribute X̂, with |X̂ | = b, and x, x′ ∈ Xk where Xk is the alphabet of Xk , with |Xk | = a. This maximization problem is equivalent to a simplified form, as shown in (6) by removing ln. Here, S ⊆ [b], [b] = {1, . . . , b}. The set S corresponds to the indices of G and G′ elements which have coefficient eε (i.e., privacy budget = ε), and the remaining (i.e., [b] \ S) have coefficient 1. P P ε i∈[b]\S Gi + e i∈S Gi ′ P maximize F (S, G, G , ε) = P ′ ′ ε S i∈[b]\S Gi + e i∈S Gi subject to

bias, temporal drift or stale knowledge. When the prior does not reflect the actual dependencies among attributes, CPL computed from the prior can be shifted—either underestimated or overestimated. Let PA (∈ Ra×b ) and PK (∈ Ra×b ) be the actual and known conditional distribution between Xk and X̂ (i.e., P (X̂|Xk )) respectively. Let CPL⋆ denote the estimated CPL of the PA and CPL′ denote the estimated CPL of PK . We say CPL is underestimated if CPL′ < CPL⋆ (calibration may grant more budget than is safe), and overestimated if CPL′ > CPL⋆ (calibration is conservative, possibly reducing utility). Since the sign of misspecification is generally unknown, mitigating the underestimation risk guarantees the privacy. We formulate the distributional mismatch as an uncertainty set around the known distribution PK (∈ Ra×b ). Let ∆(∈ Ra×b ) be the individual entry-wise difference between PA and PK (i.e., ∆ ≥ |PA − PK |). This provides fine-grained variations for PA from PK . For example, we can define relative uncertainty with respect to the known distribution ∆ = PK × 10%. Further details are available in Section V-D.

S ⊆ [b]. (6)

The optimal solution of (6) indicates the ‘maximum CPL’ caused due to the release of X̂ about Xk for given privacy budget ε when the ground-truth distribution is available. Therefore, we refer to this ‘maximum CPL’ as “CPL⋆ ” throughout the remainder of the paper, unless stated otherwise. Two existing algorithms—proposed in [26] and [14]—solve this class of optimization problems with time-complexities of O(a2 b2 ) and O(a2 b log b), respectively. Furthermore, [26] shows that the solution can be modeled as a piece-wise function, which can be solved with O(log ab), which requires a pre-computation to derive the piece-wise function. A simplified version of the algorithm proposed by [14] is available in Appendix A. Intuitively, this algorithm allocates the indexes i to S which i have a larger ratio value for G G′i . Moreover, according to this ⋆ algorithm, CPL value depends on only two realizations of Xk attribute for a given ε. Additionally, we can compute the maximum LX̂→Xk as ε varies as shown in Corollary II.2. Corollary II.2. Let Xk and X̂ be two correlated attributes. Suppose X̂ is perturbed by ε-LDP mechanism M̂ . Then, the CPL caused by X̂ about Xk saturates as ε increases, as shown in (7). Moreover, this is the maximum LX̂→Xk as ε varies (i.e., maxε LX̂→Xk ), lim LX̂→Xk = ln

ε→∞

p(x̂|x) . ′ x̂∈X̂ , x,x′ ∈Xk p(x̂|x ) max

(7)

Here, X̂ and Xk are alphabets of X̂ and Xk , respectively. The proof of Corollary II.2 is available in [14]. C. Inaccuracies in Distributional Information In LDP deployments, a prior (learned or public) rarely matches the ground-truth distribution of the target population. Mismatch can arise from demographic differences, sampling

III. M OTIVATION In this section, we extend the CPL analysis optimization problem (6) with distribution uncertainty. Next, we show that solving this problem is worst-case exponential time. This motivates the development of a heuristic metric to quantify the dependency between attributes. A. Updated Optimization Problem We can update the CPL analysis optimization problem (6) as ε i∈[b]\S Gi + e i∈S Gi P ′ ′ ε i∈[b]\S Gi + e i∈S Gi

P ′

maximize ′

F (S, G, G , ε) = P

subject to

S ⊆ [b],

S,G,G

P

hi − ∆x̂i ,x ≤ Gi ≤ hi + ∆x̂i ,x ; ∀i ∈ [b], h′i − ∆x̂i ,x′ ≤ G′i ≤ h′i + ∆x̂i ,x′ ; ∀i ∈ [b], X X Gi = 1, G′i = 1. i∈[b]

i∈[b]

(8) b

b

Here, G = (Gi )i=1 , G′ = (G′i )i=1 , hi = PK (X̂ = x̂i |Xk = x), h′i = PK (X̂ = x̂i |Xk = x′ ), ∆x̂i ,x denotes the uncertainty of PK (X̂ = x̂i |Xk = x), and PK denotes the known distribution, respectively. B. Time Complexity Analysis This optimization problem is inherently non-convex, as the objective function involves a bilinear fractional form. Consequently, computing the optimal CPL becomes substantially more expensive than in the fixed (G, G′ ) setting (i.e., without distributional uncertainty), where the problem reduces to a linear fractional program (LFP). A potential approach is to decompose the original problem into quasi-convex sub-problems by fixing the subset S and solving each sub-problem independently. The global optimum

can then be obtained by taking the maximum across all S. For a fixed S, P maximizing F (·) requires increasing the numerator term Gi while simultaneously minimizing i∈SP the denominator term i∈[b]\S G′i . However, the number of possible subsets S grows exponentially with b, leading to a worst-case complexity of O(2b ). Similarly, if G and G′ are fixed, an optimal solution can be computed efficiently using standard methods for linear fractional programs (LFPs), yet exploring all possible combinations of their bounds still incurs O(2b ) complexity. Since no straightforward convex relaxation exists, the standard approach to handle bilinear fractional programs (BFPs) is to linearise the bilinear terms—typically via McCormick relaxations or related techniques—yielding a mixed-integer linear program (MILP). While this transformation enables the use of off-the-shelf MILP solvers, it remains computationally expensive, exhibiting exponential complexity in the worst case [31]. C. Our Approach Heuristic approaches are usually adopted to solve these types of problems. In this study, we focus on extracting CPLrelated information from distribution and utilize it to compute the CPL in time efficiently, similar to conventional correlation metrics, while mitigating the privacy risks associated with them. IV. M ETHODOLOGY This section explains the design steps and theoretical proofs of “Dependency Triad”: Section IV-A analyzes and defines the requirements that the metric must fulfil. Next, Section IV-B derives a compact representation for the probability distribution. Section IV-C adjusts the metric to handle inaccuracies in distributions. A. Analyzing and Defining the Requirements of the Metric First, we analyze the requirements that need to be satisfied by the metric to address P1 and P2 (See Section I). Then, we define four objectives that must be achieved by the metric based on this analysis. For P1-Limited to specific LDP mechanisms or scalability limitations: A key challenge is to compress the CPLrelated information in the distribution into a smaller set of parameters while incurring minimal information loss. Furthermore, these parameters should represent the dependencies between attributes, allowing an algorithm to estimate CPL in a more time-efficient manner. Ensuring a privacy leakage guarantee is another essential requirement, as the conventional correlation metrics (e.g., MI) lack such guarantees [14]. Therefore, we define three decomposed objectives that should be achieved by the metric to address P1: • OB1 - The metric should provide a compressed representation of probability distribution using ‘a fixed’ and ‘a smaller’ set of parameters, • OB2 - The estimated CPL of the metric should be ‘a tight upper bound’ for the CPL⋆ to maximize the accuracy and avoid any privacy risk,

1

1

1 2

+1

(a)

1

1 2

+1

(b)

1 2

+1

(c)

Fig. 2: (a) An example for sorted (ascending order) ratio vector Q for a given G, G′ . Here, G = (G1 , . . . , Gb ) and G′ = (G′1 , . . . , G′b ). (b) Approximated (G/G′ ) values into eα and e−γ , where α = ln maxi∈[b] Gi /G′i and γ =   − ln mini∈[b] Gi /G′i . (c) Approximated (Gi /G′i ) values into eα and e−β , where β is the calibrated parameter using Theorem IV.4.

• OB3 - CPL computation should be time efficient with the parameters. For P2-Requires ground truth probability distributions between the attributes: The metric should be capable of tolerating the inaccuracies in the prior known distributions. Therefore, as the fourth objective, • OB4 - The metric should be capable of tolerating the inaccuracies in the prior known distribution. Next, the following sections outline the steps taken to develop the novel metric, achieving each objective (i.e., OB1, OB2, OB3, and OB4). B. Approximating the Distribution In the metric development, we consider the same twoattribute scenario. Let Xk and X̂ be two correlated attributes, and suppose we aim to estimate CPL of Xk caused by the release Ŷ of X̂ (i.e., LX̂→Xk ). Here, Ŷ is the LDP version of X̂, which is obtained with ε-LDP mechanism M̂. Let G = (p(x̂1 |x), . . . , p(x̂b |x)), G′ = (p(x̂1 |x′ ), . . . , p(x̂b |x′ )), and let X̂ = {x̂1 , . . . , x̂b } denotes the alphabet of X̂, with |X̂ | = b, and x, x′ ∈ Xk , where Xk is the alphabet of Xk , with |Xk | = a. Then, LX̂→Xk is given by (6). As the first step (OB1), we need to determine the most effective way of approximating the probability distribution using a smaller number of parameters while ensuring the privacy guarantee (OB2). Here, we consider two factors: (i) ”How do the existing algorithms compute the CPL?” According to Algorithm 3, we can converge to the optimal solution of the optimization problem (6) by using the elementwise division between G and G′ [26], [14]. Moreover, the CPL for a given privacy budget depends only on two realizations of the Xk attribute. (ii) ”How does CPL behave at the boundary cases?”. Corollary II.2 shows that CPL converges to p(x̂|x) ln maxx̂∈X̂ , x,x′ ∈Xk p(x̂|x ′ ) as privacy budget (i.e., ε) goes to p(x̂|x) infinity. Therefore, maxx̂∈X̂ , x,x′ ∈Xk p(x̂|x ′ ) is an essential

information that should be preserved within the metric to characterize CPL at higher privacy budgets.   Gb 1 These two factors imply that we can use Q = G , . . . , ′ ′ G Gb
b 1
b ratios3 instead of individual Gi i=1 and G′i i=1 values to estimate CPL with no privacy risks (i.e., upper bound for CPL⋆ ). However, there could be many G, G′ vectors that share the same Q. Here, G and G′ are probability distribution vectors of size b. For example, suppose b = 3 and Q is {0.5, 3, 2} for vector give these given G, G′ . There are many  other
pairs
3 3 1 3 1 1 ′ same ratio values e.g., G = , , , G = , 8
8 4 4, 8, 8 
21 1 1 38 7 ′ G = 19 , , , , , G = etc. 50 50 5 50 50 10 Therefore, let the set H denote the set of all pairs of G, G′ sharing the ratio Q. Then, we need to find the maximum CPL value of all G, G′ ∈ H to ensure OB2. Theorem IV.1 states that the maximum CPL of all G, G′ ∈ H α α+ε γ (e −1) is ln eeε (e−1+e γ −1)+eγ (eα −1) which is similar as CPL given by the boundary values of Q (i.e., Q̃ ∈ {eα , e−γ }b , where α = ln maxq∈Q (q), and γ = − ln minq∈Q (q)). Since the maximum CPL value of G, G′ ∈ H does not depend on b and r, we only need α and γ to compute it. In other words, we can approximate the original Q in Figure 2a as its boundary values as shown in Figure 2b. Therefore, this approximation reduces the parameter count from ab to two (α and γ) that are required to characterize the dependency between two attributes. Next, we discuss α and γ characterization of probability distributions. Theorem IV.1. Let Xk and X̂ be discrete, correlated attributes with alphabets Xk and X̂ = {x̂1 , . . . , x̂b }, respectively. For x, x′ ∈ Xk define the conditional probability vectors G = (Gi )bi=1 , G′ = (G′i )bi=1 , with Gi = p(x̂i |x), G′i = p(x̂i |x′ ). Let  Q denotes the  element- wise ratio vector Q = Gb 1 G ⊘ G′ := G , . . . , . Let α = ln maxq∈Q (q), γ = G′ G′ 1

b

− ln minq∈Q (q), and let Q̃ be any vector in {eα , e−γ }b . Let J be the set that contains all the probability distributions of  size b. Define H := (G, G′ ) : G, G′ ∈ J, G ⊘ G′ = Q , the set of all pairs  of probability vectors sharing the ratio Q, and define H̃ := (G, G′ ) : G, G′ ∈ J, G ⊘ G′ = Q̃ , the set of all pairs of positive probability vectors sharing the ratio Q̃. Then the correlation-induced privacy leakage (CPL) satisfies max(G,G′ )∈H CPL(G, G′ ) = max(G,G′ )∈H̃ CPL(G, G′ ) = α

α+ε

γ

(e −1) ′ ln eeε (e−1+e γ −1)+eγ (eα −1) . Here, CPL(G, G ) denotes the CPL of ′ G and G .

Proof sketch. We first relax the feasible likelihood ratios to the interval [e−γ , eα ] and solve the resulting linear-fractional optimization problem. Monotonicity shows that the optimum occurs at the extreme ratios eα and e−γ , yielding the stated closed-form bound independently of the choice of S. Finally, we show that this bound is tight for the original problem by reducing it to an equivalent two-point instance supported on 3 We assume that ratios are well-defined, i.e., G′ ̸= 0 ∀i ∈ [b]. We extend i the analysis to the cases where G′i = 0 for some i in Section IV-B2.

the maximum and minimum ratios. The complete proof is provided in Appendix C. 1) Characterization Using (α, γ): (α, γ) is a simplified representation of a conditional probability distribution between two attributes, which can be used to compute an upper bound for CPL⋆ by, ln

eα − 1 + eα+ε (eγ − 1) eε (eγ − 1) + eγ (eα − 1)

based on Theorem IV.1. Here, α should be larger than γ when selecting the parameters according to Corollary IV.2. Next, we explore the methods to handle sparse distribution in Section IV-B2. Corollary IV.2. Let α1 , γ1 and α2 , γ2 be two (α, γ) characterization values for G, G′ γ1 = such that α1 = ln maxq∈G⊘G′ (q), − ln minq∈G⊘G′ (q), and α2 = ln maxq∈G′ ⊘G (q), γ2 = − ln minq∈G′ ⊘G (q). Therefore, α2 = γ1 and γ2 = α1 . Suppose U1 corresponds to the CPL of α1 , γ1 and U2 corresponds to the CPL of α2 , γ2 . Then, α1 ≥ γ1 ⇐⇒ U1 ≥ U2 . The proof of Corollary IV.2 is available in Appendix D. 2) Handling Sparse Distribution: Sparse probability distributions are common as the alphabet size increases [28], [29]. Such distributions can lead to an undefined α and γ parameter when the denominator becomes zero. To handle such scenarios, we introduce two new vectors (δ̃1 , . . . , δ̃t ) and (δ̂1 , . . . , δ̂t ) as Gi ≤ eα G′i + δ̃i ; ∀Gi ∈ G, G′i ∈ G′ , α > 0, G′i ≤ eγ Gi + δ̂i ; ∀Gi ∈ G, G′i ∈ G′ , γ > 0.

(9)

Here, ( Gi δ̃i = 0

; if G′i = 0, , and δ̂i = ; otherwise,

(

G′i 0

; if Gi = 0, ; otherwise. (10)

Then, we can compute α and γ as α = ln

Gi , ′ ∀i∈[b],G′i ̸=0 Gi max

γ = ln

G′i . ∀i∈[b],Gi ̸=0 Gi max

(11)

For n the simplicity, we o take the maximum value δ = P P max i∈[b] δ̃i , i∈[b] δ̂i , instead of two values. Then we can estimate the CPL using (α, γ, δ) as stated in Theorem IV.3. Theorem IV.3. Let Xk and X̂ be discrete, correlated attributes. Let α, γ be characterization parameters for LX̂→Xk . Let (δ̃1 , . . . , δ̃b ) and (δ̂1 , . . . , δ̂b ) nbe parameters introduced to o P P handle sparsity with δ = max i∈[b] δ̃i , i∈[b] δ̂i . Then the CPL characterized by (α, γ, δ) can be computes as (
ln 1 + δ(eε − 1) ; if eα − 1 − δ(eε  − 1) < 0, CPL = eα +δ−eα δ−δeε +eα+ε (−1+eγ +δ)−1 ln δ(eε −1)−eε +eγ (−1+eα +δ+eε −δeε ) ; otherwise. (12)

(a)

(b)

Fig. 3: Results of the toy example. (a) LX̂→Xk vs ε for Scenario 1. (b) LX̂→Xk vs ε for Scenario 2.

Proof sketch. S, we aggregate the variables P For a fixed subset P ′ ′ as g = G and g = i i∈S i∈S Gi , reducing the original multidimensional problem to a one-dimensional linearfractional optimization. The constraints provide two affine upper bounds on g in terms of g ′ , and monotonicity shows that the optimum occurs at a boundary, their intersection, or the saturation point g = 1, resulting in a piecewise solution. We then construct feasible G and G′ attaining this solution and optimize over S by collecting all δ̃i terms inside S and all δ̂i terms outside S. Finally, bounding both aggregate slack terms by δ = max{δ̃, δ̂} eliminates the infeasible cases and gives the stated CPL bound. The complete proof is provided in Appendix E. 3) Limitations of (α, γ, δ) characterization: The main challenge with (α, γ, δ) characterization is the reduction of estimation accuracy of CPL⋆ . To illustrate this, let us consider the following toy example. Toy Example - Let Xk and X̂ be two correlated attributes, and let Xk = {x, x′ } and X̂ = {x̂1 , x̂2 , x̂3 , x̂4 } be their alphabets respectively. Then, suppose we need to compute CPL of Xk caused by the release of perturbed X̂ (i.e., LX̂→Xk ) for two scenarios: Scenario 1 - G = (0.1, 0.1, 0.15, 0.2, 0.45), G′ = (0.4, 0.3, 0.1, 0.1, 0.1), where G and G′ are the probability distri′ bution P (X̂|X  k = x) and P (X̂|Xk = x ), respectively. Then Q=

Gi G′ i

4) Calibrated Characterization Using (α, β, δ): First, let us revisit the approximation approach of the (α, γ, δ) method. “α” is crucial to represent the privacy leakage at higher ε according to the Corollary II.2. Therefore, modifying α affects the privacy guarantee at higher privacy budgets. ”γ” also contributes to representing the strength of the correlation between two attributes. However, it is not a crucial parameter, as α. According to Corollary IV.7, privacy leakage monotonically increases with γ. As discussed in Section IV-B3, the main issue with (α, γ, δ) characterization is the over-estimate of the correlation. Adjusting the lower −γ bound (i.e.,  e  ) such that it represents the average impact of b

ratios could possibly improve the accuracy. the Q = GG′i i i=1 ”δ” corresponds to the edge cases that do not directly cause the significant estimation error. In our analysis, we notice that calibrating the minimum level of Q, e−γ with respect to the CPL⋆ (taking the calibrated minimum level as e−β ) at an ε = ε0 , improves the accuracy of CPL estimation while holding the privacy guarantee for ε ≥ ε0 as stated in Theorem IV.4. Intuitively, we compute intermediate level e−β in between e−γ and 1 such that (α, β, δ) estimate CPL more accurately as shown in Figure 2c. Here, we can estimate the CPL of (α, β, δ) using Corollary IV.6 similar to (α, γ, δ). Using Corollary IV.5, we can compute β at ε → 0, and it is always less than or equal to γ. This is an important result, as the estimated CPL guarantees privacy for ε ∈ (0, ∞). Since β is always less than or equal to γ, it is ensured that (α, β, δ) provides better estimation (Note that estimated CPL is monotonically increasing with γ as stated in Corollary IV.7). Next, let us estimate CPL using the (α, β, δ) method for the running toy example (Section IV-B3). Toy Example (Continue) - Let us compute β for both Scenario 1 and 2 at ε0 = 0 using Corollary IV.5. As shown in Figure 3a and Figure 3b, the estimated CPL of (α, β, δ) method (using Corollary IV.6) is a tighter upper bound and adapts to the changes of Q. Therefore, the calibration step mitigates the uncontrolled overestimation issue of the (α, γ, δ) estimation method.

4

= (0.25, 0.33, 1.5, 2.0, 4.5).

i=1

Scenario 2 - G = (0.0025, 0.2975, 0.48, 0.13, 0.09), G′ = (0.01, 0.39, 0.47, 0.11, 0.02) where G and G′ are the probability distribution P (X̂|Xk = x) and P (X̂|Xk = x′ ) of Scenario 2, respectively. Then Q

=

Gi G′i

4

=

i=1

(0.25, 0.58, 1.02, 2.09, 4.5). Note that both scenarios have the same α = 1.50, γ = 1.38, δ = 0. However, CPL⋆ is significantly different in two scenarios as shown in Figure 3a and Figure 3a. The main reason for this is the information   loss due to representing b

the distribution with ratios GG′i as it only conveys the i i=0 information of extremes. Thus, we propose a calibration step to address this issue in the next section.

Theorem IV.4. Let the metric be calibrated at privacy budget ε0 and let l be the CPL⋆ at ε0 . Then, the calibrated lower level −1+eα +δ+el δ−eα δ−eε0 ((el −eα )(−1+δ)+δ ) . β is given by, β = ln −eε0 (eα +el (−1+δ))+el (−1+eα +δ) The estimated CPL of (α, β, δ) method is an upper bound for the CPL⋆ for ε ≥ ε0 . Proof sketch. We first calibrate β by equating the analytical CPL expression to the exact leakage CPL⋆ at the calibration budget ε0 and solving for β. We then express the calibrated CPL through a scalar parameter g ′ and show that, within each segment where the selected aggregates A and B remain fixed, g ′ decreases as the calibration budget increases. Since the CPL expression is monotonically increasing in g ′ under the considered condition, calibration at ε0 upper-bounds calibration at any larger budget within the same segment. Extending this ordering across adjacent segment boundaries proves that the

calibrated estimate upper-bounds CPL⋆ for every ε > ε0 . The complete proof is provided in Appendix F. Corollary IV.5. Let e−β be the calibrated lower bound calibrated at ε = ε0 . Then,

that CPL characterized by (α̂, β̂, δ̂) provides an upper bound for the optimal CPL of PA (i.e., CPL⋆ ) as   min{1, p(x̂|x) + ∆x̂,x } , α̂ = max p(x̂|x′ ) − ∆x̂,x′ x̂∈X̂ , x,x′ ∈Xk , p(x̂|x′ )−∆x̂,x′ >0 β̂ = ln

1 + Ã − B̃ + eα (−1 + δ) − 2δ lim β = ln ≤ γ. ε0 →0 1 + (−1 + Ã − B̃)eα − δ

(13)

1 + ϕ̂ + eα̂ (−1 + δ̂) − 2δ̂

1 + (−1 + ϕ̂)eα̂ − δ̂ X δ̂ = max ′ x,x ∈Xk

Here, P

Ã

=

Gi ∈G, G′ i ∈G′ ,

P Gi ∈G, G′ i ∈G′ , Gi >1 G′ i

G′ i .

Gi >1 G′ i

Gi

and

B̃

=

The proof of Corollary IV.5 is available in Appendix G. Corollary IV.6. Let Xk and X̂ be discrete, correlated attributes. Let (α, β, δ) be characterization parameters for LX̂→Xk . Then the CPL characterized by (α, β, δ) can be computes as ( CPL =

ln 1 + δ(eε − 1) ; if eα − 1 − δ(eε  − 1) < 0, ln

eα +δ−eα δ−δeε +eα+ε (−1+eβ +δ)−1 δ(eε −1)−eε +eβ (−1+eα +δ+eε −δeε )

; otherwise. (14)

The proof of Corollary IV.6 is available in Appendix H. Corollary IV.7. Correlation-induced privacy leakage monotonically increases with γ. The proof of Corollary IV.7 is available in Appendix I. Next, we explore the methods to handle inaccuracies in the prior distribution in Section IV-C. C. Tuning (α, β, δ) for Inaccuracies in Prior Distribution So far, we have focused on approximating the probability distribution between two correlated attributes using a reduced number of parameters (i.e., α, β, δ). In this section, we incorporate distributional uncertainty into the metric (OB4). Estimated CPL of DT is implicitly robust to the distributional uncertainties to some extent, as it provides a tight upper bound for CPL⋆ . However, it is not controllable precisely. Therefore, next, we improve the (α, β, δ) method to incorporate distributional uncertainties. Let PA (∈ Ra×b ) and PK (∈ Ra×b ) be the actual and known conditional distribution between Xk and X̂ (i.e., P (X̂|Xk )) respectively. Let ∆(∈ Ra×b ) denote the entry-wise uncertainty matrix between PA and PK (i.e., ∆ ≥ |PA − PK |, where the inequality is interpreted entry-wise). Then, we can compute the updated (α̂, β̂, δ̂) such that the estimated CPL of (α̂, β̂, δ̂) provides an upper bound for CPL⋆ as stated in Theorem IV.8. Here, CPL⋆ denotes the optimal CPL of PA . Theorem IV.8. Let ∆ denote the entry-wise uncertainty matrix satisfying ∆ ≥ |PA − PK |, where the inequality is interpreted entry-wise. Then, we can compute the updated α̂, β̂, δ̂ such

, p(x̂|x) + ∆x̂,x .

x̂∈X̂ , p(x̂|x′ )−∆x̂,x′ ≤0

P P ′ Here, ϕ = maxS,G,G′ i∈S Gi − i∈S Gi , subject to S ⊆ [b], p(x̂i |x) − ∆x̂i ,x ≤ Gi ≤ p(x̂i |x) + ∆x̂i ,x , p(x̂i |x′ ) − ∆x̂i ,x′ ≤ G′i ≤ p(x̂i |x′ ) + ∆x̂i ,x′ , ∆x̂i ,x , ∆x̂i ,x′ ∈ ∆, x, x′ ∈ Xk , X̂ = {x̂1 , . . . , x̂b }, i ∈ [b]. The proof of Theorem IV.8 is available in Appendix J. V. D EPENDENCY T RIAD In the previous section, we described the design principles of a novel metric for quantifying dependencies between attributes. In this section, we formally define Dependency Triad and present the associated algorithms. A. Definition of Dependency Triad The proposed metric quantifies the dependencies between attributes and indicates the privacy leakage arising from their interdependencies. To reflect this, we name it as “Dependency Triad” (DT). Next, we formally defined DT in Definition V.1. Definition V.1 (Dependency Triad (DT )). Let Xk and X̂ be two dependent random variables with alphabets Xk and X̂ , respectively. Then, (α, β, δ)-Dependency Triad from X̂ to Xk ((α, β, δ) − DTX̂→Xk ) is defined as   min{1, p(x̂|x) + ∆x̂,x } , α= max p(x̂|x′ ) − ∆x̂,x′ x̂∈X̂ , x,x′ ∈Xk , p(x̂|x′ )−∆x̂,x′ >0 (15) 1 + ϕ + eα (−1 + δ) − 2δ , β = ln 1 + (−1 + ϕ)eα − δ X δ = max p(x̂|x) + ∆x̂,x . ′ x,x ∈Xk

(16) (17)

x̂∈X̂ , p(x̂|x′ )−∆x̂,x′ ≤0

Here, ∆ denotes the distribution
uncertainty, and ϕ = P P ′ maxS,G,G′ G − G i∈S i i∈S i , subject to S ⊆ [b], p(x̂i |x) − ∆x̂i ,x ≤ Gi ≤ p(x̂i |x) + ∆x̂i ,x , p(x̂i |x′ ) − ∆x̂i ,x′ ≤ G′i ≤ p(x̂i |x′ ) + ∆x̂i ,x′ , ∆x̂i ,x , ∆x̂i ,x′ ∈ ∆, x, x′ ∈ Xk , X̂ = {x̂1 , . . . , x̂b }, i ∈ [b]. B. Computing α, β, δ Parameters Algorithm 1 computes (α, β, δ) − DTX̂→Xk for two dependent attributes X̂ and Xk . Here, we traverse all possible G and G′ values over the Xk alphabet as in line 3. Next, we compute the possible lower (i.e., L, L′ ) and upper (i.e., U, U ′ ) values of the actual distribution based on the known distribution PK and uncertainty ∆ in lines 4-5. Next, we traverse through the alphabet of X̂, x̂ ∈ X̂ using for-loop at line 8. Next, we

assign PK (X̂ = x̂|Xk = x) and PK (X̂ = x̂|Xk = x′ ) into g and g ′ , respectively at lines 9-10. Then, we can compute the maximum value for α as at line 12 and the maximum value for δ as at line 16. To compute β for selected G, G′ , we solve the relaxed linear program (LP) defined in line 18, which provides a polynomial-time upper bound to the exact MILP formulation. Then we compute the maximum ϕ at line 20, and β is computed at line 22. Suppose alphabet sizes of Xk and X̂ are |Xk | = a and |X̂ | = b, respectively. If we use the interior point method to solve the LP, then we have b variables and O(b) constraints. Therefore, the time complexity is approximately O(b3.5 ) for fixed numerical precision [32]. Then, Algorithm 1 has time complexity of O(a2 b3.5 ) as it traverses through all possible pairs x, x′ ∈ Xk . Algorithm 1 Compute (α, β, δ) parameters of DTX̂→Xk . Input: PK (X̂|Xk ) ▷ Known distribution. ∆ ▷ Distributional uncertainty. 1: α ← 0, δ ← 0, ϕ ← 0 ▷ Initialisation. 2: for all x, x′ ∈ Xk do ▷ All possible values pairs in Xk . G ← PK (·|Xk = x), G′ ← PK (·|Xk = x′ ) 3: 4: L ← G − ∆x , U ← G + ∆x ▷ Here, ∆x is uncertainties of PK (·|Xk = x). 5: L′ ← G′ − ∆x′ , U ′ ← G′ + ∆x′ ▷ Here, ∆x′ is uncertainties of PK (·|Xk = x′ ). 6: Mi+ = max(0, Ui − L′i ), Mi− = max(0, Ui′ − Li ), ∀i ∈ [b] δ←0 7: 8: for all x̂ ∈ X̂ do 9: g ← PK (X̂ = x̂|Xk = x) 10: g ′ ← PK (X̂ = x̂|Xk = x′ ) 11: if g ′ − ∆x̂,x′ > 0 then ▷ Here, ∆x̂,x′ is the uncertainty of PK (X̂ = x̂|Xk = x). min(1,g+∆ ) 12: α ← max(α, ln g′ −∆ x̂,x ) ▷ From (15). x̂,x′ 13: else 14: δ ← δ + g + ∆x̂,x ▷ From (17). 15: end if 16: δ ← min(1, max(δ, δ)) 17: end for 18: Linear program: P maximize zi ∈Z, i∈[b] zi ′ Z,G,G

subject to

Mi+ − ′ 0 ≤ zi ≤ M + +M − (Gi − Gi + Mi ); i i ⊤

∀i ∈ [b],

L ≤ G ≤ U, 1 G = 1, L′ ≤ G′ ≤ U ′ , 1⊤ G′ = 1.

ϕ ←Solve the LP with any polynomial-time method (e.g., interior-point) 20: ϕ ← max(ϕ, ϕ) 21: end for 1+ϕ+eα (−1+δ)−2δ 22: β = ln 1+(−1+ϕ)eα −δ ▷ From (16). 23: return α, β, δ 19:

C. Estimating CPL Using Dependency Triad As illustrated in Algorithm 2, CPL can be estimated in constant time O(1) using (α, β, δ) − DTX̂→Xk and (14). Algorithm 2 Compute CPL (i.e., LX̂→Xk ) using (α, β, δ) − DTX̂→Xk . Input: α, β, δ ▷ Parameters of DTX̂→Xk . ε ▷ Privacy budget of the mechanism of X̂. 1: if eα − 1 − δ(eε − 1) < 0 then
▷ From (14). 2: LX̂→Xk ← ln 1 + δ(eε − 1) 3: else   α α δ−δeε +eα+ε (−1+eβ +δ)−1 4: LX̂→Xk ← ln eδ(e+δ−e ε −1)−eε +eβ (−1+eα +δ+eε −δeε ) 5: end if 6: return LX̂→X k D. Defining Distribution Uncertainty We consider two main approaches to modeling uncertainty in the known distributions: (i) a naive approach and (ii) a statistically estimated approach. 1) Naive Approach: If we have only one source of known distribution (i.e., PK ), then defining the uncertainty in the known distribution can be tricky. In such scenarios, we adopt a naive method of adding a maximum error margin for PK . Let PK be the known distribution and e be the percentage error. Then the uncertainty ∆ is given by, ∆ = ePK

(18)

In our experiments, we observe that adding 10% − 20% error margin (i.e., e) provides robust CPL estimation in most of the time in real data. See Section VI-E1 for the experimental results. 2) Statistically Estimated Approach: If we have multiple sources to learn the distribution, then uncertainty can be statistically computed. We have identified that the range provides a privacy robust uncertainty while the standard deviation provides a utility-privacy balanced uncertainty level. Range Let PK1 , PK2 , . . . , PKN be the N number of known distributions. Here, PKi ∈ Ra×b . Then the uncertainty ∆ ∈ Ra×b is given by, ∆ = max {PKi } − min {PKi }. i∈[N ]

i∈[N ]

(19)

Here, maxi∈[N ] {PKi } and mini∈[N ] {PKi } compute the maximum and minimum of each entry over all known distributions, respectively. Standard Deviation Let PK1 , PK2 , . . . , PKN be the N known distributions. Here, PKi ∈ Ra×b . Then the uncertainty ∆ ∈ Ra×b is given by, s
2 PN i=1 PKi − PK ∆= . (20) N −1 Here, PK ∈ Ra×b is the mean of PK1 , PK2 , . . . , PKN .

VI. E VALUATION In this section, we experimentally evaluate and validate the proposed Dependency Triad (DT) metric. We first describe the experimental setup in Section VI-A. We then compare DT with competing metrics in Section VI-B. Section VI-C validates the CPL estimated by DT against CPL⋆ , while Section VI-E evaluates its robustness under distributional uncertainty. Section VI-F evaluates DT under different structural regimes, demonstrating that it is not limited to a single dependency pattern. Section VI-G shows how DT can be used to calibrate privacy budgets in data collection settings that incorporate prior knowledge. Section VI-H conducts attribute inference attacks on data collected under privacy budgets calibrated using DT. Finally, Section VI-I compares DT with random sampling. A. Experimental Setup 1) Environment: We implement our experiments using Python 3.10 and run them on an AMD Ryzen Threadripper PRO 3955WX processor, 128GB of RAM, and 4TB of storage. 2) Datasets: We use five real datasets. In these datasets, we have converted continuous numerical attributes into discrete attributes by binning, as this work focuses on privacy leakages related to discrete/categorical data. SPM [28] dataset is a community survey conducted in the USA on the Supplemental Poverty Measure (SPM), which contains 38 attributes with more than 3M samples. CelebA [33] dataset contains 40 binary attributes of human faces with more than 200K samples. Adult [34] is an income survey dataset containing 14 features and over 40K samples. CVD [35] dataset consists of 11 features of 70K cardiovascular patient records. DSS [29] dataset is released by the Department of Social Services (DSS) in Australia, and the selected dataset contains 27 features, with more than 38K samples. Synthetic Datasets. We generate synthetic datasets with two nonlinearly dependent attributes, Xk and X̂, using xk = sin (2πx̂) + n. Here, x̂ ∈ X̂ , xk ∈ Xk , n ∼ N(0, 2), where X̂ and Xk are the alphabets of X̂ and Xk , and N is normal distribution. We create multiple datasets with varying alphabet sizes from 2 to 1000. For example, Figure 4 depicts P (X̂|Xk ) for alphabet size 20. 3) Competitors: We have considered five state-of-the-art CPL computation algorithms to compare and validate DT: ITS [20], CBP [18], HCC-1 [14], HCC-2 [14] and LTM [26]. We use the CPL of HCC-2 and LTM as the reference to evaluate the estimated CPL of DT, because they provide the optimal CPL (i.e., CPL⋆ ) for generic LDP mechanisms when the ground-truth distributions are known (See Table II for comparison details). Additionally, we use random sampling (RS) [27] as a baseline to evaluate DT in high-dimensional statistical learning (i.e., k-marginal).

Fig. 4: Heatmap of the conditional distribution P (X̂ | Xk ) for the synthetic dataset, where both Xk and X̂ have an alphabet size of 20.

4) Evaluation Metrics: We mainly use four metrics to evaluate DT: (i) TCPL, (ii) CPL estimation error, (iii) NMSECPL, and (iv) total variation distance. TCPL quantifies the total CPL of all the attributes in the dataset as X X TCPL = Lx→Xk . (21) Xk ∈X x∈X\{Xk }

CPL Estimation Error quantifies the algebraic error between estimated CPL (L̃x→Xk ) and CPL⋆ (L⋆x→Xk ) by, CPL Estimation Error = L̃x→Xk − L⋆x→Xk .

(22)

Here, we can observe the sign of the estimation error, which is essential to identify whether the estimation is an upper bound or a lower bound for the CPL⋆ . NMSE-CPL quantifies the normalized mean square error between CPL⋆ and the estimated CPL for all the attributes in the dataset as
2 P P ⋆ Xk ∈X x∈X\{Xk } L̃x→Xk − Lx→Xk P P . (23) NMSE = ⋆ 2 Xk ∈X x∈X\{Xk } (Lx→Xk ) Total Variation Distance (TVD) quantifies the discrepancy between the estimated distribution and the true distribution by, TVD(P, P̂ ) =

1X |P (x) − P̂ (x)|. 2

(24)

x∈X

Here, P (x) denotes the true probability of value x, and P̂ (x) denotes the estimated probability after reconstruction from perturbed data. A smaller TVD indicates that the estimated distribution is closer to the true distribution. 5) Uncertainty Metrics: We have considered four commonly used variability measurement metrics to measure the uncertainty of the known distribution. Range is a measurement of the difference between the maximum and minimum value and can be computed using (19). Standard Deviation is a measure of how dispersed the data is in relation to the mean as defined in (20). Variance is the square of standard deviation.

TABLE II: Comparison between different CPL computation algorithms (CPL caused by one attribute about another) with our proposed Dependency Triad (DT). Here, a and b are alphabet sizes of the two attributes. Algorithm/ Metric ITS [20] CBP [18] HCC-1 [14] HCC-2 [14] LTM [26] MI [22]/PCC [23] DT (Ours)

Time Complexity Precomputation Privacy Calculation O(ab) O(2a ) O(a2 b2 ) O(a2 b log b) O(a2 b + ab log b) O(log ab) O(ab) O(1) O(a2 b3.5 ) O(1)

Space Complexity O(ab) O(ab) O(ab) O(ab) O(ab) O(1) O(1)

Distribution Shift Incorporability Not Support Not Support Not support Not support Not Support Not Support Support

Supporting Mechanisms Two-level LDP GRR Simple LDP Any LDP Any LDP N/A Any LDP

Nature of the Estimation CPL⋆ N/A Actual CPL⋆ CPL⋆ Rough Estimation Upperbound

Mean Absolute Deviation (MAD) is a measure of variabil- can characterize the dependency to quantify the potential CPL ity that indicates the
average distance between observations under LDP. The polynomial-time precomputation of DT is a and their mean PK , which is given by, one-time offline calibration step. After calibration, CPL can be evaluated in constant time for any privacy budget. By PN i=1 |PKi − PK | MAD = . (25) contrast, baselines such as HCC-1, HCC-2, and LTM require N repeated full computation for each candidate privacy bud6) Attribute-Inference Attack: We perform attribute- get. This distinction matters in practice, since privacy-budget inference attacks, where the adversary attempts to infer the calibration often requires evaluating many candidate privacy actual value of a target attribute from a perturbed record. budgets to explore the privacy–utility trade-off, especially In our threat model, we assume a worst-case adversary that for large-cardinality attributes. Moreover, DT has addressed knows the perturbation mechanism and the underlying data the long-lasting distribution uncertainty challenge in CPL distribution, but does not observe the exact ground-truth calculation as DT is adjustable to distribution uncertainties and values of individual records. computationally efficient. Appendix L empirically validates Let X = (X1 , . . . , Xn ) be actual user record, and let the time complexity and space complexity of DT. Y = (Y1 , . . . , Yn ) be the perturbed output. For each target ⋆ attribute k ∈ [n], we train an attacker gk : Y−k 7→ Xk , C. Validating DT with CPL In this section, we benchmark the CPL estimations of where Y−k denotes all released attributes except Yk . Here, inference is primarily driven by inter-attribute dependencies. DT against CPL⋆ . First, we evaluate three aspects of the During training, we split the datasets into a disjoint training set (α, β, δ) estimation method using synthetic distributions: (i) and an evaluation set. We apply the mechanism to the training estimation accuracy (Figure 5a), (ii) upper bound guarantee records to obtain perturbed reports Y , and train gk on pairs (Figure 5b), and (iii) robustness to large alphabet sizes (Fig(Y−k , Xk ). We instantiate gk using a neural TabTransformer- ure 5c). Four calibration levels are used in these experiments (ε0 = 1, 0.5, 0.1, and 0). Note that DT corresponds to the based attacker. See Appendix N for more details. Metric - We measure attribute-inference success (AIA) (α, β, δ) method calibrated at ε0 = 0, i.e., (α, β, δ)ε0 =0 . Here, using Macro-F1 [36]. For each attribute Xk , k ∈ [n], we ε0 = 0 refers to the calibrated parameters limit ε0 → 0 (See compute the Macro-F1 score between the attacker’s prediction Section IV-B4 for more details). DT (i.e., (α, β, δ)ε0 =0 ) remains consistently close to CPL⋆ , gk (Y−k ) and the ground truth Xk , and then average across even for alphabets containing 1, 000 symbols as shown in attributes.
Figure 5(c). In contrast, the estimation error of the uncalibrated 1 X Inference Accuracy = AIA = MacroF1 gk (Y−k ), Xk . (α, γ, δ) method increases considerably with alphabet size. n k∈[n] This highlights the importance of calibration (Section IV-B4). Finally, we evaluate DT on five real-world datasets (TaLower ‘Inference Accuracy’ indicates stronger resistance to ble III and Figure 6). DT achieves very low NMSE-CPL error attribute inference. 7) Privacy Budget Calibration Algorithms: Privacy budget (< 0.025) across all datasets for privacy budget ε ∈ [0.01, 10], ⋆ calibration is the process of adjusting the privacy budgets of confirming the tightness of its estimates relative to CPL mechanisms to trade off privacy and utility based on the re- on real data. NMSE-CPL error is further low (< 0.003) in quirements. We have proposed an algorithm (see Appendix K) high privacy regime ε ∈ (0, 1], which is commonly used in to calibrate the privacy budgets of each attribute when there practice [9]. is a targeted overall privacy for all attributes. D. Interpreting CPL Through DT Parameters B. Benchmark Although DT characterizes CPL through three parameters We use state-of-the-art six benchmarks: IST [20], CBP [18], HCC-1 [14], HCC-2 [14], LTM [26] and MI [22]/PCC [23] to compare DT as summarized in Table II. Unlike existing approaches, DT is the first metric to show that three parameters

(α, β, δ), each parameter captures a distinct aspect of the dependency structure. In this section, we empirically examine how these parameters relate to the actual CPL observed across real datasets. Specifically, we compute CPL and the

(a)

(b)

(c)

Fig. 5: CPL analysis on two attribute synthetic datasets. Here, ε0 refers to the calibrated parameters at ε0 . Further, ε0 = 0 refers to the calibrated parameters limit ε0 → 0. (a) The estimated CPL of different methods varies with privacy budget ε. Here, the alphabet size of the dataset is 10. (b) CPL estimation error varies with ε. Here, the alphabet size of the dataset is 10. (c) The estimated CPLs of different methods vary with the alphabet size of the two attributes. TABLE III: The summary of optimal TCPL (TCPL⋆ ) and estimated TCPL by DT for real datasets. Dataset

SPM CelebA Adult CVD DSS

ε

TCPL⋆

0.5 1 0.5 1 0.5 1 0.5 1 0.5 1

291.45 601.56 101.04 221.53 40.33 84.15 17.88 37.53 215.44 437.39

DT Estimated TCPL NMSE-CPL 294.33 0.00041 613.68 0.0017 101.04 1.03e−26 221.53 8.73e−27 41.00 0.00074 86.81 0.0025 18.13 0.00051 38.73 0.0025 218.99 0.00063 450.60 0.0022

to 0.69 as ε increases. This suggests that β is the dominant explanatory parameter when the privacy budget is small. In contrast, P CC(ln(α), ln(CPL)) increases from 0.67 to 0.97 as ε grows, indicating that α becomes more informative in lower-privacy regimes where weaker perturbation allows stronger dependency effects to be expressed. Since δ implicitly captures edge cases where the distribution is sparse, we have not specifically evaluated. Overall, these results provide an interpretable view of the DT parameters: β characterizes CPL under strong privacy protection, while α becomes increasingly important as the privacy budget increases.

(a)

Fig. 6: NMSE-CPL between CPL⋆ and DT for the real datasets.

corresponding DT parameters for every pair of attributes in the five real datasets. Figure 7a shows that β provides a useful single-parameter interpretation of CPL in high-privacy regimes, i.e., when the privacy budget ε is small. In particular, the results show an approximately linear relationship between ln(β) and ln(CPL). For ε = 1, the observed CPL is also upper-bounded by the privacy budget, with max(CPL) = 1, as expected. We further quantify this relationship using the Pearson correlation coefficient (PCC). Figure 7b reports the PCC between ln(α), and ln(CPL), and ln(β) and ln(CPL) across different privacy budgets. The results show that P CC(ln(β), ln(CPL)) is high in the strong-privacy regime, decreasing from 0.97

(b)

Fig. 7: Interpreting CPL Through DT Parameters using all five real datasets. (a) β vs CPL at ε = 1. (b) Pearson correlation coefficient (PCC) between ln(α)(or ln(β)) and ln(CPL), over privacy budgets. E. Tolerating Distribution Uncertainties 1) Evaluating Distribution Uncertainty Defining Methods: Next, we evaluate the impact of estimation accuracy and privacy guarantee in different uncertainty-defining methods: statistically estimated uncertainty and naively defined uncertainty. Due to the limited space, we include the experimental results in Appendix M. Statistically Estimated Uncertainty - Experimental results show that range and standard deviation (std) based uncertainty computations offer greater privacy tolerance, with std-based uncertainty being particularly robust across different prior knowledge settings.

Naively Defined Uncertainty - The experiments demonstrate that defining uncertainty within the range 10% ≤ e ≤ 20% provides the best balance between preserving utility and ensuring privacy.

TABLE IV: Summary of CPL estimation errors of DT across different structural regimes. The table reports the mean error and standard deviation; lower values indicate better estimation accuracy. Structural Regime Low entropy conditionals Sparse concentrated Many to one One to many Near monotone likelihood ratio Limited tail mass

(a)

0.1 9.4e−9± 4.3e−9 3.4e−5± 3.0e−5 1.8e−8± 7.8e−9 4.4e−5± 2.5e−5 7.9e−4± 2.5e−1 1.1e−4± 6.9e−5

Privacy Budget (ε) 1 5 9.2e−8± 9.3e−8± 4.4e−8 4.3e−8 2.8e−2± 2.4e−1± 2.1e−2 1.2e−1 1.7e−7± 1.6e−7± 9.1e−8 7.6e−8 2.0e−2± 1.1e−1± 1.3e−2 7.4e−2 2.5e−1± 7.9e−1± 8.6e−2 2.6e−1 3.8e−2± 1.9e−1± 2.2e−2 5.3e−2

10 5.3e−9± 8.4e−10 4.2e−2± 5.0e−2 6.0e−9± 3.0e−9 7.0e−3± 8.8e−3 1.5e−1± 1.8e−1 5.9e−2± 5.0e−2

(b)

2) Validating DT Over Distribution Uncertainty: First, we evaluate the CPL variation on the synthetic distribution D1 with alphabet size 10, as shown in Figure 8(a). Here, PK : CPL⋆ denotes the optimal CPL for the known distribution PK . As expected, the CPL estimated by DT is a tight upper bound for PK : CPL⋆ . Next, suppose the actual distribution PA deviates from PK by up to ±10% (i.e., |PA − PK | ≤ 10%). Under this uncertainty, the actual PA : CPL⋆ can range between the ‘PA : Max CPL’ and ‘PA : Min CPL’ lines. The uncertainty-aware DT estimate is depicted by ‘PA : DT ’, which provides a tight upper bound on the maximum CPL ‘PA : Max CPL’. This demonstrates DT’s ability to effectively incorporate uncertainty. Next, we analyse how the estimated CPL of DT changes with varying error margins, as shown in Figure 8(b). The estimated CPL grows with the error parameter e to accommodate a safety margin for greater uncertainty in PK . The case e = 0% corresponds to the ideal scenario where the known distribution perfectly matches the actual.

designed as a conservative estimator, a small positive gap is desirable. Table IV shows that DT provides comparable CPL estimates across diverse dependency structures. The results can be grouped into three cases. First, for concentrated or neardeterministic dependencies, such as low-entropy conditionals and many-to-one mappings, DT is extremely tight across all privacy budgets because the dominant conditional mass largely determines the worst-case leakage. Second, for sparse or asymmetric dependencies, such as sparse concentrated and one-tomany regimes, DT remains accurate but shows moderate looseness, especially at intermediate privacy budgets, where leakage depends on both dominant and sparse support regions. Third, for order-sensitive and tail-sensitive dependencies, such as near-monotone likelihood-ratio and limited-tail-mass regimes, DT becomes more conservative because small tail probabilities or gradual changes in the likelihood ratio can affect the worstcase CPL. Overall, these results show that DT is not limited to a single dependency pattern. It is tightest when leakage is driven by concentrated conditional mass, while remaining conservative for sparse, asymmetric, ordered, and tail-sensitive structures.

F. Evaluating DT in Different Structural Regimes

G. Privacy Budget Calibration

We further evaluate DT under six representative structural regimes of pairwise dependency: (i) low-entropy conditionals, (ii) sparse concentrated distributions, (iii) many-to-one mappings, (iv) one-to-many mappings, (v) near-monotone likelihood-ratio structure, and (vi) limited-tail-mass distributions. These regimes capture different dependency shapes, including concentrated, asymmetric, ordered, and tail-sensitive conditional distributions, which are commonly studied in information theory, sparse distribution analysis, stochastic ordering, and tail-mass estimation [22], [37]. For each regime, we generate 100 synthetic pairwise distributions with an alphabet size of 100 and compare the DT-based CPL estimate with the exact value CPL⋆ across different privacy budgets. We report the CPL estimation error where smaller values indicate tighter estimation. Since DT is

Next, we demonstrate how DT can be used to calibrate the privacy budget of LDP mechanisms, leveraging prior knowledge (with distributional uncertainty) to maximise data utility while satisfying privacy requirements (i.e., achieving a favorable privacy–utility trade-off) in a real-world scenario. We revisit the running motivational example of state-wise data collection (Section I) and instantiate it on the real SPM dataset [28]. We focus on an 8-attribute subset and assume we have prior knowledge from 5 states (NY, CA, MD, IL, TX), yielding empirical distributions {P (s) }5s=1 . Our goal is to leverage this prior information to calibrate a per-attribute privacy-budget vector ε = (ε1 , . . . , ε8 ) that maximises utility in data collections of remaining states, subject to a global privacy requirement ε. Since utility typically increases with larger per-attribute budgets, calibration amounts to choosing

Fig. 8: (a) Evaluation of DT under distributional uncertainty using synthetic dataset. (b) Estimated CPL vs uncertainty level.

(b)

Fig. 9: Calibrated privacy budgets of various algorithms at ε = 3. Here, ‘Actual’ represents the mean and standard deviation of calibrated privacy budgets (CPL⋆ ) for each state, except the initially collected five states. the largest feasible ε while ensuring that the (correlationaware) privacy leakage does not exceed ε. We solve this constrained optimization problem using gradient descent, as detailed in Appendix K. Nominal calibration (ignoring uncertainty). We first form a nominal prior by averaging the 5 known distributions (element-wise) and calibrate ε under the no-uncertainty assumption. Figure 9 shows the calibrated results for ε = 3. In this setting, DT produces calibrated budgets that closely match the theoretical optimum CP L⋆ , which is obtained by the LTM baseline. This indicates that DT is tight in the nominal regime. For context, the “Actual” calibrated budgets in Figure 9 report the mean and standard deviation of budgets obtained by running LTM on other held-out states. The observed variation reflects the dependency shifts induced by demographic differences across states, and therefore highlights a key risk: calibrating solely on the averaged prior can be overly optimistic, and may violate the intended privacy level due to distributional mismatch. Uncertainty-aware calibration. We next quantify distributional uncertainty via the variance-based estimator presented in Section V-D2 and calibrate ε using uncertainty-aware DT. As expected, accounting for uncertainty systematically yields smaller per-attribute budgets, i.e., a deliberate safety margin that hedges against plausible shifts in the dependency structure. This behavior is evident in Figure 9(b): DT (with uncertainty) lies below LTM and closely tracks the lower envelope of the observed “Actual” privacy risk across attributes, thereby preventing underestimation of leakage when the data distribution changes. In contrast, LTM can become optimistic under mismatch (underestimating privacy risks), whereas DT remains reliable by conservatively overestimating CPL and preserving a robust privacy guarantee. Finally, DT calibrates the full budget vector in 7s for this example, compared to 61s for LTM, demonstrating an orderof-magnitude speedup in DT. H. Attribute Inference Attacks Next, we evaluate DT and SPL under practical attribute inference attacks. We consider nine attributes with mixed

dependency strengths, including both highly correlated and weakly correlated attributes as measured by mutual information. The data are collected using the GRR mechanism for 3-marginal estimation, and an attribute inference attack is performed separately for each target attribute. We compare the attack accuracy of DT and SPL at the same average total variation distance (TVD), so that both methods are evaluated under comparable utility levels. Table V reports the results for TVD = 0.4 and TVD = 0.2. As expected, SPL requires a larger overall privacy budget to achieve the same utility level as DT. Despite this, DT shows comparable robustness against attribute-inference attacks, even though it allocates larger per-attribute privacy budgets to selected attributes through CPL-aware budget allocation. Additionally, we observe that weakly correlated attributes are unlikely to be exploitable via attribute-inference attacks, as inference accuracy remains largely constant across different utility levels. These results suggest that CPL-based budget allocation improves utility while preserving comparable privacy guarantees. In particular, DT achieves the same TVD with a smaller overall privacy budget than SPL, while maintaining comparable attack robustness across the evaluated attributes. TABLE V: Summary of the attribute inference attack on DT and SPL. The table reports the inference accuracy (AIA) and corresponding privacy budget for T V D = 0.2 and 0.4 (estimation error of 3-marginal). Here, ε denotes the overall privacy budget. Attribute Marital status Gender Person’s Medicare Race Hispanic Poverty status Unit has a minor Unit has couples Child care expenses

TVD 0.2 0.4 0.2 0.4 0.2 0.4 0.2 0.4 0.2 0.4 0.2 0.4 0.2 0.4 0.2 0.4 0.2 0.4

ε 2.94 1.72 2.94 1.72 2.94 1.72 2.94 1.72 2.94 1.72 2.94 1.72 2.94 1.72 2.94 1.72 2.94 1.72

DT AIA 0.200 0.187 0.445 0.405 0.156 0.156 0.193 0.180 0.489 0.489 0.463 0.463 0.498 0.498 0.468 0.468 0.330 0.330

ε 9.0 6.17 9.0 6.17 9.0 6.17 9.0 6.17 9.0 6.17 9.0 6.17 9.0 6.17 9.0 6.17 9.0 6.17

SPL AIA 0.201 0.190 0.465 0.410 0.156 0.156 0.203 0.167 0.488 0.489 0.463 0.463 0.498 0.498 0.468 0.468 0.330 0.330

I. Comparison with Random Sampling To evaluate whether the proposed dependency-aware budget allocation provides utility benefits beyond standard samplingbased multidimensional LDP, we include random sampling (RS) as a baseline for k-marginal estimation. In RS, each user reports only one randomly selected k-way attribute subset and perturbs the corresponding joint value using the full privacy budget. This makes RS attractive because it avoids splitting the privacy budget among multiple attributes or marginals. However, for joint frequency estimation, RS suffers from

(a) 2-Marginal

(b) 3-Marginal

(c) 4-Marginal

Fig. 10: TV distance (TVD) versus privacy budget ε for k-marginal estimation with k = 2, 3, 4. Lower TVD indicates better estimation utility. CPL-aware budget-tuning methods achieve substantially lower TVD than SPL and remain competitive with RS, with clearer advantages for higher-order marginals.

sample fragmentation: each k-way marginal is estimated only from the users who selected that specific view. As k increases, the number of possible views and the joint domain size both grow, resulting in fewer effective samples per marginal and consequently higher estimation error. Figure 10 reports the TV distance for 2-, 3-, and 4-marginal estimation under different privacy budgets. Here, we select the same nine attributes used in the attribute inference attack. For 2-marginals, RS is competitive with CPL-aware budget-tuning methods, since the number of views and the joint domain size remain relatively small. However, the advantage of DT becomes clearer for higher-order marginals. For 3- and 4marginals, both variants of DT achieve lower TV distance than RS across most privacy budgets, while SPL performs substantially worse because the privacy budget is uniformly divided across attributes. These results demonstrate that although RS can be effective for low-dimensional marginal estimation, it becomes less reliable for higher-order joint frequency estimation. By exploiting the dependency structure among attributes, DT allocates the privacy budget more effectively and preserves more useful joint-distribution information, leading to better utility in correlation-sensitive estimation tasks. VII. R ELATED W ORK We start this section by exploring the concept of prior knowledge and its implications for privacy risks. We then review existing CPL analysis algorithms under Differential privacy (DP) and Local differential privacy (LDP). A. CPL and Prior Knowledge Prior knowledge can manifest in various forms depending on the data context, ranging from statistical distributions [21], [17] to temporal dependencies in time-series data [2], [20], and spatial inferences such as estimating the current location from previously observed ones [20], [3]. Studies have shown that adversaries may acquire such knowledge through multiple channels, including public datasets [34], [33], social norms [17], or even during the data collection process itself [19], [12]. These sources of prior knowledge significantly heighten privacy risks, and (L)DP mechanisms require explicitly accounting for such knowledge to safeguard privacy [17], [21], [12].

B. CPL Computation in DP and LDP DP [38] and LDP [8] have emerged as standard techniques for safeguarding privacy, primarily due to the limitations of earlier approaches such as k-anonymity [39] and l-diversity [40]. LDP is widely employed when the data collector is considered untrusted [3], [11], [10], [9]. Study [13] is a pioneering work that highlights the privacy risks with correlated data under the central setting of DP. Then, studies propose different methods to address the privacy risks in correlated data. Group DP is a simple method to adjust the global sensitivity based on the number of correlated records [41]. Privacy budget splitting and sampling methods are commonly adopted methods to apply LDP in correlated data [27]. These methods primarily assume no prior knowledge. When prior knowledge is available, studies propose different algorithms to measure the CPL using prior knowledge. We can group them into two main categories as discussed in the following sections. 1) Conventional Correlation Metrics Based CPL Analysis and Their Problems: Early studies tend to adopt conventional correlation metrics (e.g., mutual information (MI), Pearson correlation coefficient (PCC), and covariance) to measure the CPL. Study [21] formulates the sensitivity parameter using a correlation degree matrix. Another study [42] uses distance correlation to measure the correlation. In [43], a periodic sensitivity calculation algorithm is proposed to address the periodic correlation changes in temporal data using autocorrelation. Study [18] proposes a covariance-based algorithm to quantify CPL, and [44] calibrates privacy budgets using PCC to tradeoff privacy and utility. However, these conventional metrics are unable to correctly characterize some critical properties of CPL in (L)DP—e.g., asymmetric behavior and identifying the worst-case scenario [14]. 2) Bayesian Theorem-Based Algorithms to Compute CPL: Study [26] proposes an algorithm to quantify the CPL in DP. A recent study [20] has analyzed privacy leakage related to spatial-temporal data, a specific family of LDP mechanisms which have two levels of perturbation probabilities (i.e., GRR [30], Unary encoding [24], Hash encoding [24], etc.). Study [14] proposes two algorithms to compute CPL in

any LDP mechanism. However, all these algorithms primarily assumed that ground truth probability distributions are known, which is usually not true, especially for locally perturbing scenarios like LDP. Furthermore, these algorithms have either polynomial or logarithmic time complexity over alphabet size, which can be challenging when CPL is iteratively evaluated at different privacy budgets to calibrate utility and privacy. In summary, privacy leakage analysis in correlated environments is crucial to guarantee the privacy of mechanisms as well as to maximize the utility by tuning the privacy budgets. However, the CPL analysis is currently performed using computationally expensive algorithms that assume the ground-truth distributions are known. Therefore, currently, there is no method to time efficiently estimate CPL under inaccurate distributional information. VIII. C ONCLUSION This work demonstrates that three parameters derived from the joint distribution of two attributes are sufficient to construct a conservative surrogate for pairwise correlation-induced privacy leakage (CPL), even under distributional uncertainty. We formalise these parameters as a new metric, the Dependency Triad (DT), and provide a theoretical foundation for its use. DT is not intended to fully characterise the underlying joint distribution; rather, we prove that it yields a tight, uncertaintyaware upper bound on pairwise CPL. Further, we develop algorithms that enable practical CPL evaluation and privacybudget calibration. Since exact multidimensional privacy leakage analysis is often intractable, this pairwise formulation provides a tractable building block for assessing total privacy leakage across attributes. Collectively, these results show that DT is more than an empirical heuristic: the proofs certify when and why DT remains conservative enough to mitigate privacy risks, while staying tight in the nominal regime. Moreover, DT overcomes two key limitations of prior CPL computation methods by (i) explicitly incorporating configurable dependence through uncertainty in distributional information and (ii) enabling constant-time CPL estimation using the computed parameters of DT. Our empirical results corroborate the theory: DT accurately tracks CPL, particularly in high-privacy regimes (e.g., ε ≤ 1), and scales effectively to high-dimensional settings. Limitations and Future work - This work focuses on estimating CPL in pure LDP mechanisms using the proposed metric DT. We will extend this work to CPL estimation in approximated LDP mechanisms in our future work. E THICAL C ONSIDERATIONS We use five publicly available datasets—SPM, CelebA, Adult, Cardiovascular (CVD), DSS—under their research licenses and within their stated consent and usage scopes. R EFERENCES [1] U. Erlingsson, V. Pihur, and A. Korolova, “Rappor: Randomized aggregatable privacy-preserving ordinal response,” in Proceedings of the 2014 ACM SIGSAC CCS, 2014.

[2] H. Wang, H. Hong, L. Xiong, Z. Qin, and Y. Hong, “L-srr: Local differential privacy for location-based services with staircase randomized response,” in 2022 ACM SIGSAC, ser. CCS ’22, p. 2809–2823. [3] J. W. Kim, K. Edemacu, J. S. Kim, Y. D. Chung, and B. Jang, “A survey of differential privacy-based techniques and their applicability to location-based services,” Computers Security, vol. 111, 2021. [4] X. Gu, M. Li, Y. Cheng, L. Xiong, and Y. Cao, “PCKV: Locally differentially private correlated Key-Value data collection with optimized utility,” in USENIX Security 20, 2020. [5] M. Yang, T. Guo, T. Zhu, I. Tjuawinata, J. Zhao, and K.-Y. Lam, “Local differential privacy and its applications: A comprehensive survey,” Computer Standards Interfaces, 2024. [6] A. T. Oyewole, B. B. Oguejiofor, N. E. Eneh, C. U. Akpuokwe, and S. S. Bakare, “Data privacy laws and their impact on financial technology companies: A review,” Computer Science & IT Research Journal, 2024. [7] W. Xie, M. Kantarcioglu, W. S. Bush, D. C. Crawford, J. C. Denny, R. Heatherly, and B. A. Malin, “Securema: protecting participant privacy in genetic association meta-analysis,” Bioinformatics, vol. 30 23, pp. 3334–41, 2014. [8] J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy and statistical minimax rates,” in 2013 51st Annual Allerton Conference on Communication, Control, and Computing, 2013, pp. 1592–1592. [9] G. Cormode, S. Jha, T. Kulkarni, N. Li, D. Srivastava, and T. Wang, “Privacy at scale: Local differential privacy in practice,” ser. SIGMOD ’18. ACM, 2018, p. 1655–1658. [10] B. Ding, J. Kulkarni, and S. Yekhanin, “Collecting telemetry data privately,” ser. NIPS’17, Red Hook, NY, USA, 2017, p. 3574–3583. [11] A. Inc., “Learning with privacy at scale,” https://machinelearning.apple. com/research/learning-with-privacy-at-scale, 2017. [12] Z. Zhang, T. Wang, N. Li, S. He, and J. Chen, “Calm: Consistent adaptive local marginal for marginal release under local differential privacy,” in ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’18, 2018, p. 212–229. [13] D. Kifer and A. Machanavajjhala, “No free lunch in data privacy,” ser. SIGMOD ’11. ACM, 2011, p. 193–204. [14] S. Jayawardana, S. Ulukus, M. Ding, and K. Thilakarathna, “The hidden cost of correlation: Rethinking privacy leakage in local differential privacy,” 2025. [Online]. Available: https://arxiv.org/abs/2508.12539 [15] 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, no. 5, p. 1126–1139, 2023. [16] H. H. Arcolezi, J.-F. Couchot, B. Al Bouna, and X. Xiao, “Random sampling plus fake data: Multidimensional frequency estimates with local differential privacy,” in Proceedings of the 30th ACM CIKM, 2021, p. 47–57. [17] Y. Li, X. Ren, S. Yang, and X. Yang, “Impact of prior knowledge and data correlation on privacy leakage: A unified analysis,” IEEE Transactions on Information Forensics and Security, vol. 14, no. 9, pp. 2342–2357, 2019. [18] R. Du, Q. Ye, Y. Fu, and H. Hu, “Collecting high-dimensional and correlation-constrained data with local differential privacy,” in 2021 18th Annual IEEE SECON, 2021, pp. 1–9. [19] F. Wei, E. Bao, X. Xiao, Y. Yang, and B. Ding, “Aaa: An adaptive mechanism for locally differentially private mean estimation,” Proc. VLDB Endow., vol. 17, no. 8, p. 1843–1855, 2024. [20] K. M. Chong and A. Malip, “Local differential privacy for correlated location data release in its,” Computer Networks, vol. 255, p. 110830, 2024. [21] T. Zhu, P. Xiong, G. Li, and W. Zhou, “Correlated differential privacy: Hiding information in non-iid data set,” IEEE Transactions on Information Forensics and Security, vol. 10, no. 2, pp. 229–242, 2015. [22] T. M. Cover and J. A. Thomas, Entropy, Relative Entropy, and Mutual Information. John Wiley and Sons, Ltd, 2005, ch. 2, pp. 13–55. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10. 1002/047174882X.ch2 [23] H. Akoglu, “User’s guide to correlation coefficients,” Turkish Journal of Emergency Medicine, vol. 18, no. 3, pp. 91–93, 2018. [24] T. Wang, N. Li, and S. Jha, “Locally differentially private frequent itemset mining,” in 2018 IEEE Symposium on Security and Privacy (SP), 2018, pp. 127–143. [25] Q. Geng, P. Kairouz, S. Oh, and P. Viswanath, “The staircase mechanism in differential privacy,” IEEE Journal of Selected Topics in Signal Processing, vol. 9, pp. 1176–1184, 2015.

A PPENDIX

[26] Y. Cao, M. Yoshikawa, Y. Xiao, and L. Xiong, “Quantifying differential privacy under temporal correlations,” in ICDE, 2017, pp. 821–832. [27] T. Wang, J. Blocki, N. Li, and S. Jha, “Locally differentially private protocols for frequency estimation,” in USENIX Security 17, 2017, pp. 729–745.

O PEN S CIENCE Artifacts are available in https://github.com/ SandaruJayawardana/dependency-triad-ccs26.

[28] U.S. Census Bureau, “ACS Supplemental Poverty Measure (SPM) Research Files: 2009–2019, 2021–2023,” https://www.census. gov/data/datasets/time-series/demo/supplemental-poverty-measure/ acs-research-files.html, 2025. [29] A. U. R. I. N. (AURIN), “Dss 2016 dataset,” https://data.gov.au/data/ dataset/dss-payment-demographic-data. [30] T. Wang, X. Zhang, J. Feng, and X. Yang, “A comprehensive survey on local differential privacy toward data statistics and analysis,” Sensors, vol. 20, no. 24, 2020. [31] G. P. McCormick, “Computability of global solutions to factorable nonconvex programs: Part i—convex underestimating problems,” Mathematical Programming, vol. 10, no. 1, pp. 147–175, 1976. [32] S. Boyd and L. Vandenberghe, Convex Optimization. University Press, 2004.

Cambridge

[33] Z. Liu, P. Luo, X. Wang, and X. Tang, “Deep learning face attributes in the wild,” in ICCV, December 2015. [34] B. Becker and R. Kohavi, “Adult,” UCI Machine Learning Repository, 1996, DOI: https://doi.org/10.24432/C5XW20. [35] S. Sulianova, “Cardiovascular disease dataset,” https://www.kaggle.com/ datasets/sulianova/cardiovascular-disease-dataset, 2021. [36] J. Opitz and S. Burst, “Macro f1 and macro f1,” 2021. [Online]. Available: https://arxiv.org/abs/1911.03347 [37] S. Karlin and H. Rubin, “The theory of decision procedures for distributions with monotone likelihood ratio,” The Annals of Mathematical Statistics, vol. 27, pp. 272–299, 1956. [38] C. Dwork, “Differential privacy,” in Automata, Languages and Programming, M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 1–12.

A PPENDIX A T HE CPL⋆ A LGORITHM Algorithm 3 Compute CPL⋆ (HCC method [14]). Input: P (X̂|Xk ) ▷ Conditional probability distribution. ε ▷ Privacy budget of M̂ . 1: L ← 0 ▷ Variable to keep maximum leakage. 2: for all x, x′ ∈ Xk do 3: G ← P (X̂|Xk = x) 4: G′ ← P (X̂|Xk = x′ ) 5: Q ← sort(G ⊘ G′ ) ▷ Descending order element-wise ratios. 6: A, B ← 0 ▷ Variables to keep the summation. 7: for all Qi ∈ Q do 1+A(exp(ε)−1) then 8: if Qi ≥ 1+B(exp(ε)−1) 9: A←A+g ▷ g is the element of G corresponds to Qi . 10: B ← B + g′ ▷ g ′ is the element of G′ corresponds to Qi . 11: end if 12: end for   1+A(exp(ε)−1) 13: L ← max L, 1+B(exp(ε)−1) ▷ The maximum. 14: end for 15: return LX̂→X = ln L k

[39] L. Sweeney, “Achieving k-anonymity privacy protection using generalization and suppression,” Int. J. Uncertain. Fuzziness Knowl.-Based Syst., vol. 10, no. 5, p. 571–588, Oct. 2002.

A PPENDIX B M ONOTONICITY OF L INEAR F RACTIONAL F UNCTIONS

[40] A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam, “L-diversity: privacy beyond k-anonymity,” in ICDE’06, 2006, pp. 24– 24. [41] C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,” Foundations and Trends® in Theoretical Computer Science, vol. 9, pp. 211–407, 2014. [42] S. Biswas, A. Fole, N. Khare, and P. Agrawal, “Enhancing correlated big data privacy using differential privacy and machine learning,” Journal of Big Data, vol. 10, no. 1, p. 30, 2023.

Lemma B.1 will be used in mathematical proofs. 1 Lemma B.1. The function f (x) defined as f (x) = aa12 x+b x+b2 is monotonic. Specifically, f (x) is increasing with respect to x if a1 b2 − a2 b1 ≥ 0, and f (x) is strictly decreasing with respect to x if a1 b2 − a2 b1 < 0.

(x) −a2 b1 Proof. We have dfdx = a(a12b2x+b 2 . 2)

[43] J. Zhao, S. Liu, X. Xiong, and Z. Cai, “Differentially private autocorrelation time-series data publishing based on sliding window,” Secur. Commun. Networks, vol. 2021, pp. 6 665 984:1–6 665 984:10, 2021. [44] J. Wei, J. Li, Y. Lin, and J. Zhang, “Ldp-based social content protection for trending topic recommendation,” IEEE IoT Journal, vol. 8, no. 6, pp. 4353–4372, 2021.

Therefore,

df (x) dx

(

≥0 <0

; if a1 b2 − a2 b1 ≥ 0, ; otherwise.

This completes the proof. A PPENDIX C P ROOF T HEOREM IV.1

[45] X. Huang, A. Khetan, M. Cvitkovic, and Z. Karnin, “Tabtransformer: Tabular data modeling using contextual embeddings,” 2020. [Online]. Available: https://arxiv.org/abs/2012.06678

First, let us formulate the optimization problem based on (6) as

ε i∈[b]\S Gi + e i∈S Gi P F (S, G, G , ε) = P ′ ′ + eε G i∈S Gi i∈[b]\S i ′ ′ ′ Gi = qi Gi ; ∀i ∈ [b], Gi ∈ G, Gi ∈ G , qi ∈ Q, ′ 0 < Gi , Gi ≤ 1; ∀i ∈ [b], X X Gi = 1, G′i = 1, S ⊆ [b]. i∈[b] i∈[b]

P

maximize ′ G,G ,S

subject to

P

′

(26) Here, we need to maximize F (·) with respect to all S, G, G′ . Next, we consider an alternative optimization problem (27) with relaxing the strict constraints Gi = qi G′i , ∀i ∈ [b] in (26). Also, let us assume that S is fixed for the simplicity and |S| = b − r (i.e., |[b] \ S| = r). Later, we show that the optimal result is independent of S. P P ε i∈[b]\S Gi + e i∈S Gi ′ P maximize F (S, G, G , ε) = P ′ ′ ε ′ G,G i∈S Gi i∈[b]\S Gi + e subject to

Gi ≤ eα G′i ;

∀i ∈ [b], α = ln max q,

G′i ≤ eγ Gi ;

∀i ∈ [b], γ = − ln min q,

q∈Q

q∈Q

0 < Gi , G′i ≤ 1; X

Gi = 1,

i∈[b]

∀i ∈ [b], X G′i = 1.

Proposition C.1. Using the same notation as above, α α+ε γ (e −1) maxG,G′ , G⊘G′ ∈Q̃ F (S, G, G′ , ε) = eeε (e−1+e γ −1)+eγ (eα −1) . ⋆ Proof. Let P us take F as thePoptimal′ solution for (27). Since i∈[b] Gi = 1 and i∈[b] Gi = 1, we have P P 1 − j∈S Gj + eε j∈S Gj ′ P P F (S, G, G , ε) = . (28) 1 − j∈S G′j + eε j∈S G′j

Moreover, we can take Gi = g and G′i = g ′ for all i ∈ S as it does not change the optimal solution for (27). Then we can write F (S, G, G′ , ε) in a form of U (g, g ′ , ε, b, r) as 1 + (b − r)(eε − 1)g . 1 + (b − r)(eε − 1)g ′

(29)

Next, let us take the ratio gg′ = q. Here, q should be q > 1 to maximize U (·). Then we can write U (g, g ′ , ε, b, r) in a form of V (q, g ′ , ε, b, r) as 1 + (b − r)(eε − 1)qg ′ . 1 + (b − r)(eε − 1)g ′

(30)

Here, we know that V (·) monotonically increases with g ′ from Lemma B.1 as (b − r)(eε − 1)(q − 1) ≥ 0. We can calculate the feasible g ′ values based on the constraint G′i ≤ eγ Gi for all i ∈ [b] in (27). From this constraint, we have X X G′i ≤ eγ Gi . (31) i∈[b]\S

eγ − 1 . (qeγ − 1)(b − r)

(32)

Note that the upper bound of g ′ monotonically decreases as q increases. Moreover, V (·) monotonically increases with q as (b−r)(eε −1)g ′ ′ 1+(b−r)(eε −1)g ′ > 0. Therefore, to check which g and q values maximize V (·), let us compute V (q, g ′ = eγ −1 (qeγ −1)(b−r) , ε, b, r) as
−1 + 1 + eε (eγ − 1) q V (·) = ε γ . e (e − 1) − eγ + eγ q

(33)

γ

−1 Here, we know that V (q, g ′ = (qeγ e−1)(b−r) , ε, b, r) monotonically increases with q from Lemma B.1 as 1 + eε (eγ −
ε γ
γ γ ε ε γ 2 1) e (e − 1) − e − e = e (e − 1)(e − 1) ≥ 0. Since q ∈ {1, eα }, the optimal solution F ⋆ is given by q = eα and γ −1 , g ′ = (qeγ e−1)(b−r)

eα − 1 + eα+ε (eγ − 1) . eε (eγ − 1) + eγ (eα − 1)

(34)

i∈[b]

Next, we establish intermediate results: Proposition C.1 and Corollary C.2 to prove Theorem IV.1.

V (q, g ′ , ε, b, r) =

0 ≤ g′ ≤

F⋆ = (27)

U (g, g ′ , ε, b, r) =

P P Here, i∈[b]\SP G′i and i∈[b]\S Gi can be written P using terms of g ′ and q as i∈[t]\S G′i = 1 − (b − r)g ′ and i∈[b]\S Gi = 1 − (b − r)qg ′ . Therefore, we have

i∈[b]\S

Therefore, the optimal solution for (27) is given by when G α −γ b } . Thus maxG,G′ ,G⊘G′ ∈Q̃ F (S, G, G′ , ε) = G′ ∈ {e , e ⋆ F . This completes the proof of Proposition C.1. Based on Proposition C.1, we can state the following Corollary C.2, which is required to prove Theorem IV.1. Corollary C.2. When b = 2, the solution for the optimization problem (26) can be solved with Proposition C.1. Proof. The constraint Gi = qi G′i in (26) becomes Q̃ for b = 2. Therefore, we can compute the optimal solution of (26) using the Proposition C.1. This completes the proof of Corollary C.2. Proof of Theorem IV.1 Proof. Next, let us move to the proof of Theorem IV.1. We can find a scenario where all Gi and G′i values go to zero except the value corresponding to the maximum ratio and minimum ratio (i.e., e−γ and eα ) for any G, G′ without violating the constraints in (26). In such a case, the impact on the objective function of (26) is equivalent to b = 2. Then, from Corollary C.2, the solution for (26) equals to (34) (i.e., Proposition C.1). Therefore, the correlation-induced privacy leakage (CPL) satisfies max(G,G′ )∈H CPL(G, G′ ) = α α+ε γ (e −1) max(G,G′ )∈H̃ CPL(G, G′ ) = ln eeε (e−1+e γ −1)+eγ (eα −1) . This completes the proof of Theorem IV.1.

A PPENDIX D P ROOF OF C OROLLARY IV.2 Proof. Let U1 and U2 be estimated CPL values corresponds to (α1 , γ1 ) and (α2 , γ2 ) respectively. eα1 − 1 + eα1 +ε (eγ1 − 1) eε (eγ1 − 1) + eγ1 (eα1 − 1) eα2 − 1 + eα2 +ε (eγ2 − 1) U2 = ε γ2 e (e − 1) + eγ2 (eα2 − 1) Since γ2 = α1 and α2 = γ1 , eγ1 − 1 + eγ1 +ε (eα1 − 1) = ε α1 e (e − 1) + eα1 (eγ1 − 1) U1 =

Next, let us evaluate U1 − U2 eα1 − 1 + eα1 +ε (eγ1 − 1) eγ1 − 1 + eγ1 +ε (eα1 − 1) − λ1 λ2 (−1 + eα1 )(eα1 − eγ1 )(−1 + eγ1 )(−1 + eε )2 = . λ1 λ2 =

Since the objective function is monotonically increasing with respect to g, maximizing F (·) requires maximizing g. We therefore consider an upper bound function V (·) of F (·), obtained by replacing g with its upper bound g. Let V ⋆ denote the maximum value of V (·). We then show that there always exist attainable vectors G and G′ such that F (·) = V ⋆ , which implies the optimality of V ⋆ for fixed S. From the constraint Gi ≤ eα G′i + δ̃i , ∀Gi ∈ G, G′i ∈ G′ , we have X X X Gi ≤ eα G′i + δ̃i , i∈[S] i∈[S] i∈[S] (38) α ′ g ≤ e g + δ̃. P Here, i∈S δ̃i = δ̃. From the constraint G′i ≤ eγ G′i + δ̂i , ∀Gi ∈ G, G′i ∈ G′ , we have X X X G′i ≤ eγ Gi + δ̂i i∈[b]\S

Here, λ1 = eε (eγ1 − 1) + eγ1 (eα1 − 1) and λ2 = eε (eα1 − 1) + eα1 (eγ1 − 1). Since α1 ≥ 1 and γ1 ≥ 1, denominator is positive (i.e., λ1 , λ2 > 0). Therefore, if and only if α1 ≥ γ1 then U1 − U2 ≥ 0. This completes the proof. A PPENDIX E P ROOF OF T HEOREM IV.3 Proof. Based on new constraints in (9), we can formulate the updated optimization problem as P 1 + i∈S Gi (eε − 1) ′ P maximize F (S, G, G , ε) = S,G,G′ 1 + i∈S G′i (eε − 1) subject to

Gi ≤ eα G′i + δ̃i ; ∀i ∈ [b], G′i ≤ eγ Gi + δ̂i ; ∀i ∈ [b],

(35)

0 < Gi , G′i ≤ 1; ∀i ∈ [b], X X Gi = 1, G′i = 1, S ⊆ [b]. i∈[b] i∈[b] A. Simplifying the Problem With Fixed S First, let us fix S (see (36)) and solve the above optimization. Next, we repeat that for all S ⊆ [b] and find the maximum value as the solution for (35). P 1 + i∈S Gi (eε − 1) ′ P maximize F (S, G, G , ε) = G,G′ 1 + i∈S G′i (eε − 1) subject to

Gi ≤ eα G′i + δ̃i ; ∀i ∈ [b], G′i ≤ eγ Gi + δ̂i ; ∀i ∈ [b], 0 ≤ Gi , G′i ≤ 1; ∀i ∈ [b], X X Gi = 1, G′i = 1, S ⊆ [b]. i∈[b] i∈[b]

(36)

F (·) =

1 + g(eε − 1) . 1 + g ′ (eε − 1)

g≤

(37)

i∈[b]\S

(39)

eγ + δ̂ + g ′ − 1 . eγ

P Here, i∈[b]\S δ̂i = δ̂. There are two upper bounds for g (i.e., g) in terms of g ′ : γ ′ −1 g ≤ min{ e +δ̂+g , eα g ′ + δ̃}. eγ Then, we can write an upper bound V (g ′ , δ, ε, α) for F (·) such that 1 + g(eε − 1) V (g ′ , δ, ε, α) = , (40) 1 + g ′ (eε − 1) ′

γ

−1 α ′ where g = min{ e +δ̂+g , e g + δ̃}. Next, we compute V ⋆ , eγ which is the maximum value of V (·) for g ′ ∈ [0, 1]. 1) Compute V ⋆ : We check the valid value range of g ′ and γ ′ −1 how V (·) behaves with g ′ for g = e +δ̂+g and g = eα g ′ + eγ δ̃. γ ′ −1 then • If g = e +δ̂+g eγ

V (g ′ , δ, ε, α) =

1 + e−γ (eγ + δ̂ + g ′ − 1)(eε − 1) . 1 + g ′ (eε − 1)

(41)

Since e−γ (eε − 1) − (eε − 1)(1 + e−γ (eγ + δ̂ − 1)(eε − 1)) = −e−γ (eε − 1)(eε (eγ − 1) + δ̂(eε − 1)) < 0, V (g ′ , δ, ε, α) monotonically decreases with g ′ as per Lemma B.1. Further, we have g≤

eγ + δ̂ + g ′ − 1 ≤ eα g ′ + δ̃ eγ eγ − 1 − δ̃eγ + δ̂ . g′ ≥ eα+γ − 1 γ

P P Let g = i∈S Gi and g ′ = i∈S G′i . Then, we can write the objective function as

i∈[b]\S

1 − g ′ ≤ eγ (1 − g) + δ̂

(42)

′

−1 Therefore, e +δ̂+g ≤ eα g ′ + δ̃ holds for g ′ ∈ eγ γ γ γ e −1−δ̃e +δ̂ δ̃eγ +δ̂ ′ [ eα+γ −1 , 1] and g = max{0, e −1− } maximizes V . eα+γ −1 • If g = eα g ′ + δ̃ then

V (g ′ , δ, ε, α) =

1 + (eα g ′ + δ̃)(eε − 1) . 1 + g ′ (eε − 1)

(43)

Since eα (eε − 1) − (eε − 1)(1 + δ̃(eε − 1)) = (eε − 1)(eα − 1 − δ̃(eε −1)), from Lemma B.1, we know that V (·) monotonically increases with g ′ if eα − 1 − δ̃(eε − 1) ≥ 0. Otherwise V (·) monotonically decreases with g ′ . Further, we have eγ + δ̂ + g ′ − 1 eγ γ e − 1 − δ̃eγ + δ̂ g′ ≤ . eα+γ − 1

(44)

′

−1 Therefore, eα g ′ + δ̃ ≤ e +δ̂+g holds for g ′ ∈ eγ γ γ δ̃e +δ̂ [0, e −1− ]. If eα −1−δ̃(eε −1) < 0, then g ′ = 0 gives the eα+γ −1 δ̃ eγ −1−δ̃eγ +δ̂ maximum V . Otherwise g ′ = min{ 1− } gives eα , eα+γ −1 1−δ̃ ′ the maximum V , as g = 1 when g = eα . γ ′ −1 become upper bounds Interestingly, eα g ′ + δ̃ and e +δ̂+g eγ for g in the mutually exclusive g ′ range. γ δ̃eγ +δ̂ 1) If g ′ ∈ [0, e −1− ] then g = eα g ′ + δ̃. eα+γ −1 γ

′

γ

γ

−1 δ̃e +δ̂ 2) If g ′ ∈ [ e −1− , 1] then g = e +δ̂+g . eα+γ −1 eγ γ

′

γ

γ

−1 δ̃e +δ̂ Furthermore, eα g ′ + δ̃ = e +δ̂+g at g ′ = e −1− . eγ eα+γ −1 ⋆ Therefore, we can compute V based on the value of eγ −1−δ̃eγ +δ̂ under three cases. eα+γ −1 eγ −1−δ̃eγ +δ̂ Case 1 - ( eα+γ −1 ≤ 0) Since g ′ ≥ 0, the feasible upper ′

γ

γ

γ

−1 δ̃e +δ̂ bound is g = e +δ̂+g . Therefore, if e −1− ≤ 0 then eγ eα+γ −1 ′ g = 0 gives the maximum V (·) as

V ⋆ = 1 + e−γ (eγ + δ̂ − 1)(eε − 1). γ

(45)

γ

δ̃ δ̃e +δ̂ α ε ≤ 1− Case 2 - (0 < e −1− eα+γ −1 eα ) When e − 1 − δ̃(e − γ

′

−1 1) ≥ 0 both g = eα g ′ + δ̃ and g = e +δ̂+g have the same eγ γ ′ γ γ −1 e −1−δ̃e +δ̂ α ′ ′ . maximum V (·) at g = eα+γ −1 as e g + δ̃ = e +δ̂+g eγ α ε If e − 1 − δ̃(e − 1) < 0 then the maximum V (·) of g = eα g ′ + δ̃ is 1 + δ̃(eε − 1) which is larger than the maximum γ ′ −1 V (·) given by g = e +δ̂+g . Therefore, eγ  1 + δ̃(eε − 1); if eα − 1 − δ̃(eε − 1) < 0, V ⋆ = eα+γ+ε −eα (−1+δ̂)+eα+ε (−1+δ̂)+δ̃−eε δ̃−1  −δ̂+eε −1+δ̂−eγ (−1+δ̃) +eγ −1+eα +δ̃ ; Otherwise. ( ) ( ) (46) δ̃ eγ −1−δ̃eγ +δ̂ Case 3 - ( 1− ) Here, both g = eα g ′ + δ̃ eα < eα+γ −1 γ

′

−1 δ̃ and g = e +δ̂+g become > 1 when g ′ > 1− eγ eα . However, we know that max g = 1. Therefore, g = eα g ′ + δ̃ gives more tight upper bound for g for this case. Therefore, ( 1 + δ̃(eε − 1); if eα − 1 − δ̃(eε − 1) < 0, ⋆ V = (47) eε+α ; Otherwise. eα +(1−δ̃)(eε −1)

2) Optimality of V ⋆ : Next, let us evaluate the optimality of V ⋆ . Interestingly, each of the above cases has attainable G and G′ . For example, consider the case eγ − 1 − δ̃eγ + δ̂ ≤ 0. eα+γ − 1 In this scenario, we select G′i for all i ∈ [b] \ S as G′i = eγ Gi + δ̂i ,

X

Gi =

i∈S

g ≤ eα g ′ + δ̃ ≤

γ

P P such that i∈[b]\S G′i = 1 and i∈S G′i = 0. Accordingly, for all i ∈ S, we set Gi ≤ δ̃i to ensure eγ + δ̂ − 1 eγ

and

X i∈[b]\S

Gi =

1 − δ̂ . eγ

Since these assignments satisfy the constraints in (36), there exists at least one feasible pair (Gi , G′i ) for all i ∈ [b]. Substituting these values yields F (·) = V ⋆ . A similar construction shows that feasible (Gi , G′i ) exist for γ δ̃eγ +δ̂ δ̃ 1−δ̃ the remaining two cases: 0 < e −1− ≤ 1− eα+γ −1 eα and eα < eγ −1−δ̃eγ +δ̂ ⋆ . Therefore, V serves as an attainable upper eα+γ −1 bound for F (·), and there exist feasible vectors G and G′ such that F (·) = V ⋆ . Hence, V ⋆ is the optimal value of the problem in (36). B. Variable S As we defined δ̃ and δ̂ in (10), we have δ˜i > 0 =⇒ ˆ δi = 0 and δˆi > 0 =⇒ δ˜i = 0 for all i ∈ [b]. Next, let us consider the variable S scenario. Here, we need to obtain the maximum V (·) for all S ⊆ [b]. Note that, only δ̃ and δ̂ depends on S. Since V (·) is monotonically increases with δ̃ and δ̂ as stated in Corollary E.1. Therefore, V (·) P the maximum P is given by any subset S ⊆ [b] when i∈S δ̃ = i∈[b] δ̃ and P P δ̂. Therefore, at the maximum of V (·), i∈[b]\S δ̂ = P i∈[b] P we have δ̃ = i∈[b] δ̃i and δ̂ = i∈[b] δ̂i . For the simplicity let us take a single parameter δ instead of two parameters δ̂ and δ̃ such that δ = max{δ̂, δ̃}. This δ holds the constraints in (35). Furthermore, this simplifies the optimal results as Case 1 and Case 3 are not feasible. (eγ − 1)(1 − δ) eγ − 1 − δ̃eγ + δ̂ = ≥ 0, α+γ e −1 eα+γ − 1 1 − δ̃ eγ − 1 − δ̃eγ + δ̂ δ̂ = δ̃ = δ =⇒ − α e eα+γ − 1 α (e − 1)(1 − δ) = α α+γ ≥ 0. e (e − 1) δ̂ = δ̃ = δ =⇒

Therefore, the maximum of V (·) (i.e., CPL(α, γ, δ)) is given by (
ln 1 + δ(eε − 1) ; if eα − 1 − δ(eε  − 1) < 0, CPL = eα +δ−eα δ−δeε +eα+ε (−1+eγ +δ)−1 ln δ(eε −1)−eε +eγ (−1+eα +δ+eε −δeε ) ; otherwise. (48) In addition, CPL(α, γ, δ) can be characterised as CPL(α, γ, δ) =

1 + (eα g ′ + δ)(eε − 1) . 1 + g ′ (eε − 1)

(49)

This result is used to prove Proposition F.1 in Section F. This completes the proof of Theorem IV.3. Corollary E.1. V ⋆ monotonically increases with both δ̃ and δ̂. Proof. First, we analyze how V ⋆ behaves in each case. Case 1: Here, V ⋆ monotonically increases with δ̂ and does not vary with δ̃.

Case 2: Here, if eα −1− δ̃(eε −1) < 0 then V ⋆ monotonically increases with δ̃ and does not vary with δ̂ as V ⋆ = 1+δ̃(eε −1). If eα −1− δ̃(eε −1) ≥ 0 then V ⋆ monotonically increases with δ̃ according to Lemma B.1 as (−1+eα+γ )(eε −1)(eε (eγ −1)+ δ̂(eε − 1)) ≥ 0. Similarly, we can show that V ⋆ monotonically increases with δ̂. Case 3: Similar to Case 2, if eα − 1 − δ̃(eε − 1) < 0 then V ⋆ monotonically increases with δ̃ and does not vary with δ̂. If eα − 1 − δ̃(eε − 1) ≥ 0 then V ⋆ monotonically increases with δ̃ and does not vary with δ̂. Therefore, in each case, V ⋆ monotonically increases with δ̂ and δ̃. Next, let us consider the transition between cases due to increasing the δ̂ or δ̃. It can be easily proved that V ⋆ is continuous between each case over δ̃ and δ̂. Therefore, V ⋆ monotonically increases with both δ̃ and δ̂. This completes the proof of Corollary E.1. A PPENDIX F P ROOF OF T HEOREM IV.4

α

ε

g+δ)(e −1) Lemma F.2. Let 1+(e1+g(e , where α > 0, ε > 0, 0 ≤ ε −1) α ε g ≤ 1. If e − 1 − δ(e − 1) ≥ 0, then f (g) is monotonically non-decreasing in g.

Proof. From Lemma B.1, the function f (g) is monotonically
increasing with g when (eε − 1) eα − δ(eε − 1) − 1 ≥ 0. Therefore, if eα −1−δ(eε −1) ≥ 0, then f (g) is monotonically non-decreasing in g. This completes the proof of Lemma F.2. ε0

A−δ+B(−1+δ−e δ) Proposition F.3. Let g0′ = −1+A−Ae ε0 +eα (1+B(−1+eε0 )) and ε1

A−δ+B(−1+δ−e δ) g1′ = −1+A−Ae ε1 +eα (1+B(−1+eε1 )) where, 0 < A, B < 1, 0 < ε0 < ε1 . Then, g0′ ≥ g1′ .

Proof. Let us consider g0′ − g1′ , A − δ + B(−1 + δ − eε0 δ) − −1 + A − Aeε0 + eα (1 + B(−1 + eε0 )) = A − δ + B(−1 + δ − eε1 δ) −1 + A − Aeε1 + eα (1 + B(−1 + eε1 )) (A − δ + B(−1 + δ − eε0 δ))ω1 − ω0 ω1 = (A − δ + B(−1 + δ − eε1 δ))ω0 ω0 ω1 Here, ω0 = 1 + A(eε0 − 1) + eα (B − Beε0 − 1), and

Proof. First, we prove the calibrated level e−β . According to Thm. IV.3, Computed CPL does not depends on γ when eα − 1 − δ(eε − 1) < 0. Therefore, we do not need a calibrated β for this case as β is a replacement for γ. From Theorem IV.3, we can compute CPL when eα − 1 − δ(eε − 1) ≥ 0 with,  α  e + δ − eα δ − δeε + eα+ε (−1 + eγ + δ) − 1 = ln . δ(eε − 1) − eε + eγ (−1 + eα + δ + eε − δeε ) ω1 = 1 + A(eε1 − 1) + eα (B − Beε1 − 1). (50) (B − A)(eε1 − eε0 )(A − Beα − δ) Let e−β be the updated lower bound by calibrating at = ω0 ω1 privacy budget ε0 and let l be CPL⋆ at privacy budget ε0 . Since, (B − A) ≤ 0, (eε1 − eε0 ) > 0, (A − Beα − δ) ≤ 0, eα +δ−eα δ−δeε0 +eα+ε0 (−1+eβ +δ)−1 Then we have l = ln δ(eε0 −1)−eε0 +eβ (−1+eα +δ+eε0 −δeε0 ) . g0′ − g1′ ≥ 0. Therefore,
This completes the proof of Proposition F.3. eα + δ + el δ − eα δ − eε0 (el − eα )(−1 + δ) + δ − 1
β = ln . −eε0 eα + el (−1 + δ) + el (−1 + eα + δ) Next, let us move to the proof that the estimated CPL of (51) (α, β, δ) method is an upper bound for the CPL⋆ for ε > ε . 0 Next, we prove that the estimated CPL of (α, β, δ) method is 1+(eα g0′ +δ)(eε −1) 1+(eα g1′ +δ)(eε −1) Let CPL0 = and CPL1 = ′ (eε −1) ′ (eε −1) ⋆ 1+g 1+g 0 1 an upper bound for the CPL for ε > ε0 . To prove this, we first be two estimated CPLs at ε that are calibrated at privacy establish the following intermediate results: Proposition F.1, budgets ε0 and ε1 , respectively using (49). Let A0 , B0 and Lemma F.2 and Proposition C.1. A1 , B1 be the sum of selected elements of G, G′ respectively Proposition F.1. Estimated CPL (calibrated atε privacy budget at ε0 and ε1 by Algorithm 3. Moreover, we know that the α ′ −1) ε0 ) can be characterised using ln 1+(e1+gg ′+δ)(e . Here, g ′ = Algorithm 3 selects elements of G, G′ in a discrete manner ε (e −1) A−δ+B(−1+δ−eε0 δ) over privacy budget ε. For example, suppose A, B are the −1+A−Aeε0 +eα (1+B(−1+eε0 )) , and A, B are sum of selected selected G, G′ respectively at ε′ . Then, A, B would not change ′ elements of G and G respectively by the Algorithm 3 at ε0 . for a range around ε′ , which we call a segment. Therefore, the Proof. From (49), we ε can compute the estimated CPL as previously considered A0 , B0 and A1 , B1 can be vary based on α ′ −1) their segments. We can analyze them in three different cases. . CPL = ln 1+(e1+gg ′+δ)(e (eε −1) ⋆ Case 1 (within same segment, i.e., Let l be CPL at privacy budget ε0 . Here, A, B are = A1 and B0 = B1 ) εAccording to sum of selected elements of G and G′ respectivelyε by the A0 A0 −δ+B0 (−1+δ−e 0 δ) 0 ′ Algorithm 3 at ε0 . Then we have, l = ln 1+A(eε0 −1) = Prop. F.1, g0 = −1+A0 −A0 eε0 +eα (1+B0 (−1+eε0 )) and α ′

ε0

1+B(e

−1)

−1) ln 1+(e1+gg ′+δ)(e . Therefore, (eε0 −1)

g′ =

A − δ + B(−1 + δ − eε0 δ) . −1 + A − Aeε0 + eα (1 + B(−1 + eε0 ))

This completes the proof of Theorem IV.4.

(52)

ε1

δ) 1 −δ+B1 (−1+δ−e g1′ = −1+A1A−A . From Prop. F.3, we ε ε α 1 e 1 +e (1+B1 (−1+e 1 )) ′ ′ have g0 > g1 as ε0 ≤ ε1 . Therefore, from Lemma F.2, the estimated CPL by calibrated parameters at ε0 is an upper bound for the CPL by calibrated parameters at ε1 . Therefore, the estimated CPL by calibrated parameters at ε0 is an upper bound for CPL⋆ within the same segment.

Case 2 - (between neighboring segments, i.e., A0 < A1 and B0 ≤ B1 ) Let us take CPL2 be estimated CPL at ε2 which is calibrated at ε2 . Here, ε2 is selected such that the two segments join each other. From previous case 1, CPL0 ≥ CPL2 and CPL2 ≥ CPL1 . Therefore, CPL0 ≥ CPL1 . Case 3 - (between any two segments ε > ε0 ) Using Case 1 and Case 2, we have CPL0 ≥ CPL1 for any two segments. Therefore, estimated CPL by calibrated parameters at ε0 provides an upper bound for CPL⋆ for privacy budgets ε > ε0 . This completes the proof of Theorem F.

ln

Theorem

β

F,

−1+eα +δ+el δ−eα δ−eε0 el −eα )(−1+δ)+δ

−eε0 eα +el (−1+δ) +el (−1+eα +δ)

=

.

Since

at ε0 can be computed as l = we can write β in terms of A and B as λ1 +λ2 β = ln eε0 (Beα +A(−1+δ))−(−1+A)(−1+e Here, α +δ) . α ε0 λ1 = −1 + e + Ae (−1 + δ) + B(−1 + eα )(−1 + δ), λ2 = 2δ − Aδ − eα δ + Beε0 (eα + δ − eα δ) and A, B are selected elements from G, G′ respectively by the Algorithm 3 at privacy budget ε0 . Then, 1 + Ã − B̃ + eα (−1 + δ) − 2δ . lim β = ln ε0 →0 1 + (−1 + Ã − B̃)eα − δ P P Here, Ã = i∈[b], Gi >1, Gi and B̃ = i∈[b], Gi >1, G′i .

(53)

G′ i

Furthermore, we know that γ G′i

≥

a1 b1 − a2 b2 = eα+ε (δ(eε − 1) − eε ) − (−1 + eα + δ + eε − δeε )λ Here, λ = (eα + δ − eα δ − δeε + eα+ε (−1 + δ) − 1) Since a1 b1 − a2 b2 ≥ 0, CPL is monotonically increasing with γ. This completes the proof of Corollary IV.7.

CPL⋆

1+A(eε0 −1) ln 1+B(e ε0 −1) ,

G′ i

Proof. From (12), CPL(α, γ, δ) does not depends on γ when eα − 1 − δ(eε − 1) < 0. When eα − 1 − δ(eε − 1) ≥ 0, let us check the monotonicity by evaluating a1 b1 − a2 b2 . Here, we remove ln(x) as it is a monotonically increasing function with x.

= −(eα − 1) (eε − 1) (δ − 1) (eα + δ − eε δ − 1) ≥ 0.

A PPENDIX G P ROOF OF C OROLLARY IV.5 Proof. From

A PPENDIX I P ROOF OF C OROLLARY IV.7

B̃ as γ ln 1− 1−Ã

=

ln supi∈[b], Gi ̸=0 Gi from (11). Next, let us evaluate 1 + à − B̃ + eα (−1 + δ) − 2δ 1 − B̃ − 1 + (−1 + à − B̃)eα − δ 1 − à ÃB̃ − Ã2 − δ + 2ÃB̃ − δ B̃ + eα ((à − B̃)B̃ + δ − Ãδ) = (1 + (−1 + à − B̃)eα − δ)(1 − Ã) (à − B̃)(B̃eα + δ − Ã) + δ(1 − Ã)(eα − 1) = (1 + (−1 + à − B̃)eα − δ)(1 − Ã) Since 0 ≤ B̃ ≤ à < 1 and à ≤ eα B̃ + δ, =

≤0 Therefore,

A PPENDIX J P ROOF OF T HEOREM IV.8 We use Corollary J.1 to prove Theorem IV.8. Corollary J.1. Let (α1 , β1 , δ1 ) and (α2 , β2 , δ2 ) be two characterisations for the Dependency budget. Then, (α, β, δ) gives an upper bound for both characterisations. Here, α = max{α1 , α2 }, β = max{β1 , β2 }, and δ = max{δ1 , δ2 }. Proof. It can be easily proved that the estimated CPL given by Corollary IV.6 monotonically increases with α, β, and δ using Lemma B.1. Proof. From Corollary J.1, we need to compute the maximum values of α and δ for all possible distributions within the uncertainty. Let α̂ and δ̂ be the updated values of α and δ, respectively. Compute α̂. Since we consider a ∆ uncertainty between known distribution (i.e., PK ) and actual distribution (i.e., PA ), |pA (a|x) − pK (a|x)| ≤ ∆a,x for all a ∈ X̂ , x ∈ Xk , where ∆a,x ∈ ∆, pA (·|·) ∈ PA , pK (·|·) ∈ PK . Therefore, updated α̂ should be the maximum of all possible α which is given by,   min{1, p(a|x) + ∆a,x } α̂ = max . p(a|x′ ) − ∆a,x′ a∈X̂ ,x,x′ ∈Xk ,p(a|x′ )−∆a,x′ >0 (55) Compute δ̂. Similarly the maximum δ can be computed as X δ̂ = max p(a|x) + ∆a,x . (56) ′ x,x ∈Xk

lim β ≤ γ.

ε0 →0

(54)

This completes the proof of Corollary IV.5. A PPENDIX H P ROOF OF T HEOREM IV.6 Proof. As per Theorem IV.4, the calibrated parameter β holds the privacy guarantee of the estimated CPL. Therefore, we can compute the estimated CPL of the (α, β, δ) method in the same way as in Theorem IV.3.

a∈X̂ , p(a|x′ )−∆a,x′ ≤0

Compute β̂. From Corollary IV.5, β̂ can be computed for given distribution by, β̂ = ln

1 + A − B + eα̂ (−1 + δ̂) − 2δ̂ 1 + (−1 + A − B)eα̂ − δ̂

.

(57)

Since β̂ is monotonically increasing with A − B (can be proved using Lemma B.1 similar to the proof I), we need to find the maximum A − B for all possible distributions within the uncertainty to compute β̂. We can formulate this as

(a)

(b)

(c)

Fig. 11: Empirically validate the space and time complexities of DT. Here, space is measured with the Python object allocated to store the values.

privacy/utility compared to the rest. Since LXi →Xk is a nonconvex function, this is a non-convex optimization problem. In our experiments, we use a standard gradient descent algorithm to solve this optimization problem with (59) loss function (differentiable). 2  ∀i ∈ [b], X X εk + LXi →Xk − ε̃ . (59) Loss =

a relaxed linear program, which provides a polynomial-time upper bound to the exact MILP formulation. X maximize zi ′ Z,G,G

subject to

zi ∈Z, i∈[b]

Mi+ (Gi − G′i + Mi− ); Mi+ + Mi− L ≤ G ≤ U, 1⊤ G = 1, 0 ≤ zi ≤

′

′

′

L ≤G ≤U ,

⊤

k∈[n]

′

1 G = 1. (58)

Here, Mi+ = max{0, Ui − P L′i }, Mi− = max{0, Ui′ − ′ Li }, ∀i ∈ [b], and maxG,G i∈[b] zi gives the maximum A − B for all possible distributions within the uncertainty. We can compute the solution using standard LP algorithms such as the simplex method, the interior point method, etc. Therefore, from Theorem J.1, α̂, β̂, δ̂ estimates an upper bound for CPL⋆ for any privacy budget level. This completes the proof of Theorem IV.8.

i∈[n]\{k}

A PPENDIX L E XPERIMENTAL R ESULTS FOR T IME AND S PACE A NALYSIS To validate the space and time complexity analysis, we empirically compute the time and space with varying the alphabet size as shown in Figure 11a–c. Here, we use a logarithmic scale on the time and space axes to validate polynomialtime/space and constant-time/space complexities. Empirical results validate the computational and space efficiency of DT compared to other algorithms.

A PPENDIX K P RIVACY B UDGET C ALIBRATION We model the privacy budget calibration as a maximization problem as minimize

Loss

subject to εk +

X

LXi →Xk ≤ ε̃;

∀k ∈ [n],

i∈[n]\{k}

ε̃ ; ∀k ∈ [n]. n Here, εk is the privacy budget of the Xk attribute and ε̃ n is the value of the basic privacy budget splitting (SPL) algorithm. Since SPL is assigning privacy budgets assuming perfect correlation, we can always find a better or equal privacy budget for each attribute. Note that the loss function is a flexible choice based on the requirements. For example, we use (59). Here, intuitively, we need to minimize the difference between the target overall privacy and the privacy leakage of each attribute. Someone can define a different loss function by assigning weights for some attributes that are significant in εk ≥

Fig. 12: Normalized over estimation and under estimation of estimated CPL of DT and LTM with respect to ground truth CPL⋆ . Here, DT does not incorporate uncertainty. A PPENDIX M E XPERIMENTAL R ESULTS FOR D ISTRIBUTION U NCERTAINTY D EFINING M ETHODS Statistically defined uncertainty. We begin by evaluating the four statistical methods introduced in Section VI-A5, outlining their respective strengths and limitations. To ground

(a) Range

(b) Standard deviation

(c) Variance

(d) MAD

Fig. 13: Normalized overestimation and underestimation of estimated CPL with respect to ground truth CPL⋆ for different uncertainty methods.

the analysis, we consider the motivational example: a statewise household income survey in the United States conducted under LDP, which is explained in Section I. To instantiate this setup, we use the real-world SPM dataset [28]. We evaluate the normalized underestimation and overestimation of estimated ˜ relative to the groundCPL (based on prior knowledge, CPL) truth CPL (based on actual distributional knowledge, CPL⋆ ). 1 ˜ 0}, max{CPL⋆ − CPL, ε 1 ˜ − CPL⋆ , 0}. Normalized Overestimation = max{CPL ε

Normalized Underestimation =

Next, we plot all the attributes on an x-y graph using overestimation on the y-axis and underestimation on the x-axis. We first evaluate DT without incorporating distributional uncertainty, using LTM as a baseline, as shown in Figure 12. Each point in the plot corresponds to the normalized error of a given attribute across states, excluding those used as prior knowledge. The results indicate that both DT and LTM yield a considerable number of underestimated attributes. Next, we incorporate uncertainty into DT, as shown in Figure 13. In this figure, the red crosses denote average estimation. Points farther from the x = 0 axis indicate an underestimation of CPL relative to the ground truth, which may introduce privacy vulnerabilities. Conversely, points farther from the y = 0 axis represent overestimation of CPL, which reduces data utility. Since our goal is to ensure strong privacy protection while preserving utility, the ideal outcome is to keep points as close as possible to both the x = 0 axis (minimizing potential privacy vulnerabilities from underestimation) and the origin (increasing data utility). The results show that CPL estimated using range- and standard deviation-based uncertainty estimates exhibits less underestimation than variance- and MAD-based methods. This implies that range- and std-based uncertainty definitions provide stronger privacy guarantees. We further analyze the impact of prior knowledge by varying the set of prior states. Here, we observe that range-based uncertainty is highly sensitive to the choice of prior knowledge, while std-based uncertainty demonstrates more stable behavior.

Naively defined uncertainty. In this setting, we use the publicly available LFW dataset to learn correlations between facial attributes, which are then used to estimate CPL for the CelebA dataset. Since only a single source is available to infer correlations, we adopt a naive method to define uncertainty. Specifically, we vary the error parameter e across 10%, 15%, 20%, 30%. We observe that values of 10% ≤ e ≤ 20% yield a better balance between utility and privacy. To further validate this observation, we repeat the experiment on additional datasets by using 20% of the data to learn the distributions and the remainder for testing. The results consistently confirm that 10% ≤ e ≤ 20% achieves the most favorable trade-off between utility and privacy. A PPENDIX N ATTRIBUTE I NFERENCE ATTACKS TabTransformer attacker. We model a strong learned adversary using TabTransformer, which embeds each released categorical attribute as a token and applies a Transformer encoder to capture cross-attribute interactions, followed by a multi-class softmax head for predicting Xj [45]. We train a separate attacker gj for each target attribute using auxiliary pairs (Ỹ−j , Xj ) and report the attribute-averaged Macro-F1 via AIA. We train for 10 epochs and select a batch size of 16384. Macro-F1. Macro-F1 is the unweighted mean of the per-class F1 scores (one-vs-rest), giving equal weight to each class 1 X 2Pc Rc MacroF1 = . |C| Pc + R c c∈C

Here, PC and RC are the precision and recall for class C.

Related documents

• Advances in Information-Theoretic Differential Privacy: Composition and Calibration#273820
• The Fast Mixing Mechanism for Differential Privacy#652332
• The Fast Mixing Mechanism for Differential Privacy#650879
• A Federated Generalized Linear Model for Privacy-Preserving Analysis#404552
• Cross-Silo De-Anonymization Under Local Differential Privacy: Threat Model, Phase Transition, and Coordination Necessity#280099