Multi-tier Differential Private Query Release Shaowei Wang, Jinn Li, Yun Peng
arXiv:2606.15543v1 [cs.CR] 14 Jun 2026
Guangzhou University Guangzhou, China [email protected]
Puning Zhao, Wenqi Ren Sun Yat-sen University Shenzhen, China
Changyu Dong, Jin Li, Jian Weng Guangzhou University Guangzhou, China
Abstract
1
Answering statistical queries over sensitive data under differential privacy (DP) is a common task in many settings, including databases, mobile computing, and data markets. In these scenarios, multiple analysts may issue the same query, while receiving answers generated under different privacy budgets due to differences in trust levels or willingness to pay. Existing approaches for such multi-tier DP queries either incur excessive cumulative privacy loss or suffer from suboptimal utility. In this paper, we propose a framework for multi-tier DP query release that simultaneously bound the cumulative privacy loss by the maximum privacy budget among all queries and achieve optimal utility comparable to that of singletier mechanisms. Our framework applies to different classes of DP mechanisms. For noise-adding mechanisms (e.g., count queries with the two-sided Geometric mechanism in the curator model), we develop a general solution based on the characteristic functions of noise distributions. For other mechanisms (e.g., count queries under the local DP model with the Subset mechanism), we design mechanism-specific primitives for budget transformation and introduce a template-based strategy that attains optimal utility across different privacy regimes. Experimental results demonstrate the effectiveness of our framework.
Collecting and analyzing user data benefits a wide range of domains, from healthcare services to mobile computing. However, because user data in these domains often contains sensitive personal information, preserving data privacy is essential. Differential privacy (DP) [12] has emerged as a de facto standard for privacy protection and is widely adopted in real-world industrial systems. For example, Google [40] and LinkedIn [28] use DP for analytical queries in data warehouses, while Apple [18], Google [20], and Microsoft [10] apply DP on the user side to collect mobile service usage data. In many DP systems, multiple parties may issue the same query, often with varying privacy budgets and utility targets. For example:
CCS Concepts • Security and privacy → Privacy protections; Privacy-preserving protocols.
Keywords differential privacy, local differential privacy ACM Reference Format: Shaowei Wang, Jinn Li,, Yun Peng, Puning Zhao, Wenqi Ren, and Changyu Dong, Jin Li,, Jian Weng. 2018. Multi-tier Differential Private Query Release. In Proceedings of Make sure to enter the correct conference title from your rights confirmation email (Conference acronym ’XX). ACM, New York, NY, USA, 18 pages. https://doi.org/XXXXXXX.XXXXXXX
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. Conference acronym ’XX, Woodstock, NY © 2018 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-XXXX-X/2018/06 https://doi.org/XXXXXXX.XXXXXXX
Introduction
• Multi-analyst data warehouses. Different analysts within a data warehouse may query the same statistics, such as a user population histogram, with varying levels of trust and DP budgets. For example, LinkedIn’s Audience Engagement API platform [28] reports that internal analysts (such as for dashboards, anomaly detection, and A/B testing) and external analysts (e.g., those asking profile statistics) are allocated different privacy budgets. • Multi-target mobile services. Mobile devices often run multiple Apps and services concurrently, many of which rely on user demographic information and usage data, albeit with varying levels of accuracy (e.g., with different local DP noises). For example, Google uses DP-protected keyboard typing data for both nextword prediction modeling [19] and out-of-vocabulary (OOV) word discovery [20]; personalized services (e.g., Apple Maps) typically require relatively accurate user information to deliver high-quality experiences, whereas aggregate analytics services (e.g., Apple and Google’s epidemic exposure notification [4]) may operate effectively with only approximate information. • Multi-buyer data markets. In data markets [3, 5], data owners provide access to sensitive datasets to multiple buyers with different monetary budgets and accuracy requirements. Different buyers may purchase the same data asset (e.g., individual records or precomputed statistics) at varying levels of precision (e.g., controlled by DP noise) depending on their willingness to pay. This practice is known as data versioning [39] in data markets. A straightforward approach to handling these multi-tier DP queries is to independently invoke a base DP mechanism for each recipient 𝑖 ∈ [𝑚] with privacy budget 𝜖𝑖 , to obtain the result 𝑟𝑖 . We call this independent release approach. However, it leads to substanÍ tial cumulative privacy loss for the data owner (typically 𝑖 ∈ [𝑚] 𝜖𝑖 ), as the recipients may collude. Specifically, multiple analysts in a data warehouse or multiple buyers in a data market could share and fuse their results to obtain a more accurate version that surpasses each individual privacy level; multiple mobile services (e.g., those
Conference acronym ’XX, June 03–05, 2018, Woodstock, NY
Multi-analyst Data Warehouses
Wang et al.
Multi-target mobile services
Multi-buyer Data Markets High Price Buyer 1
Maps
Medium Price Buyer 2
Internal Analysts
External Analysts
Personalized Information
Epidemic Exposure
Aggregation Analytics
Data Owner
Low Price Buyer 3
Figure 1: Application scenarios of multi-tier differentially private queries. from the same parent company) could ensemble several sanitized user reports to achieve an unexpected precision. Another approach is to release the responses gradually by invoking a base DP mechanism for each recipient 𝑖 ∈ [𝑚] with privacy budget 𝜖𝑖 − 𝜖𝑖+1 to obtain 𝑟𝑖′ , assuming that party 𝑖 + 1 has a lower budget than party 𝑖 (i.e. 𝜖𝑖+1 < 𝜖𝑖 ) and already receives 𝑟𝑖+1 . The result 𝑟𝑖 for the 𝑖-th recipient can then be obtained by combining 𝑟𝑖′ and 𝑟𝑖+1 (e.g., via weighted average). As a consequence, the cumulative privacy loss would be 𝜖1 (i.e., the largest budget among all recipients). We call this the gradual release approach. However, combining two or more DP results with split budgets often results in suboptimal utility. For example, averaging 𝑚 results, each of which is (𝜖/𝑚)-DP with the Laplace mechanism [12] under query sensitivity 1, yields a variance of 2𝑚/𝜖 2 , whereas directly invoking an 𝜖-DP Laplace mechanism gives a variance of 2/𝜖 2 . Ideally, solutions for multi-tier DP queries should simultaneously achieve the following two objectives: • Privacy objective. From the data owner’s perspective, the cumulative privacy loss should be bounded by max𝑖 ∈ [𝑚] 𝜖𝑖 . More generally, for any colluding set of parties 𝑆 ⊆ [𝑚], the joint output {𝑟𝑖 }𝑖 ∈𝑆 should satisfy (max𝑖 ∈𝑆 𝜖𝑖 )-DP. • Utility objective. From the recipients’ perspective, the utility of each received result 𝑟𝑖 should (closely) match the optimal/best utility achievable under 𝜖𝑖 -DP. Clearly, the independent release approach fails to achieve the desired privacy goal, whereas the gradual release approach satisfies the privacy objective but often incurs substantial utility loss. Several attempts have been made to address multi-tier DP queries. Specifically, for DP queries with Gaussian mechanism, because Gaussian noises are closed under linear operations, one can gradually add Gaussian noises to transform a low-privacy result into a high-privacy result [41]. For queries with Laplace mechanism, the work of [22] also designed a gradual noise addition rule. In the local DP setting, the randomized response mechanism [21, 34] has simple re-sampling rules to transform a low-privacy result into a high-privacy result [36]. Nevertheless, these classical base DP mechanisms are known to be suboptimal. For example, in the high-privacy regime, the Laplace mechanism exhibits an exponential error gap compared to the two-sided Geometric mechanism [16]; meanwhile, the binary randomized response [34] and the general randomized response [21] perform significantly worse than the Subset mechanism [31] in the high-privacy and low-privacy
regimes, respectively. In multi-recipient scenarios, the target privacy levels {𝜖𝑖 }𝑖 ∈ [𝑚] can span from low regimes (e.g., 𝜖 > 1) to high regimes (e.g., 𝜖 < 1), making these approaches inherently incapable of achieving the utility objective. Designing DP mechanisms for multi-tier queries that achieve optimal utility remains a fundamental challenge: • Some state-of-the-art DP noise-adding mechanisms, such as the two-sided Geometric mechanism [16] and the discrete Gaussian mechanism [9], operate in the non-smooth discrete domain (to improve utility and avoid floating-point attacks [26]). This makes the existence of outputting rules (e.g., via Markov gradual noise adding [22] for low-to-high privacy transformation) that satisfy the privacy objective of the joint output {𝑟𝑖 }𝑖 ∈𝑆 difficult to verify, let alone the concrete design of transformation strategies. • Other DP mechanisms that do not rely on explicit noise addition, such as the Subset mechanism [31] (used in Google Gboard’s OOV discovery [20]) and local hash mechanism [33], employ a general probabilistic mapping between the input and output domains, where the output domain differs from the input domain and varies with the privacy budget 𝜖. This variation renders privacy adaptation considerably difficult. In this work, we propose new approaches to achieve both goals for the above multi-tier differentially private query release problem. Concretely, for noise-adding DP mechanisms (e.g., the two-sided Geometric mechanism), we propose a characteristic function-based framework to check the existence of the privacy transformation and to seamlessly transform a low-privacy result into a high-privacy result (if such a transformation exists), and derive concrete residual noises for the transformation. For other DP mechanisms (e.g., the Subset mechanism in the local DP), we propose a template-based method, which first generates several template results using reference privacy budgets with mechanism-specific operators, and then finds the closest template for each target budget 𝜖𝑖 . Through theoretical analyses, we ensure that these methods provide exactly/approximately optimal results for all possible budgets on count queries in the curator and local DP settings, respectively. The contributions of this work are as follows: • Multi-tier noise-adding DP framework. For noise-adding DP mechanisms, we propose a framework that transforms a lowprivacy output into a stricter one by adding extra noise, determined by the characteristic function of the noise distributions. We instantiate it for optimal count query mechanisms.
Multi-tier Differential Private Query Release
Additionally, we demonstrate non-existence of such transformations for the discrete Gaussian mechanism. • Multi-tier mapping-based DP Method. For mapping-based DP mechanisms (e.g., the Subset/local hash mechanism), we present a template-based method that generates collusion-resilient tiered templates. We prove the optimality of each tier’s result for the multi-tier Subset mechanism. • Experimental evaluations. Through extensive simulations, we demonstrate the effectiveness of our proposed multi-tier frameworks and concrete mechanisms, show significant error reduction compared to existing approaches. The remainder of this paper is organized as follows. Section 2 provides preliminaries. Section 3 formalizes the multi-tier DP query problem. Section 4 presents the multi-tier framework for noise-adding mechanisms, and Section 5 develops multi-tier LDP mapping-based mechanisms. Section 6 presents evaluation results. Section 7 summarizes related works. Section 8 concludes the paper.
2
Preliminaries
Notations. We use [𝑐] to denote {1, 2, . . . , 𝑐}, and [𝑐 1, 𝑐 2 ] to denote {𝑐 1, 𝑐 1 + 1, . . . , 𝑐 2 }.
2.1
Characteristic Function
For a random variable 𝑋 , the characteristic function Φ𝑋 : R ↦→ C is defined as: Φ𝑋 (𝑡) = E[𝑒 𝑗𝑡𝑋 ], where 𝑗 is the imaginary unit and 𝑡 is the parameter of the characteristic function. It captures all moments of the distribution in a single complex-valued function. The key properties of characteristic functions are as follows: • Existence property: The characteristic function Φ𝑋 (𝑡) exists for every valid probability distribution of 𝑋 . • Bijection property: The mapping from a probability distribution to its characteristic function is bijective. A valid characteristic function Φ𝑋 uniquely determines the distribution of 𝑋 . • Summation property: For independent variables 𝑋 and 𝑌 , Φ𝑋 +𝑌 (𝑡) = Φ𝑋 (𝑡) · Φ𝑌 (𝑡). This extends to finite sums of independent random variables: Î ΦÍ𝑛𝑖=1 𝑋𝑖 (𝑡) = 𝑛𝑖=1 Φ𝑋𝑖 (𝑡). • Mixture property: For a mixture distribution where 𝑋 takes values from a family of variables 𝑋𝑖 with probabilities 𝑝𝑖 , ∑︁ Φ𝑋 (𝑡) = 𝑝𝑖 · Φ𝑋𝑖 (𝑡). 𝑖
There exist established criteria to check whether a function is a valid characteristic function and how to numerically derive the probability distribution from a characteristic function [8]. These properties of characteristic functions together will facilitate the design of the multi-tier DP noise-adding framework.
2.2
Differential Privacy
Conference acronym ’XX, June 03–05, 2018, Woodstock, NY
between 𝑃 and 𝑄 is: 𝐻𝛼 (𝑃 ∥𝑄) =
∑︁
[𝑃 (𝑣) − 𝛼𝑄 (𝑣)] + ,
𝑣∈ F
where [𝑥] + = max(𝑥, 0). Differential privacy (DP) guarantees that the output of an algorithm does not reveal too much information about any individual: Definition 2.2 ((𝜖, 𝛿)-DP). A mechanism M : X𝑛 → Y satisfies (𝜖, 𝛿)-differential privacy if, for any adjacent datasets 𝑋, 𝑋 ′ ∈ X𝑛 that differ by at most one record, the following holds: 𝐻𝑒 𝜖 (M (𝑋 )∥M (𝑋 ′ )) ≤ 𝛿. This is equivalent to saying that for any 𝑆 ⊆ Y: Pr[M (𝑋 ) ∈ 𝑆] ≤ 𝑒 𝜖 Pr[M (𝑋 ′ ) ∈ 𝑆] + 𝛿. Typically, 𝛿 is restricted to a small value (e.g., 𝛿 < 𝑂 (1/𝑛)). The parameter 𝜖 determines the strength of the privacy guarantee: smaller values mean stronger privacy. The special case (𝜖, 0)-DP is often referred to as 𝜖-DP. Similarly, when each data owner applies privacy mechanisms locally, the definition of the local model of DP is as follows: Definition 2.3 (𝜖-LDP). A mechanism M : X → Y satisfies 𝜖-local differential privacy iff for all 𝑥, 𝑥 ′ ∈ X: 𝐻𝑒 𝜖 (M (𝑥)∥M (𝑥 ′ )) = 0. Data processing inequality. For 𝑓 -divergences, including the Hockey-stick divergence, a desirable property is data processing inequality. It formalizes the fundamental intuition that data processing can only reduce the distinguishability between distributions. Lemma 2.4 (Data Processing Ineqality [27]). For any Markov kernel 𝐾 and 𝑓 -divergence 𝐷: 𝐷 (𝑃 ∥𝑄) ≥ 𝐷 (𝐾 (𝑃)∥𝐾 (𝑄)). Base noise-adding mechanisms: DP is typically achieved by adding carefully calibrated noise to the output of a query. Here are some popular noise-adding mechanisms: • Laplace Mechanism: Designed for functions 𝑓 : D → R with sensitivity Δ (the maximum change in output when one record altered), this mechanism satisfies 𝜖-DP by adding noise 𝜂 following a Laplace distribution: 𝜖 −𝜖 |𝑦 |/Δ Pr[𝜂 = 𝑦] = 𝑒 , ∀𝑦 ∈ R 2Δ • Two-sided Geometric Mechanism [16]: Designed for integervalued functions 𝑓 : X𝑛 → Z with sensitivity Δ, this mechanism adds noise 𝜂 following distribution: 1 − 𝑒 −𝜖/Δ −𝜖 |𝑘 |/Δ 𝑒 , ∀𝑘 ∈ Z 1 + 𝑒 −𝜖/Δ It satisfies 𝜖-DP and is universally optimal when Δ = 1 [16]. • Discrete Gaussian Mechanism [9]: Designed for integer-valued functions 𝑓 : X𝑛 → Z, this mechanism adds noise 𝜂 drawn from the discrete Gaussian distribution 𝑁 Z (0, 𝜎 2 ): Pr[𝜂 = 𝑘] =
2
Definition 2.1 (Hockey-Stick Divergence). For distributions 𝑃, 𝑄 over domain F and 𝛼 ≥ 1, the 𝛼-Hockey-Stick divergence
Pr[𝜂 = 𝑘] = Í
2
𝑒 −𝑘 /(2𝜎 ) , − 𝑗 2 /(2𝜎 2 ) 𝑗 ∈Z 𝑒
∀𝑘 ∈ Z.
Conference acronym ’XX, June 03–05, 2018, Woodstock, NY
For any 𝜖, 𝛿 ∈ (0, 1) with 𝜖 < 1, use 𝜎 2 = 2Δ2 log(2/𝛿)/𝜖 2 ensures (𝜖, 𝛿)-DP. This mechanism is useful crypto-assisted decentralized DP noise generation. • Skellam Mechanism [2]: Designed for integer-valued functions 𝑓 : X𝑛 → Z with sensitivity Δ, this mechanism adds noise 𝜂 following the Skellam distribution: Pr[𝜂 = 𝑘] = 𝑒 −2𝜆 𝐼 |𝑘 | (2𝜆),
∀𝑘 ∈ Z,
where 𝐼 𝜈 is the modified Bessel function of the first kind. Choosing 𝜆 = Δ/(𝑒 𝜖 − 1) yields 𝜖-DP. The Skellam mechanism is particularly attractive for integer-valued queries in decentralized settings due to its infinite divisibility. Base mapping mechanisms: Besides adding noises, DP can also be realized by explicitly defining a transition/mapping probability matrix between the input and output (e.g., randomized response [21, 34], local hash [33] and Subset mechanism [31]). • Generalized Randomized Response (GRR) [21]: For categorical data 𝑥 ∈ [𝑑] with 𝜖-LDP, the output distribution is: ( 𝜖 𝑒 if 𝑦 = 𝑥; 𝜖 Pr[𝑦|𝑥] = 𝑒 +𝑑1 −1 if 𝑦 ≠ 𝑥 . 𝑒 𝜖 +𝑑 −1 • Local Hash Mechanism [33]: It maps the domain [𝑑] to a domain [𝑔] using a hash function 𝐻 : [𝑑] → [𝑔], then applies GRR over [𝑔]. The output distribution is: ( 𝜖 𝑒 if 𝑦 = 𝐻 (𝑥); 𝜖 Pr[𝑦|𝑥] = 𝑒 +𝑔−1 1 if 𝑦 ≠ 𝐻 (𝑥). 𝑒 𝜖 +𝑔−1 The hash domain size 𝑔 is typically set to ⌊𝑒 𝜖 + 1⌋. • Subset Mechanism [31, 32]: For categorical data 𝑥 ∈ [𝑑], it outputs a subset 𝑆 ⊆ [𝑑] of size 𝑘, assigns probabilities to subsets based on whether they contain the true value 𝑥: 𝑒𝜖 (𝑑 −1)𝑒 𝜖 + (𝑑 −1) if 𝑥 ∈ 𝑆; 𝑘 −1 𝑘 Pr[𝑆 |𝑥] = 1 (𝑑 −1)𝑒 𝜖 + (𝑑 −1) if 𝑥 ∉ 𝑆. 𝑘 −1 𝑘 𝑑 The subset size 𝑘 is set around 1+𝑒 𝜖 . It is optimal in all privacy regimes for discrete distribution estimation [37].
3
Problem Formulation
In this section, we define the multi-tier differentially private query release problem. Without loss of generality to both central DP and local DP (i.e., where a single user’s data constitutes the dataset), we consider a database query setting with the following components: • A dataset 𝑋 ∈ D, where D is the domain of the dataset. • A query function 𝑞 : D ↦→ Y, which maps a dataset to an output in some domain Y. • A set of analysts A = {1, 2, . . . , 𝑚}. • A list of privacy budgets 𝐿 = {𝜖1, 𝜖2, . . . , 𝜖𝑚 }, where 𝜖𝑖 > 0 is the privacy budget assigned to analyst 𝑖 ∈ A. • A mechanism M : D×R𝑚 ↦→ Y𝑚 that collectively generates 𝑚 query results 𝑅 = {𝑟 1, 𝑟 2, . . . , 𝑟𝑚 } given the input dataset and the budget list 𝐿, where 𝑟𝑖 is the result released to analyst 𝑖 with associated privacy budget 𝜖𝑖 . Privacy objectives: We require that the marginal distribution of each single result 𝑟𝑖 satisfies the 𝜖𝑖 level of DP (or LDP). Additionally, to limit the accumulated privacy loss from multiple results (e.g.,
Wang et al.
due to the aforementioned collusion scenarios), we also require that for any subset of results, the privacy loss does not exceed the maximum marginal privacy budget among the component results. We call this collusion resistance (see Definition 3.1). Definition 3.1 (Collusion-resistant Property). A multi-tier mechanism M satisfies the collusion-resistant property if for any subset 𝑆 ⊆ A of analysts, the joint distribution of M𝑆 (𝑋, 𝐿) over the coordinates in 𝑆 satisfies (max𝑖 ∈𝑆 𝜖𝑖 )-differential privacy. Because the marginal privacy budget of some 𝑟𝑖 may be looser (e.g., 𝑟𝑖 actually satisfies a DP level 𝜖𝑖′ where 𝜖𝑖′ < 𝜖𝑖 ), the joint distribution of M𝑆 (𝑋, 𝐿) in the previous collusion resistance condition could exceed max𝑖 ∈𝑆 𝜖𝑖′ . It is therefore necessary to define a stricter version of collusion resistance. Following the principle of the data processing inequality, we define the advanced collusion-resistant property (see Definition 3.2). Since the hockey-stick divergence satisfies the data processing inequality, it is easy to see that the advanced collusion-resistant property implies the basic collusionresistant property. Definition 3.2 (Advanced Collusion-resistant Property). A mechanism M satisfies the advanced collusion-resistant property if, for any subset 𝑆 ⊆ A of analysts, any adjacent datasets 𝑋, 𝑋 ′ ∈ D, and any distance measure 𝐷 that satisfies the data processing inequality, the following holds: 𝐷 (M𝑆 (𝑋, 𝐿)∥M𝑆 (𝑋 ′, 𝐿)) ≤ max 𝐷 (M {𝑖 } (𝑋, 𝐿)∥M {𝑖 } (𝑋 ′, 𝐿)). 𝑖 ∈𝑆
This definition is equivalent to the Blackwell ordering property [7]: for every subset 𝑆 ⊆ A of analysts and every pair of adjacent datasets 𝑋, 𝑋 ′ ∈ D, there exists an analyst 𝑖 ∈ 𝑆 (which may depend on 𝑆, 𝑋 , and 𝑋 ′ ) such that the joint output distribution M𝑆 (𝑋, 𝐿) is a post-processing of M {𝑖 } (𝑋, 𝐿) and, simultaneously, M𝑆 (𝑋 ′, 𝐿) is the same post-processing of M {𝑖 } (𝑋 ′, 𝐿). Utility objectives: From an honest analyst’s perspective, we require that the received result 𝑟𝑖 maintains optimal utility under the constraint of 𝜖𝑖 -DP (or LDP), up to a small constant factor. That is, each analyst 𝑖 attains utility comparable to what they would obtain from an optimal single-tier mechanism operating at privacy level 𝜖𝑖 , thereby. We formalize this approximate optimal utility requirement of the multi-tier DP query system as the utility-match property (see Definition 3.3). Definition 3.3 (𝛼-Utility-Match Property). Given an error measure Error : Y × Y ↦→ R, a positive constant 𝛼 ∈ R ≥1 , and a multi-tier mechanism M, we say that M satisfies the 𝛼-utility-match property if, for any privacy budget 𝜖 ′ ∈ R+ , any input dataset 𝑋 ∈ D, any 𝑚 ∈ N+ , and any budget list 𝐿 ∈ R𝑚 such that 𝜖 ′ is the 𝑖 ′ -th element of 𝐿, the result 𝑟𝑖 ′ = M {𝑖 ′ } (𝑋, 𝐿) achieves error bounds that match the optimal bounds: E[Error(𝑟𝑖 ′ , 𝑞(𝑋 ))] ≤ 𝛼 · E[Error(M ∗ (𝑋, 𝜖 ′ ), 𝑞(𝑋 ))], where M ∗ : X × R+ ↦→ Y denotes the optimal mechanism for query 𝑞 under privacy budget 𝜖 ′ . This property provides an incentive for analysts to participate in the multi-tier system. Remark 3.1. We note that other types of requirements may also be relevant. For example, M should operate efficiently, in time
Multi-tier Differential Private Query Release
Conference acronym ’XX, June 03–05, 2018, Woodstock, NY
polynomial in the dataset size and number of analysts. In this paper, our proposals satisfy this efficiency requirement.
4
�
Higher ��
Multi-tier Noise-adding Mechanisms
This section presents a general multi-tier framework for noiseadding DP mechanisms based on characteristic functions, and then provides concrete realizations for count queries.
4.1
�� = �(�) + �(�� )
Residual Noise ��
Lower ��+1
A Framework via Characteristic Functions
The basic idea of the framework is to gradually inject calibrated noises. It first generates a query result with the highest budget, then uses that high-budget result to generate lower-budget results sequentially, without accessing the dataset again. Therefore, by the data processing inequality, these multi-tier results naturally satisfy the advanced collusion-resistant property. Specifically, our framework leverages the characteristic function (CF) of the noise distribution to derive the calibrated residual noise needed to transform a high-budget result into a low-budget result. Consider two noise distributions 𝜂 (𝜖𝑖 ) and 𝜂 (𝜖𝑖+1 ) with 𝜖𝑖 > 𝜖𝑖+1 , corresponding to some noise-adding DP mechanisms that provide 𝜖𝑖 -DP and 𝜖𝑖+1 -DP guarantees, respectively. Our objective is to
��+1 = �� + �� ��+1 = �(�) + �(��+1 )
�(�) �(��+1 )
÷
�(�� )
Characteristic Function (CF) ��� (�) =
��(��+1) (�) ��(��) (�)
Independent of � and �(�)
Figure 2: Procedures of multi-tier DP noises adding from 𝜖𝑖 to 𝜖𝑖+1 . Theorem 4.1 (Advanced Collusion Resistance of Multi-tier Noise-adding Framework). Algorithm 1 satisfies the advanced collusion-resistance property.
𝑑
transform an output 𝑟𝑖 = 𝑞(𝑋 ) + 𝜂 (𝜖𝑖 ) into an output 𝑟𝑖+1 = 𝑞(𝑋 ) + 𝜂 (𝜖𝑖+1 ) without direct access to 𝑞(𝑋 ) or to the dataset 𝑋 . The key insight is to exploit the summation property of characteristic functions. For independent random variables, the characteristic function of their sum is the product of their individual characteristic functions. Applying this property, we have: Φ𝑞 (𝑋 )+𝜂 (𝜖𝑖+1 ) (𝑡) = 𝑒 𝑗𝑡𝑞 (𝑋 ) · Φ𝜂 (𝜖𝑖+1 ) (𝑡); Φ𝑞 (𝑋 )+𝜂 (𝜖𝑖 ) (𝑡) = 𝑒 𝑗𝑡𝑞 (𝑋 ) · Φ𝜂 (𝜖𝑖 ) (𝑡). Dividing these equations isolates the residual noise (denoted as 𝑠𝑖 ): Φ𝑠𝑖 (𝑡) =
Φ𝑞 (𝑋 )+𝜂 (𝜖𝑖+1 ) (𝑡) Φ𝜂 (𝜖𝑖+1 ) (𝑡) = , Φ𝑞 (𝑋 )+𝜂 (𝜖𝑖 ) (𝑡) Φ𝜂 (𝜖𝑖 ) (𝑡)
which represents the characteristic function of the incremental residual noise required to transform 𝑟𝑖 into 𝑟𝑖+1 . Crucially, Φ𝑠𝑖 (𝑡) depends only on the noise distributions of 𝜂 (𝜖𝑖 ) and 𝜂 (𝜖𝑖+1 ), and is independent of both 𝑞(𝑋 ) and the underlying dataset 𝑋 . This property enables the Markov transformation without direct access to the true query answer 𝑞(𝑋 ) or the dataset 𝐷. Given an observed output 𝑟𝑖 = 𝑞(𝑋 ) + 𝜂 (𝜖𝑖 ), applying the transformation 𝑟𝑖+1 = 𝑟𝑖 + 𝑠𝑖 produces a new output distributed identically to 𝑞(𝑋 ) + 𝜂 (𝜖𝑖+1 ). We present the overall procedure in Algorithm 1. The distribution of 𝑠𝑖 can be derived from its characteristic function Φ𝑠𝑖 (𝑡) via the inverse Fourier transform [29], provided that Φ𝑠𝑖 (𝑡) is a valid characteristic function (a condition that can be checked using established criteria [8]). This framework satisfies the advanced collusion-resistant property, since for any 𝑆 ⊆ [𝑚], all low-budget results are derived from the highest-budget result in 𝑆. See formal statement in Theorem 4.1 (proved in Appendix A). As shown in the next section, the algorithm may fail depending on the choice of the base mechanism. However, for the most commonly used mechanisms, including the Laplace and Gaussian mechanisms, the algorithm is guaranteed to succeed.
Algorithm 1: Multi-tier DP Noise Adding Input : Dataset 𝑋 , query 𝑞, privacy list 𝜖1 > 𝜖2 > · · · > 𝜖𝑚 , noise distributions {𝜂 (𝜖𝑖 )}𝑖 ∈ [𝑚] 𝑑
Output : Outputs {𝑟𝑖 }𝑖 ∈ [𝑚] where 𝑟𝑖 = 𝑞(𝑋 ) + 𝜂 (𝜖𝑖 ) // step 1: Generate highest-budget output 1 𝑟 1 ← 𝑞(𝐷) + 𝜂 (𝜖 1 ) 2 for 𝑖 = 1 to 𝑚 − 1 do // step 2: Add residual noise Φ𝑠𝑖 ←
3
if Φ𝑠𝑖 is a valid characteristic function (CF) then // derive the residual distribution 𝑠𝑖 ← CF−1 (Φ𝑠𝑖 ) 𝑠 ∼ 𝑠𝑖 𝑟𝑖+1 ← 𝑟𝑖 + 𝑠 else return Failed
4
5 6 7 8 9 10
Φ𝜂 (𝜖𝑖+1 ) Φ𝜂 (𝜖𝑖 )
return {𝑟 1, 𝑟 2, . . . , 𝑟𝑚 }
4.2
Use Cases
In this section, we instantiate the proposed multi-tier noise addition framework with state-of-the-art base mechanisms for count queries, and also demonstrate cases where the base mechanism fails. 4.2.1 Multi-tier Count Queries with Δ = 1. The two-sided Geometric (TSG) mechanism is known to be universally optimal for count queries [16] with Δ = 1, and its noise’s characteristic function is (1−𝑝𝑖 ) 2 , where 𝑝𝑖 1−2𝑝𝑖 cos 𝑡 +𝑝𝑖2
= 𝑒 −𝜖𝑖 /Δ𝑓 . In the multi-tier noise-adding
framework, the residual kernel Φ𝑠𝑖 (𝑡) is then: Φ𝑠𝑖 (𝑡) =
Φ𝜂 (𝜖𝑖+1 ) (𝑡) (1 − 𝑝𝑖+1 ) 2 (1 − 2𝑝𝑖 cos 𝑡 + 𝑝𝑖2 ) = . 2 ) Φ𝜂 (𝜖𝑖 ) (𝑡) (1 − 𝑝𝑖 ) 2 (1 − 2𝑝𝑖+1 cos 𝑡 + 𝑝𝑖+1
Conference acronym ’XX, June 03–05, 2018, Woodstock, NY
Noise Mechanisms
Wang et al.
Distribution
CF
Residual CF
𝜖 −𝜖 |𝑥 | 2𝑒
𝜖2 𝜖 2 +𝑡 2
2 (𝜖 2 +𝑡 2 ) 𝜖𝑖+1 𝑖 2 +𝑡 2 ) 𝜖𝑖2 (𝜖𝑖+1
𝐿𝑎𝑝𝑙𝑎𝑐𝑒 (𝜖) [12]
Residual Distribution 𝜖2 w.p. 𝜖𝑖+1 0, 2 𝑖 𝜖2 𝐿𝑎𝑝𝑙𝑎𝑐𝑒 (𝜖𝑖+1 ), w.p. 1 − 𝑖+1 𝜖𝑖2 2 − 𝜎 2) 𝐺𝑎𝑢𝑠𝑠𝑖𝑎𝑛(𝜎𝑖+1 𝑖
2
𝐺𝑎𝑢𝑠𝑠𝑖𝑎𝑛(𝜎 2 ) [13]
− 𝑥 √ 1 𝑒 2𝜎 2 2𝜋𝜎 2
𝑒− 2𝜎 𝑡
𝑒 − 2 (𝜎𝑖+1 −𝜎𝑖 )𝑡
1−𝑝 |𝑥 | 1+𝑝 𝑝
(1−𝑝 ) 2 1−2𝑝 cos 𝑡 +𝑝 2
(1−𝑝𝑖+1 ) 2 (1−2𝑝𝑖 cos 𝑡 +𝑝𝑖2 ) 2 ) (1−𝑝𝑖 ) 2 (1−2𝑝𝑖+1 cos 𝑡 +𝑝𝑖+1
𝑒 2𝜆 (cos 𝑡 −1)
𝑒 2(𝜆𝑖+1 −𝜆𝑖 ) (cos 𝑡 −1)
(1−𝑝 ) 2 𝑝𝑖 0, w.p. (1−𝑝𝑖+1 2 𝑖 ) 𝑝𝑖+1 (𝑝 −𝑝 ) (1−𝑝𝑖 𝑝𝑖+1 ) 𝑇 𝑆𝐺 (𝑝𝑖+1 ), w.p. 𝑖+1(1−𝑝𝑖 𝑖 ) 2 𝑝𝑖+1 𝑆𝑘𝑒𝑙𝑙𝑎𝑚(𝜆𝑖+1 − 𝜆𝑖 )
invalid (in general)
× (see Remark 4.1)
Two-sided Geometric (𝑇 𝑆𝐺 (𝑝)) [16]
𝑒 −2𝜆 𝐼 |𝑥 | (2𝜆)
𝑆𝑘𝑒𝑙𝑙𝑎𝑚(𝜆) [2]
𝑒
discrete Gaussian (𝐷𝐺 (𝜎 2 )) [9]
−𝑥 2 /(2𝜎 2 )
Í
𝑧 ∈Z 𝑒
1
1 2 2
𝑥 ∈Z
2 2 𝑒 −𝑥 /(2𝜎 ) +𝑗𝑡𝑥
Í
−𝑧 2 /(2𝜎 2 )
Í
−𝑧 2 /(2𝜎 2 )
𝑧 ∈Z 𝑒
2
2
2
Table 1: Characteristic functions and residuals of commonly-used noise-adding DP mechanisms.
By the mixture property, this residual noise’s characteristic function can be decomposed as: (1 − 𝑝𝑖+1 ) 2 (1 − 2𝑝𝑖 cos 𝑡 + 𝑝𝑖2 ) 2 ) (1 − 𝑝𝑖 ) 2 (1 − 2𝑝𝑖+1 cos 𝑡 + 𝑝𝑖+1
=
(1 − 𝑝𝑖+1 ) 2 𝑝𝑖 (𝑝𝑖+1 − 𝑝𝑖 )(1 − 𝑝𝑖 𝑝𝑖+1 ) (1 − 𝑝𝑖+1 ) 2 · 1 + · , 2 (1 − 𝑝𝑖 ) 2 𝑝𝑖+1 (1 − 𝑝𝑖 ) 2 𝑝𝑖+1 1 − 2𝑝𝑖+1 cos 𝑡 + 𝑝𝑖+1
where 1 is the characteristic function of the Dirac distribution at (1−𝑝𝑖+1 ) 2 value 0, and 1−2𝑝 cos is the characteristic function of a TSG 2 𝑡 +𝑝 𝑖+1
𝑖+1
noise. Therefore, the residual noise 𝑠𝑖 is as follows: 𝑠𝑖 =
0, TSG(𝑝𝑖+1 ),
(1−𝑝
) 2𝑝
𝑖 w. p. (1−𝑝𝑖+1 ; ) 2𝑝
w. p.
𝑖 𝑖+1 (𝑝𝑖+1 −𝑝𝑖 ) (1−𝑝𝑖 𝑝𝑖+1 ) (1−𝑝𝑖 ) 2 𝑝𝑖+1
Remark 4.1. Our framework also facilitates analyzing the existence of multi-tier versions for other prevalent noise-adding mechanisms. For example, the discrete Gaussian (DG) mechanism [9] has characteristic function: ∑︁ ∑︁ 2 2 2 2 Φ𝜎 (𝑡) := 𝑒 −𝑘 /(2𝜎 ) 𝑒 𝑗𝑘𝑡 / 𝑒 −𝑘 /(2𝜎 ) , 𝑘 ∈Z
𝑘 ∈Z
and the residual function is Φ𝜎𝑖+1 (𝑡)/Φ𝜎𝑖 (𝑡). Recall that any valid characteristic function 𝑅 : R → C must be positive definite [8]: for every 𝑛 ∈ N and every choice of points 𝑡 1, . . . , 𝑡𝐶 ∈ R, the associated Bochner matrix 𝑀 := 𝑀𝑎,𝑏 𝑎,𝑏 ∈ [𝐶 ] , 𝑀𝑎,𝑏 := 𝑅(𝑡𝑎 − 𝑡𝑏 ),
(1) .
4.2.2 Multi-tier Count Queries with Δ > 1. We note that an optimal mechanism for count queries with Δ > 1 when 𝜖 > 1 (i.e., MSDLap [17]) is available via weighted summation of Δ independent twosided Geometric noises, each with budget 𝜖. Specifically, it achieves an MSE error rate of 𝑂 (Δ3 · 𝑒 −𝜖 ) and is constructed as follows: ∑︁ MSDLap(𝜖) = 𝜉 · TSG(𝜖).
must be Hermitian positive semi-definite. Equivalently, all eigenvalues of 𝑀 must be non-negative. We construct a counterexample for the residual function 𝑅(𝑡) = Φ𝜎𝑖+1 (𝑡)/Φ𝜎𝑖 (𝑡) with 𝜎𝑖+1 = 1.1 and 𝜎𝑖 = 1. When 𝑡 takes values in {𝜋 ·(𝑘−1)/2}𝑘 ∈ [4] , the Bochner matrix 𝑀 ∈ C4×4 with entries 𝑀𝑎,𝑏 = 𝑅(𝑡𝑎 − 𝑡𝑏 ) is:
𝜉 ∈ [Δ]
For multi-tier privacy levels, one can simply add Δ weighted inÍ dependent residual noises from Equation 1 (i.e., 𝜉 ∈ [Δ] 𝜉 · 𝑟𝑖 ) to transform from MSDLap(𝜖𝑖 ) to MSDLap(𝜖𝑖+1 ), thereby obtaining a multi-tier version of the MSDLap mechanism. 4.2.3 Other Queries. Many other popular DP noise-adding mechanisms (e.g., Laplace [12], Gaussian [13], Skellam [2]) can also be turned into multi-tier versions within our framework. We list their characteristic functions and residual noises in Table 1. Specifically, the Laplace mechanism are commonly used for numerical queries without non-integer constraints; the Skellam mechanism are particular useful for decentralized DP queries over cryptographic secure aggregation where query results must be quantized for compatible in the cryptographic domain and each party injects partial noises. These mechanisms, together with the two-sided geometric mechanism, encompass most use cases of noise-adding DP (including those implemented in popular repositories such as OpenDP, IBM’s Diffprivlib, PySyft, Google DP, TensorFlow Privacy, and Opacus).
1 0.771729 0.354762 0.771729
0.771729 1 0.771729 0.354762
0.354762 0.771729 1 0.771729
0.771729 0.354762 0.771729 1
It has a smallest eigenvalue of approximately −0.1886953 < 0. Therefore, 𝑀 is not positive semi-definite, the Φ𝜎𝑖+1 (𝑡)/Φ𝜎𝑖 (𝑡) is not a valid characteristic function, and no additive noise can transform from DG(12 ) to DG(1.12 ). A similar failure happens to the staircase mechanism [14] (see Appendix F) .
5
Multi-tier Mapping Mechanisms
In this section, we study multi-tier DP count queries in the local model of DP, which often employ mapping-based mechanisms. Intuitively, these mechanisms define a general transition or mapping probability matrix, and the output domain may not align with the input domain (unlike noise-adding mechanisms). Particularly, for count queries over categorical data, we propose a multi-tier LDP mechanism based on the Subset mechanism [31].
Multi-tier Differential Private Query Release
5.1
A Template-based Method
Conference acronym ’XX, June 03–05, 2018, Woodstock, NY
Expansion operator. Given a Subset output 𝑟 of size 𝑘 and d
Many state-of-the-art mapping-based mechanisms use output domains with hyperparameters, whose optimal values depend on the privacy budget 𝜖. Examples include the subset size in Subset mechanisms [31], the hash domain size in local hashing [33], and the partition size in Hadamard response [1]. These mechanisms face challenges in multi-tier settings: transitions between privacy levels require adapting both hyperparameters and probability ratios that determine privacy levels, and it might be impossible to meet optimal hyperparameter conditions for all target levels 𝜖𝑖 . As a result, utility gaps may arise, unlike in multi-tier noise-adding mechanisms, where smooth residual noise injection is often possible. To address this, we propose a template-based method. It firstly defines primitive operators that adapt hyperparameters while maintaining distributional equivalence, then identifies reference privacy levels where these transitions are viable and generate corresponding templates, finally matches the privacy list 𝐿 to the templates. Specifically, the method works as follows: (1) Design primitive operators: For a base mechanism with hyperparameter 𝜃 , define operators that can adapt 𝜃 and/or adjust the probability ratio to achieve target privacy levels, while preserving distributional equivalence to the base mechanism. (2) Set reference privacy levels: Identify privacy levels {𝜖𝑘′ } in descending order where hyperparameter and probability ratio transitions are naturally supported by the primitive operators. (3) Generate templates: For each 𝜖𝑘′ , sequentially generate a template 𝑟𝑘′ from 𝑟𝑘′ −1 using the primitive operators. (4) Match levels: For target level 𝜖𝑖 , select the closest template with 𝜖𝑘′ ≤ 𝜖𝑖 . When reference privacy levels are close to each other, the utility gap between the optimal error bound of 𝜖𝑖 and the matched template are guaranteed to be small. In following subsections, we demonstrate this method using the Subset mechanism [31, 32]. This method also applies to the local hash mechanism [33] (see Appendix G). We focus on the Subset mechanism, as it is known to achieve optimal results for LDP count queries in all privacy regimes [37].
5.2
Multi-tier Subset Mechanism
Recall that in the Subset mechanism R over a one-hot data domain 𝑥 ∈ {0, 1}𝑑 with budget 𝜖 and subset size 𝑘, the variance is: 𝑉 (𝜖, 𝑘) = E[(R (𝑥) − 𝑥)22 ] =
𝑡 (1 − 𝑡) + (𝑑 − 1)𝑓 (1 − 𝑓 ) , (𝑡 − 𝑓 ) 2
𝜖
−1)+(𝑑 −𝑘 )𝑘 where 𝑡 = 𝑘𝑒 𝜖𝑘𝑒+𝑑 −𝑘 and 𝑓 = 𝑘𝑒(𝑘𝑒(𝑘 𝜖 +𝑑 −𝑘 ) (𝑑 −1) . The variance formula can be further simplified as: (𝑑 − 1) 𝑘 − 𝑑 + (𝑑 − 𝑘) 2 + 2𝑒 𝜖 (𝑑 − 𝑘)𝑘 + 𝑒 2𝜖 (𝑘 − 1)𝑘 𝑉 (𝜖, 𝑘) = . (𝑒 𝜖 − 1) 2 (𝑑 − 𝑘)𝑘 𝜖
Theoretical analyses [31, 32, 37] indicate that 𝑘 ≈ 𝑑/(𝑒 𝜖 + 1) minimizes the estimation variance, and the optimal subset size is non-decreasing with the privacy budget. Therefore, we introduce two primitive operations for adjusting the subset size/privacy sequentially (from a relatively lower privacy setting to a relatively higher one) in the multi-tier setting without accessing the original true value:
privacy level 𝜖 (i.e., 𝑟 = Subset(𝑥, 𝑘, 𝜖)), the expansion operator extends the subset by one element. Specifically, we add one uniformly random element from [𝑑] \ 𝑟 to 𝑟 , obtaining: Expansion(𝑟 ) = 𝑟 ∪ {uniform([𝑑] \ 𝑟 )}. In Lemma 5.1, we show that the expanded result is distributionally equivalent to a Subset output with a lower budget. Lemma 5.1 (Properties of expansion operation). Let 𝑟 ∈ [𝑑] 𝑘 denote the output variable of the subset mechanism tightly satisfies d
with budget 𝜖 (i.e., 𝑟 = 𝑆𝑢𝑏𝑠𝑒𝑡 (𝑥, 𝑘, 𝜖)), then 𝜖 𝑒 𝑘 +1 d Expansion(𝑟 ) = 𝑆𝑢𝑏𝑠𝑒𝑡 𝑥, 𝑘 + 1, ln . 𝑘 +1 Rescale operator. Given a Subset output 𝑟 and a parameter 𝛽 ∈ [0, 1), the rescale operation Rescale(𝑟, 𝛽) outputs the original input 𝑟 with probability 𝛽, otherwise it samples a uniform random element from {𝑠 ⊆ [𝑑] : |𝑠 | = |𝑟 |} as the output: ( 𝑟, 𝑤 .𝑝. 𝛽; 𝑅𝑒𝑠𝑐𝑎𝑙𝑒 (𝑟, 𝛽) = uniform({𝑠 ⊆ [𝑑] : |𝑠 | = |𝑟 |}), 𝑤 .𝑝. 1 − 𝛽. In Lemma 5.2, we show that Rescale(𝑟, 𝛽) satisfies a new level of LDP and is distributionally equivalent to a new level Subset output (see Appendix C for proof). Conversely, setting the parameter to ′
(𝑒 𝜖 − 1)(𝑘𝑒 𝜖 + 𝑑 − 𝑘) , ′ 𝑑 (𝑒 𝜖 − 𝑒 𝜖 ) transforms the privacy level from 𝜖 to 𝜖 ′ (assuming 𝜖 ′ < 𝜖). 𝛽=
Lemma 5.2 (Properties of rescale operation). Let 𝑟 ∈ [𝑑] 𝑘 denote the output variable of the subset mechanism with budget 𝜖 d
(i.e., 𝑟 = 𝑆𝑢𝑏𝑠𝑒𝑡 (𝑥, 𝑘, 𝜖)), then for 0 ≤ 𝛽 ≤ 1: 𝑑𝛽𝑒 𝜖 + (1 − 𝛽)(𝑘𝑒 𝜖 + 𝑑 − 𝑘) d Rescale(𝑟, 𝛽) = 𝑆𝑢𝑏𝑠𝑒𝑡 𝑥, 𝑘, log . 𝑑𝛽 + (1 − 𝛽)(𝑘𝑒 𝜖 + 𝑑 − 𝑘) Failure of direct adaptation. When transforming from a higher budget 𝜖𝑖 to a lower budget 𝜖𝑖+1 , in order to achieve desirable utility, we may need to adapt both the subset size and the probability ratio (i.e., 𝑒 𝜖 ). However, a straightforward approach that sequentially adapts the subset size and the privacy level for 𝜖1, . . . , 𝜖𝑚 may be infeasible, since not all exact optimality conditions can be satisfied simultaneously for these privacy levels. For example, with 𝑑 = 10, 𝜖 = ln(6.4), and 𝜖 ′ = ln(5), the optimal subset sizes that minimize variance are 𝑘 = 1 and 𝑘 ′ = 2, respectively. After applying an expansion operation to Subset(𝑥, 𝑘, 𝜖), the privacy level of Expansion(𝑟 ) becomes ln 6.4·1+1 = ln(3.7), which is lower than the next target 1+1 privacy level 𝜖 ′ = ln(5). This also implies that achieving exactly best utility for all privacy levels, as in the single-tier subset mechanism, is generally impossible. A template-based approach. We aim to approximately match the best utility and employ the template-based method that generates a series of viable outputs using the two operations. This series corresponds to a list of reference privacy levels {ln(𝑑/𝑘 − 1)}𝑘 ∈ [1,⌊ (𝑑 −1)/2⌋ ] , whose optimal subset size changes from 1 to ⌊(𝑑 − 1)/2⌋. This is sequentially viable using the expansion and rescale operators,
Conference acronym ’XX, June 03–05, 2018, Woodstock, NY