Multi-tier Differential Private Query Release

Multi-tier Differential Private Query Release Shaowei Wang, Jinn Li, Yun Peng

arXiv:2606.15543v1 [cs.CR] 14 Jun 2026

Guangzhou University Guangzhou, China wangsw@gzhu.edu.cn

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 permissions@acm.org. 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



5 = 0.6

6 = 0.3

7 = 0.1







 

   

   







 

 





          

 

 

  



 



 



 



 



4 = 1.0





3 = 1.7











0DWFKLQJ 









PXOWLWLHU6XEVHWL2





2 = 2.5

,QWHUPHGLDWHUHVXOWZLWKVXEVHWVL]HN





SULYDF\OLVW/







1 = 3.0

PXOWLWLHU6XEVHWL1

7HPSODWHZLWKVXEVHWVL]HN



5HVFDOHRSHUDWLRQ 

([SDQVLRQRSHUDWLRQ

Wang et al.

Figure 3: Procedure demonstration of multi-tier subset mechanism with 𝑑 = 8. because when applying the expansion operator to the previous template result 𝑟 with budget ln(𝑑/𝑘 − 1), according to Lemma 5.1, Expansion(𝑟 ) satisfies the LDP level of:       𝑘 (𝑑/𝑘 − 1) + 1 𝑑 −𝑘 +1 𝑑 ln = ln > ln − 1 , (2) 𝑘 +1 𝑘 +1 𝑘 +1 which is always larger than the next reference budget ln(𝑑/(𝑘 + 1) − 1). Finally, we match each target level in 𝐿 to the closest lower-budget template (see Algorithm 4). The advantage of this template-based approach over naive sequential adaptation is clear: the template results for the reference privacy levels {ln(𝑑/𝑘 − 1)}𝑘 ∈ [1,⌊ (𝑑 −1)/2⌋ ] are exactly optimal at their levels, and each privacy level 𝜖𝑖 in 𝐿 can be matched to a nearby template result. Recall the previous example: the privacy level in the naive sequential approach jumped from ln(6.4) to ln(3.7), which is lower than the reference privacy level ln(4) = ln(10/2 − 1); matching the next target level ln(5) to ln(3.7) causes more excess utility loss than matching it to ln(4). The overall multi-tier subset mechanism (presented in Algorithm 2) consists of five major steps: (1) Handle low privacy regimes: For privacy levels 𝜖𝑖+1 such that ∗ = 1), sequentially generate the 1-subset 𝑒 𝜖𝑖+1 +1 > 𝑑 (where 𝑘𝑖+1 mechanism’s output. Use the Rescale operator with 𝛽=

(𝑒 𝜖𝑖+1 − 1)(𝑒 𝜖𝑖 + 𝑑 − 1) 𝑑 (𝑒 𝜖𝑖 − 𝑒 𝜖𝑖+1 )

during the sequential procedure, ensuring that the resulting output satisfies the target level of 𝜖𝑖+1 -LDP (assuming 𝜖0 = +∞). (2) Generate middle regime templates: For each 𝑘 ∈ [1, ⌊(𝑑 − 1)/2⌋], sequentially generate a template result for 𝜖𝑘′ = ln(𝑑/𝑘 − 1). Each generation iteration involves two steps: first expanding the subset size by 1, and then rescaling the probability ratio to exactly 𝑑/𝑘 − 1. This is summarized in Algorithm 3, for which Lemma 5.1 ensures that the resulting probability ratio 𝜌 after expansion is always larger than 𝑑/𝑘 − 1 (i.e., 𝜖𝑘′ is exactly achievable by a further rescale operator). (3) Handle high privacy regimes when (𝑑 + 2)/⌊𝑑/2⌋ < 𝑒 𝜖 + 1 < 𝑑/⌊(𝑑 − 1)/2⌋: When 𝑑 is even, for the privacy regime where (𝑑 + 2)/⌊𝑑/2⌋ < 𝑒 𝜖 + 1 < 𝑑/⌊(𝑑 − 1)/2⌋, expand the subset size from ⌊(𝑑 − 1)/2⌋ to ⌊𝑑/2⌋ and save the corresponding result.

Algorithm 2: Multi-tier Subset Mechanism 𝑆𝑢𝑏𝑠𝑒𝑡 𝐿 (𝑥) Input : Privacy list 𝐿 = {𝜖1, . . . , 𝜖𝑚 }; the true value 𝑥 ∈ [𝑑] Output : Query results {𝑟𝑖 }𝑖 ∈ [𝑚] each with 𝜖𝑖 -LDP 1 𝑅 ← {}; 𝑠 ← {𝑥 }; 𝜌 ← +∞ // Step 1: handle cases when 𝑒𝑖𝜖 + 1 > 𝑑 𝜖 2 for 𝜖𝑖 in 𝐿 where 𝑒 𝑖 + 1 > 𝑑 do   (𝑒 𝜖𝑖 −1) (𝑘𝜌+𝑑 −𝑘 ) 𝑑 (𝜌 −𝑒 𝜖𝑖 )

3

𝑠 ← Rescale 𝑠,

4

append (𝜖𝑖 , 𝑠) to 𝑅

; 𝜌 ← 𝑒 𝜖𝑖

// Step 2: generate middle templates ′ 5 𝑅 , 𝑠, 𝜌 =TeampleGen(𝑠, 𝜌) ′ 6 append elements in 𝑅 to 𝑅 // Step 3: handle cases when 𝑑 is even 𝜌 |𝑠 |+1

𝜌 ← |𝑠 |+1 ; 𝑠 ← Expansion(𝑠) 8 append (ln(𝜌), 𝑠) to 𝑅 // Step 4: cases when 𝑒 𝜖𝑖 + 1 < (𝑑 + 2)/⌊𝑑/2⌋ (if 𝑑 is even) or 𝑒 𝜖𝑖 + 1 < 𝑑/⌊(𝑑 − 1)/2⌋ (if 𝑑 is odd) 𝜖 9 for 𝜖𝑖 in 𝐿 where 𝑒 𝑖 < 𝜌 do   7

(𝑒 𝜖𝑖 −1) (𝑘𝜌+𝑑 −𝑘 ) 𝑑 (𝜌 −𝑒 𝜖𝑖 )

10

𝑠 ← Rescale 𝑠,

11

append (𝜖𝑖 , 𝑠) to 𝑅

; 𝜌 ← 𝑒 𝜖𝑖

// Step 5: match privacy list to results 12 {𝑟 1 , . . . , 𝑟𝑚 } ←TemplateMatch(𝑅, 𝐿) 13 return {𝑟 1 , . . . , 𝑟𝑚 }

(4) Handle high privacy regimes when 𝑒 𝜖 + 1 < (𝑑 + 2)/⌊𝑑/2⌋ (if 𝑑 is even) or 𝑒 𝜖 + 1 < 𝑑/⌊(𝑑 − 1)/2⌋ (if 𝑑 is odd): Sequentially generate the corresponding result from the previous result for the specific 𝜖𝑖+1 using only the rescale operator. (5) Match privacy list to results: Given the generated results 𝑅, for each target level 𝜖𝑖 ∈ 𝐿, find the closest result that satisfies 𝜖𝑖 and set that result as 𝑟𝑖 . We depict an example of the procedure in Figure 3 (denoted as multi-tier Subset𝐿1 ). We note that each template {𝑟𝑘′ }𝑘 satisfies exactly ln(𝑑/𝑘 −1)-LDP and is exactly optimal at the corresponding privacy level. These templates help provide desirable results (with

Multi-tier Differential Private Query Release

Algorithm 3: TemplateGen(𝑠, 𝜌) Input : Previous result 𝑠 satisfying ln(𝜌)-LDP and |𝑠 | = 1 with 𝜌 + 1 > 𝑑. Output : Templates {𝑟𝑘′ }𝑘 ∈ [1,⌊ (𝑑 −1)/2⌋ ] each satisfies ln(𝑑/𝑘 − 1)-LDP. ′ 1 𝑅 ← {} 2 for 𝑘 ∈ [1, ⌊(𝑑 − 1)/2⌋] do 3 if 𝑘 > |𝑠 | then // expand the subset size by 1 4

𝜌 |𝑠 |+1

𝜌 ← |𝑠 |+1 ; 𝑠 ← Expansion(𝑠)

6

// rescale the probability ratio/budget 𝜖𝑘′ ← ln(𝑑/𝑘 − 1)   𝜖′ ′ (𝑒 𝑘 −1) (𝑘𝜌+𝑑 −𝑘 ) 𝑠 ← Rescale 𝑠, ; 𝜌 ← 𝑒 𝜖𝑘 𝜖′

7

append (𝜖𝑘′ , 𝑠) to 𝑅 ′

5

𝑑 (𝜌 −𝑒 𝑘 )

′ 8 return 𝑅 , 𝑠, 𝜌

Algorithm 4: TemplateMatch(𝑅, 𝐿) Input : Sorted templates 𝑅; privacy list 𝐿 = {𝜖1, . . . , 𝜖𝑚 } Output : Results {𝑟𝑖 }𝑖 ∈ [1,𝑚] with 𝑟𝑖 satisfies 𝜖𝑖 -LDP // 𝑅 [𝑙].𝜖: the 𝑙-th template’s level // 𝑅 [𝑙].𝑠: the 𝑙-th template’s result 1 for 𝑖 ← 1 to 𝑚 do 2 𝑙𝑖 ← arg min𝑙 ∈ [ |𝑅 | ] {𝑅 [𝑙].𝜖 ≤ 𝜖𝑖 } 3 𝑟𝑖 ← 𝑅 [𝑙𝑖 ].𝑠 4

return {𝑟 1, . . . , 𝑟𝑚 }

sufficiently close optimal subset size and close privacy level) in the middle privacy regime. For privacy levels in the low and high privacy regimes, the mechanism exactly matches the optimal subset mechanism. We provide the overall utility-match (see Definition 3.3) guarantee of the multi-tier subset mechanism in Theorem 5.3. Theoretically, the multiplicative factor is upper bounded by 171/11 (see Appendix D). Numerically, its value is relatively small in most cases (e.g., ≤ 3), according to Figure 4 (left part). Theorem 5.3 (Utility of Multi-tier Subset Mechanism). For any 𝜖𝑖 ∈ 𝐿 in the multi-tier subset mechanism 𝑆𝑢𝑏𝑠𝑒𝑡 𝐿 (𝑥), let 𝑘𝑖∗ denote the optimal subset size arg min𝑘 ∈ [1,...,⌊𝑑/2⌋ ] 𝑉 (𝜖𝑖 , 𝑘), the correspond result 𝑆𝑢𝑏𝑠𝑒𝑡 𝐿 (𝑥)𝑖 = 𝑟𝑖 satisfies: E[∥𝑆𝑢𝑏𝑠𝑒𝑡 𝐿 (𝑥)𝑖 − 𝑥 ∥ 22 ] 𝑉 (𝜖𝑖 , 𝑘𝑖∗ )           𝑑 𝑑+2     𝑉 ln ⌊𝑑/2⌋ − 1 , ⌊ 𝑑2 ⌋  𝑉 ln 𝑘 𝑖 − 1 , 𝑘 𝑖       ,     . ≤ max   𝑑 𝑑 𝑑 −1   𝑉 ln 𝑘 −1 − 1 , 𝑘 𝑖 − 1 𝑉 ln ⌊ (𝑑 −1)/2⌋ − 1 , ⌊ 2 ⌋   𝑖   Since the original subset mechanism is optimal in all privacy regimes and the multi-tier subset mechanism approximates the best single-tier subset mechanism up to a constant factor, the multi-tier subset mechanism is order-optimal for all privacy regimes.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Algorithm 5: TemplateGen2(𝑠, 𝜌, 𝐿) Input : Previous result 𝑠 satisfying ln(𝜌)-LDP and |𝑠 | = 1; a list of privacy budget 𝐿 Output : A list of template randomization results ′ 1 𝐿 ←𝐿 // add more reference privacy levels 2 for 𝑘 ∈ [1, ⌊(𝑑 − 1)/2⌋] do 3 add ln(𝑑/𝑘 − 1), ln((𝑑 + 1)/𝑘 − 1) to 𝐿 ′ sort 𝐿 ′ in descending order ′ 5 𝑅 ← {} 6 for 𝑘 ∈ [1, ⌊(𝑑 − 1)/2⌋] do 7 if 𝑘 > |𝑠 | then 𝜌 |𝑠 |+1 8 𝜌 ← |𝑠 |+1 ; 𝑠 ← Expansion(𝑠) 9 append (log(𝜌), 𝑠) to 𝑅 ′ 4

for 𝜖𝑖 ∈ 𝐿 ′ that 𝜖𝑖 ∈ [ln((𝑑 − 1)/𝑘 − 1, ln(𝜌))) do if 𝑘 ≠ ⌊(𝑑 − 1)/2⌋ or 𝜖𝑖 ≥ ln(𝑑/⌊(𝑑 −  1)/2⌋ − 1) then

10 11

(𝑒 𝜖𝑖 −1) (𝑘𝜌+𝑑 −𝑘 ) 𝑑 (𝜌 −𝑒 𝜖𝑖

12

𝑠 ← Rescale 𝑠,

13

𝜌 ← 𝑒 𝜖𝑖 append (𝜖𝑖 , 𝑠) to 𝑅 ′

14

15

return 𝑅 ′, 𝑠, 𝜌

5.3

Improving Template Generation

The template generation algorithm can be further improved. The improvement exploits the gap in Equation 2, where the value of 𝑘 · (𝜌 + 1) increases by two after each expansion operation. This implies that additional templates can be generated for free within the gap regions. For example, after each expansion operation for 𝑘 ∈ [1, ⌊(𝑑 − 1)/2⌋], one can further use the rescale operation for: 𝜖𝑖 ∈ (min{𝜌, ln((𝑑 + 1)/𝑘 − 1)}, ln((𝑑 − 1)/𝑘 − 1)]

to generate extra templates. These extra templates can be closer to the privacy levels in 𝐿 and thus improve utility over Algorithm 2. We summarize the new template generation process in Algorithm 5, which takes as input the previous result and the privacy list 𝐿. We present the utility match property of the multi-tier Subset mechanism with improved template generation in Theorem 5.4. It reduces the multiplicative factor of utility matching guarantee compared to Theorem 5.3. Figure 4 demonstrates the numerical values of the multiplicative factor bounds under various 𝑑 and 𝜖𝐼 , with comparison to Theorem 5.3. In extensive settings, the improved template generation could limit the upper bound of multiplicative factors in a desirable range (e.g. < 2). Theorem 5.4 (Utility of Multi-tier Subset Mechanism with Improved Template Generation). For any 𝜖𝑖 ∈ 𝐿 in the multi-tier subset mechanism 𝑆𝑢𝑏𝑠𝑒𝑡 2𝐿 (𝑥) with template generation algorithm 5, let 𝑘𝑖∗ denote the optimal subset size arg min𝑘 ∈ [1,...,⌊𝑑/2⌋ ] 𝑉 (𝜖𝑖 , 𝑘), 𝑘 𝑖

Wang et al.

1

Basic Template Generation (Theorem 5.3)

3 4 7 16 33 64 127 256 513 1025 2048 4095 0

1

2

3

4

5 6 privacy budget

7

8

Multiplicative Factor 2

3

number of categories d

number of categories d

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

3 4 7 16 33 64 127 256 513 1025 2048 4095

9

4

5 6 7 8 910

0

1

Improved Template Generation (Theorem 5.4)

2

3

4

5 6 privacy budget

7

8

9

Figure 4: Heatmap of theoretical multiplicative factor upper bounds of Theorem 5.3 and Theorem 5.4, under varying categories 𝑑 and privacy budget 𝜖𝑖 (grid values from 0.01 to 10 with granularity 0.01). gradual(Laplace)

denote max{2, ⌈𝑑/(𝑒𝑖𝜖 + 1)⌉}, the result 𝑆𝑢𝑏𝑠𝑒𝑡 2𝐿 (𝑥)𝑖 = 𝑟𝑖 satisfies:

Computation and memory complexity. For the multi-tier algorithm using either the template generation procedure in Algorithm 3 or 5, the resulting set of templates 𝑅 contains at most 𝑚 + ⌊𝑑/2⌋ (sorted) elements. Additionally, the TemplateMatch procedure, which takes two sorted lists as input, has computational and memory complexity of 𝑂 (|𝐿| + |𝑅|). Therefore, the overall computational and memory complexity of Subset𝐿 (𝑥) is 𝑂 (|𝐿| + 𝑑).

6

MSE of r1

multi-tier(Geometric)

100

101 100

10−2

10−1 5

10

15

20

5 10

(c) grid(0.4)

100

10

15

20

10 15 Number of tiers m

20

1

(d) grid(0.8)

10−3

10−2

10−7

10−4

10−11

10−6 5

10 15 Number of tiers m

20

5

Figure 5: MSE result of count queries under grid budgets.

and the maximum MSE ratio among all tiers (Max MSE Ratio):

Experiments

In this section, we present numerical experimental results of our multi-tier DP proposals, with comparison to the following baseline: The gradual release baseline. Recall the gradual release method: (i) release an intermediate result for 𝜖𝑚 using a corresponding base mechanism; (ii) for 𝑗 ∈ [1, 𝑚 − 1], further release an intermediate result under budget 𝜖 𝑗 − 𝜖 𝑗+1 using the base mechanism; (iii) a weighted sum of the first 𝑚 − 𝑗 + 1 intermediate results is used as the query result for 𝜖 𝑗 . Specifically, each intermediate result is weighted inversely to its variance, so as to minimize the variance of the weighted-sum result [38]. Privacy list. We consider both grid and random privacy levels. The grid cases assume that the privacy list 𝐿 is uniformly separated by 𝛼 (denoted as grid(𝛼)), i.e., 𝐿 = {𝑚𝛼, (𝑚 − 1)𝛼, . . . , 𝛼 }. We vary 𝛼 from 0.1 to 0.8 and 𝑚 from 1 to 20. The random cases include budgets uniformly sampled from [0.01, 𝐶] (denoted as uniform(𝐶)) and Gaussian-sampled random budgets centered at 𝜇 with variance 𝜌 2 (denoted as normal(𝜇, 𝜌 2 )), where values below 0.01 are omitted. These settings cover many scenarios where privacy budgets vary across high and low regimes. Metrics. We evaluate the utility of query results by the mean squared error E[∥𝑟𝑖 − 𝑞(𝑋 )∥ 22 ]. Specifically, we use both the total Í mean squared error (Total MSE) defined as 𝑖 ∈ [𝑚] E[∥𝑟𝑖 − 𝑞(𝑋 )∥ 22 ]

multi-tier(Laplace)

(b) grid(0.2)

MSE of r1

E[∥𝑆𝑢𝑏𝑠𝑒𝑡 2𝐿 (𝑥)𝑖 − 𝑥 ∥ 22 ] 𝑉 (𝜖𝑖 , 𝑘𝑖∗ )           𝑑+1 𝑑+2     𝑉 ln ⌊𝑑/2⌋ − 1 , ⌊ 𝑑2 ⌋  𝑉 ln 𝑘 𝑖 − 1 , 𝑘 𝑖       ,     . ≤ max  𝑑 −1 𝑑 𝑑 −1  𝑉 ln  − 1 , 𝑘 𝑖 − 1 𝑉 ln ⌊ (𝑑 −1)/2⌋ − 1 , ⌊ 2 ⌋    𝑘 𝑖 −1  

gradual(Geometric) (a) grid(0.1)

102

max

E[∥𝑟𝑖 − 𝑞(𝑋 )∥ 22 ]

𝑖 ∈ [𝑚] E[∥M ∗ (𝑋, 𝜖𝑖 ) − 𝑞(𝑋 )∥ 2 ] 2

,

where M ∗ denotes the optimal single-tier mechanism (e.g., the base two-sided Geometric and Subset mechanisms for 𝜖𝑖 in our context). The total MSE is often dominated by the error of low-budget results, and the maximum MSE ratio cares more about individual excess error compared to solo query.

6.1

Multi-tier DP Count Queries with Noise-adding Mechanisms

Consider the most fundamental count query with sensitivity Δ = 1, for which both the Laplace and two-sided Geometric mechanisms are applicable. We compare their multi-tier versions with the gradual baseline. In Figures 5 and 6, we present the MSE results for tier 1 under grid privacy lists and the maximum MSE ratio results under random privacy lists, respectively. Our multi-tier two-sided Geometric mechanism outperforms the gradual approach by a large margin, as the gradual approach splits the budget into multiple parts and introduces more noise. As expected, the multi-tier twosided Geometric mechanism also achieves significantly lower MSE than the multi-tier Laplace mechanism, especially when the privacy budgets are relatively large.

Multi-tier Differential Private Query Release

gradual(Geometric) (a) uniform(4)

Max MSE Ratio

10

102

multi-tier(Geometric)

3 × 104

(b) uniform(8)

101 10

15

20

(c) normal(1,1)

5

Max MSE Ratio

10

15

20

5

10

15

20

6.2.1 Total MSE results. Under grid privacy lists, we vary the domain size and present the total MSE results in Figures 7 and 8, respectively. In most cases, the multi-tier, Subset𝐿1 and multi-tier, Subset𝐿2 has total MSEs close to the ideal one. Since total MSE is often dominated by low-budget results, and the base BRR is comparable to the Subset mechanism in the low-budget regimes, the multi-tier BRR only has small gap to our proposals; however, when the lowest budget is relatively large (e.g., with 𝑔𝑟𝑖𝑑 (0.8) privacy list), the error gap gets larger. As contrast, since GRR performs poorly in the low-budget regime, their total MSE has significant gap with our proposals in all settings. The 𝑔𝑟𝑎𝑑𝑢𝑎𝑙 approach is comparable to our proposals when 𝑚 is small, but the gap drastically grows as the number of tiers gets large. In random privacy lists, we vary the domain size and present the total MSE results in Figures 9 and 10 where each result is averaged in 500 simulations. Since the error of the sampled lowest-budget result dominates total MSE, and the lowest budget can be 0.01, both the BRR and the gradual approach is comparable to our proposals. 6.2.2 Maximum MSE ratio results. In grid privacy lists, we present the maximum MSE ratio results in Figures 11 and 12, respectively. When there are relatively small number of categories (i.e., 𝑑 = 15) and the subset size parameter 𝑘 in the Subset has significant effects, the multi-tier, Subset𝐿2 has much lower maximum ratio than the

5

10 15 Number of tiers m

20

5

10 15 Number of tiers m

20

Figure 7: Total MSE result of LDP categorical queries with Subset mechanism and 𝑑 = 15, under random privacy lists. ideal

BRR

GRR

gradual

multi-tier(SubsetL1 )

(a) grid(0.1)

106

multi-tier(SubsetL2 ) (b) grid(0.2)

Total MSE

Considering the release of categorical data 𝑥 ∈ [𝑑] using the subset mechanism, we compare the proposed multi-tier subset mechanism with the gradual baseline (using the subset mechanism as the base mechanism) and an ideal mechanism (denoted as ideal): each 𝑟𝑖 for level 𝜖𝑖 is released by the optimal subset mechanism Subset(𝑥, 𝑘𝑖∗, 𝜖𝑖 ), where 𝑘𝑖∗ is the optimal subset size for 𝜖𝑖 . Note that the ideal mechanism violates the collusion-resistance property; we use it as an MSE lower bound to demonstrate the excess utility loss due to coordination in our multi-tier proposal. We also compare it with the multi-tier binary randomized response [11] (denoted as BRR) and generalized randomized response [21] (denoted as GRR) mechanisms, using the re-sampling technique presented in [36]. We denote our proposal using the template generation procedure in Algorithm 3 as multi-tier, Subset𝐿1 , and the one using Algorithm 5 as multi-tier, Subset𝐿2 .

20

102

20

Multi-tier LDP Count Queries with the Subset Mechanism

15

105

105 5

10

15

20

5

10

15

20

10 15 Number of tiers m

20

104

(c) grid(0.4)

(d) grid(0.8)

Total MSE

10 15 Number of tiers m

10 (d) grid(0.8)

104 103 5

10 15 Number of tiers m

20

5

Figure 8: Total MSE result of LDP categorical queries with Subset mechanism and 𝑑 = 128, under grid privacy lists. ideal 105

BRR

GRR

gradual

multi-tier(SubsetL1 )

(a) uniform(4)

multi-tier(SubsetL2 ) (b) uniform(8)

104

Total MSE

5

5

2 × 102

103

Figure 6: Maximum MSE result of count queries under random budgets (averaged over 500 simulations).

6.2

2 × 103

104 103

103

10

5

5

10

15

20

5

(c) normal(1,1)

10

15

20

10 15 Number of tiers m

20

(d) normal(2,4)

Total MSE

20

multi-tier(SubsetL2 ) (b) grid(0.2)

(c) grid(0.4)

101 10 15 Number of tiers m

multi-tier(SubsetL1 )

6 × 103 4 × 103 3 × 103

6 × 103

103

5

gradual

104

101 100

GRR

(a) grid(0.1)

(d) normal(2,4)

105

102

BRR

Total MSE

5

ideal

2 × 104

103

101 100

multi-tier(Laplace) 5

Total MSE

gradual(Laplace) 103

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

104

104

103

103 5

10 15 Number of tiers m

20

5

Figure 9: Total MSE result of LDP categorical queries with Subset mechanism and 𝑑 = 15, under random privacy lists. multi-tier, Subset𝐿1 through generating more templates, and is very close to the ideal one (with the ratio controlled near to 1). The BRR is comparable to multi-tier, Subset𝐿2 when all privacy budgets are relatively low (e.g., in 𝑔𝑟𝑖𝑑 (0.1)), but the gap are significant when the largest budget gets large. Since the base GRR has relatively large errors in the low-budget regime, it has significant gaps with the multi-tier, Subset𝐿2 when 𝛼 ∈ [0.1, 0.2, 0.4], though the gap is relatively small in the 𝑑 = 15 & 𝑔𝑟𝑖𝑑 (0.8) setting. When there are relatively large number of categories (i.e., 𝑑 = 15), the gap between our two proposals are quite small (as neighboring subset size 𝑘 has small error effects in Subset), and the maximum ratios of both

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

ideal

BRR

GRR

gradual

Total MSE

105

BRR

10

15

20

5

(c) normal(1,1)

10

15

20

(d) normal(2,4) 106

106

100

10 15 Number of tiers m

20

5

10 15 Number of tiers m

20

Figure 10: Total MSE result of LDP categorical queries with Subset mechanism and 𝑑 = 128, under random privacy lists. BRR

GRR

gradual(Subset)

multi-tier(SubsetL1 )

100

101

5

10

15

20

100

5

10

15

20

100

5

GRR

gradual(Subset)

multi-tier(SubsetL1 )

10 15 Number of tiers m

20

100

10

15

20

100

5

10

15

20

100

15

20

100

5

10 15 Number of tiers m

20

gradual(Subset)

multi-tier(SubsetL1 )

10

multi-tier(SubsetL2 ) (b) uniform(8)

101

5

10

15

20

100

5

10 15 Number of tiers m

15

20

10 15 Number of tiers m

20

(d) normal(2,4) 10

5

10

20

1

100

5

20

(d) grid(0.8)

Max MSE Ratio

10 15 Number of tiers m

GRR

1

100

101

5

10

Figure 14: Maximum MSE ratio result of LDP categorical queries with Subset mechanism and 𝑑 = 128 under random privacy lists (averaged over 500 simulations).

(c) grid(0.4) 101

100

multi-tier(SubsetL2 )

101

5

20

(c) normal(1,1)

(b) grid(0.2)

Max MSE Ratio

(a) grid(0.1) 101

10 15 Number of tiers m

Max MSE Ratio

100 5

Figure 11: Maximum MSE ratio result of LDP categorical queries with Subset mechanism and 𝑑 = 15. BRR

5

(d) normal(2,4)

101

Max MSE Ratio

10 15 Number of tiers m

100

(a) uniform(4)

101

5

20

20

(d) grid(0.8)

Max MSE Ratio

100

15

101

BRR (c) grid(0.4) 101

10

Figure 13: Maximum MSE ratio result of LDP categorical queries with Subset mechanism and 𝑑 = 15 under random privacy lists (averaged over 500 simulations).

multi-tier(SubsetL2 ) (b) grid(0.2)

Max MSE Ratio

(a) grid(0.1) 101

5

101

100

multi-tier(SubsetL2 )

101

(c) normal(1,1)

104 5

multi-tier(SubsetL1 )

(b) uniform(8)

101

105

5

gradual(Subset)

Max MSE Ratio

5

GRR (a) uniform(4)

104

107 Total MSE

the mean budget gets large (e.g., in uniform(8) and normal(2,4)) and the number of categories is relatively small (i.e., 𝑑 = 15).

106

105

10

multi-tier(SubsetL2 ) (b) uniform(8)

106

104

multi-tier(SubsetL1 )

(a) uniform(4)

Max MSE Ratio

107

Wang et al.

5

10 15 Number of tiers m

20

In summary, since our multi-tier Subset design tightly approximates its optimal hyper-parameters (i.e., subset size, privacy level) as in the single-tier Subset mechanism for all privacy levels through template generation, our proposals outperform baselines with a clear margin (both in total MSE and maximum MSE ratios).

Figure 12: Maximum MSE ratio result of LDP categorical queries with Subset mechanism and 𝑑 = 128.

7

proposals are below 2; the base GRR will always has large gap with our proposals, as base GRR performs much worse than Subset when 𝑑 is relative large even under large budget (e.g., 1 < 𝜖 < log(𝑑)). In random privacy lists, we present maximum MSE ratio results in Figures 13 and 14. The multi-tier, Subset𝐿2 is able to keep a low maximum ratio at ≤ 1.4, and the multi-tier, Subset𝐿1 has relatively large gap with it when the number of categories is low (i.e., 𝑑 = 15). As expected, the gap between BRR and multi-tier, Subset𝐿2 is moderate when the mean budget is relatively small (e.g., in normal(1,1) and uniform(4)), and the gap grows with the mean privacy budget. As contrast, the gap with GRR and multi-tier, Subset𝐿2 decreases when

Differentially private query mechanisms. Depending on the query types (e.g., discrete/continuous, one/multiple dimension, centralized/decentralized), plenty of base DP mechanisms are available in the literature. In the centralized curator model, for count and numerical summation queries, the Laplace mechanism [12] and the Gaussian mechanism [13] provide pure and approximate DP, respectively; the two-sided Geometric mechanism [16] further improves error rates for count query, and is universally optimal under sensitivity Δ = 1; the staircase mechanism [14] provides optimal utility for numerical summation queries; for selection queries (e.g., selecting the candidate with the maximum votes), the exponential mechanism [25] is a general tool for designing differentially private selection probabilities. In the local model of DP where each user

Related Works

Multi-tier Differential Private Query Release

sanitizes their own data, for count queries over categorical data, randomized response [34] and its variants [11, 21] are prevalent mechanisms, the local hash mechanism [33] improves communication efficiency by introducing shared randomness via hash functions, and the Subset mechanism [31, 32] provides optimal utility [37]; for numerical queries, several mechanisms [6, 11, 23, 30] provide optimal utility in the high privacy regime. Multi-tier DP queries. The idea of support multi-analyst DP query previously appears in database settings, such as for database queries [22, 41], dataset perturbation [36]. Specifically, the [22] provides a multi-tier realization of the Laplace mechanism, [41] uses multi-tier Gaussian noise adding, the [36] proposes re-sampling strategies for multi-tier randomized response. Nevertheless, these base DP mechanisms are known to be suboptimal. For example, in the high-privacy regime, Laplace mechanism exhibits an exponential error gap compared to the two-sided Geometric mechanism [16]; meanwhile, the binary randomized response [34] and general randomized response [21] perform significantly worse than the Subset mechanism [31] in the low-privacy and high-privacy regimes, respectively. In multi-analyst 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. A closely-related setting is accuracy-first DP query [15, 24, 35], which aims to minimize privacy losses upon satisfying the analyst’s accuracy criteria. It firstly releases a high-privacy result, then trace back to low-privacy result according to the accuracy requirements. The [24, 35] propose accuracy-first Laplace and Gaussian mechanisms, respectively, based on generating a continuous trace of the multi-tier transformation (e.g., in [22]) from the lowest-privacy result to higher privacy results. It is interesting to extend our multitier results for two-sided Geometric mechanism in Section 4 to the accuracy-first setting.

8

Conclusion

In this paper, we investigated the multi-tier DP query release problem, which is pervasive in data warehouses, mobile services, and data markets. For noise-adding DP mechanisms, we developed a general transformation framework via characteristic functions, provided concrete instantiations for count queries with two-sided Geometric noises, and demonstrated infeasible for some prevalent mechanisms (e.g., discrete Gaussian). Additionally, for the more challenging mapping-based DP mechanisms (commonly found in local DP), we provided a template-based multi-tier method and achieved optimal error rates for count queries with the Subset mechanism in local DP. Through extensive experiments, we numerically evaluated the effectiveness of our multi-tier DP proposals.

References [1] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. 2019. Hadamard response: Estimating distributions privately, efficiently, and with little communication. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 1120–1129. [2] Naman Agarwal, Peter Kairouz, and Ziyu Liu. 2021. The skellam mechanism for differentially private federated learning. Advances in neural information processing systems 34 (2021), 5052–5064. [3] Daniel Alabi, Sainyam Galhotra, Shagufta Mehnaz, Zeyu Song, and Eugene Wu. 2025. Privacy and security in distributed data markets. In Companion of the 2025 International Conference on Management of Data. 775–787.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

[4] Apple and Google. 2021. Exposure Notification Privacy-preserving Analytics white paper. (2021). https://covid19-static.cdn-apple.com/applications/covid19/ current/static/contact-tracing/pdf/ENPA_White_Paper.pdf. [5] Santiago Andrés Azcoitia and Nikolaos Laoutaris. 2022. A survey of data marketplaces and their business models. ACM SIGMOD Record 51, 3 (2022), 18–29. [6] Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. 2018. Protection against reconstruction and its applications in private federated learning. arXiv preprint arXiv:1812.00984 (2018). [7] David Blackwell. 1953. Equivalent comparisons of experiments. The annals of mathematical statistics (1953), 265–272. [8] Salomon Bochner. 2005. Harmonic analysis and the theory of probability. Courier Corporation. [9] Clément L Canonne, Gautam Kamath, and Thomas Steinke. 2020. The discrete gaussian for differential privacy. Advances in Neural Information Processing Systems 33 (2020), 15676–15688. [10] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting telemetry data privately. Advances in neural information processing systems 30 (2017). [11] John C Duchi, Michael I Jordan, and Martin J Wainwright. 2018. Minimax optimal procedures for locally private estimation. J. Amer. Statist. Assoc. 113, 521 (2018), 182–201. [12] Cynthia Dwork. 2006. Differential privacy. In International colloquium on automata, languages, and programming. Springer, 1–12. [13] Cynthia Dwork. 2008. Differential privacy: A survey of results. In International conference on theory and applications of models of computation. Springer, 1–19. [14] Quan Geng and Pramod Viswanath. 2015. Staircase mechanism in differential privacy. In IEEE International Symposium on Information Theory. 2376–2380. [15] Badih Ghazi, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. 2025. Private Hyperparameter Tuning with Ex-Post Guarantee. In The Thirty-ninth Annual Conference on Neural Information Processing Systems. [16] Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. 2012. Universally utility-maximizing privacy mechanisms. SIAM J. Comput. 41, 6 (2012), 1673–1693. [17] Charlie Harrison and Pasin Manurangsi. 2025. Infinitely Divisible Noise for Differential Privacy: Nearly Optimal Error in the High 𝜀 Regime. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Schloss Dagstuhl–LeibnizZentrum für Informatik, 12–1. [18] Apple Inc. 2017. Differential Privacy. https://www.apple.com/privacy/docs/ Differential_Privacy_Overview.pdf. [Accessed 29-03-2026]. [19] Google Inc. 2024. Advances in private training for production on-device language models — research.google. https://research.google/blog/advances-in-privatetraining-for-production-on-device-language-models/. [Accessed 28-03-2026]. [20] Google Inc. 2024. Improving Gboard language models via private federated analytics — research.google. https://research.google/blog/improving-gboardlanguage-models-via-private-federated-analytics/. [Accessed 28-03-2026]. [21] Peter Kairouz, Keith Bonawitz, and Daniel Ramage. 2016. Discrete distribution estimation under local privacy. In International Conference on Machine Learning. PMLR, 2436–2444. [22] Fragkiskos Koufogiannis, Shuo Han, and George J Pappas. 2016. Gradual Release of Sensitive Data under Differential Privacy. Journal of Privacy and Confidentiality 7, 2 (2016). [23] Zitao Li, Tianhao Wang, Milan Lopuhaä-Zwakenberg, Ninghui Li, and Boris Škoric. 2020. Estimating numerical distributions under local differential privacy. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 621–635. [24] Katrina Ligett, Seth Neel, Aaron Roth, Bo Waggoner, and Steven Z Wu. 2017. Accuracy first: Selecting a differential privacy level for accuracy constrained erm. Advances in Neural Information Processing Systems 30 (2017). [25] Frank McSherry and Kunal Talwar. 2007. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07). IEEE, 94–103. [26] Ilya Mironov. 2012. On significance of the least significant bits for differential privacy. In Proceedings of the 2012 ACM conference on Computer and communications security. 650–661. [27] Yury Polyanskiy and Yihong Wu. 2022. Information Theory: From Coding to Learning. Cambridge University Press. https://people.lids.mit.edu/yp/homepage/ data/itbook-export.pdf. [28] Ryan Rogers, Subbu Subramaniam, Sean Peng, David Durfee, Seunghyun Lee, Santosh Kumar Kancha, Shraddha Sahay, and Parvez Ahammad. 2021. LinkedIn’s Audience Engagements API: A Privacy Preserving Data Analytics System at Scale. Journal of Privacy and Confidentiality 11, 3 (2021). [29] Neil G Shephard. 1991. From Characteristic Function to Distribution Function: A Simple Framework for theTheory. Econometric theory 7, 4 (1991), 519–529. [30] Ning Wang, Xiaokui Xiao, Yin Yang, Jun Zhao, Siu Cheung Hui, Hyejin Shin, Junbum Shin, and Ge Yu. 2019. Collecting and analyzing multidimensional data with local differential privacy. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 638–649.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

[31] Shaowei Wang, Liusheng Huang, Yiwen Nie, Xinyuan Zhang, Pengzhan Wang, Hongli Xu, and Wei Yang. 2019. Local differential private data aggregation for discrete distribution estimation. IEEE Transactions on Parallel and Distributed Systems 30, 9 (2019), 2046–2059. [32] Shaowei Wang, Liusheng Huang, Pengzhan Wang, Yiwen Nie, Hongli Xu, Wei Yang, Xiang-Yang Li, and Chunming Qiao. 2016. Mutual information optimally local private discrete distribution estimation. arXiv preprint arXiv:1607.08025 (2016). [33] Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. 2017. Locally differentially private protocols for frequency estimation. In 26th USENIX security symposium (USENIX Security 17). 729–745. [34] Stanley L Warner. 1965. Randomized response: A survey technique for eliminating evasive answer bias. J. Amer. Statist. Assoc. (1965). [35] Justin Whitehouse, Aaditya Ramdas, Steven Z Wu, and Ryan M Rogers. 2022. Brownian noise reduction: Maximizing privacy subject to accuracy constraints. Advances in Neural Information Processing Systems 35 (2022), 11217–11228. [36] Xiaokui Xiao, Yufei Tao, and Minghua Chen. 2009. Optimal random perturbation at multiple privacy levels. Proc. VLDB Endow. 2, 1 (2009), 814–825. [37] Min Ye and Alexander Barg. 2018. Optimal schemes for discrete distribution estimation under locally differential privacy. IEEE Transactions on Information Theory 64, 8 (2018), 5662–5676. [38] NIE Yiwen, Wei Yang, Liusheng Huang, Xike Xie, Zhenhua Zhao, and Shaowei Wang. 2018. A utility-optimized framework for personalized private histogram estimation. IEEE Transactions on Knowledge and Data Engineering 31, 4 (2018), 655–669. [39] Haifei Yu and Mengxiao Zhang. 2017. Data pricing strategy based on data quality. Computers & Industrial Engineering 112 (2017), 1–10. [40] Bing Zhang, Vadym Doroshenko, Peter Kairouz, Thomas Steinke, Abhradeep Thakurta, Ziyin Ma, Eidan Cohen, Himani Apte, and Jodi Spacek. 2024. Differentially Private Stream Processing at Scale. Proceedings of the VLDB Endowment 17, 12 (2024), 4145–4158. [41] Shufan Zhang and Xi He. 2023. DProvDB: Differentially private query processing with multi-analyst provenance. Proceedings of the ACM on Management of Data 1, 4 (2023), 1–27.

A

Wang et al.

B

Now consider two cases: Case 1 (𝑥 ∈ 𝑆 ′ ): There is exactly one element 𝑦 = 𝑥 in 𝑆 ′ such that 𝑥 ∈ 𝑆 ′ \ {𝑦} (when 𝑦 ≠ 𝑥), and for 𝑦 = 𝑥, we have 𝑥 ∉ 𝑆 ′ \ {𝑥 }. Using the probability distribution of 𝑆𝑢𝑏𝑠𝑒𝑡 (𝑥, 𝑘, 𝜖):   ∑︁  1  ′ ′  Pr[𝑟 ′ =𝑆 ′ |𝑥] = Pr[𝑟 =𝑆 \{𝑥 }|𝑥] + Pr[𝑟 =𝑆 \{𝑦}|𝑥]   𝑑 −𝑘   𝑦 ∈𝑆 ′ ,𝑦≠𝑥 "  # 1 𝑒𝜖 1 =

+ 𝑘 · 𝑑 −1
𝜖
𝑑 − 𝑘 𝑑 −1 𝑒 𝜖 + 𝑑 −1 𝑒 + 𝑑 −1 𝑘 −1

(1) setting 𝑟𝑖 ∗ as the input; (2) sequentially, for 𝑖 ′ ∈ [𝑖 ∗ + 1, max 𝑆], drawing an residual noise 𝑠𝑖 ′ −1 according to Equation 1, and set 𝑟𝑖 ′ = 𝑟𝑖 ′ −1 + 𝑠𝑖 ′ −1 ; (3) return results {𝑟𝑖 }𝑖 ∈ [𝑖 ∗ ,max 𝑆 ]\𝑆 that the indices are in 𝑆. The residual noises 𝑠𝑖 ′ −1 are predetermined and do not depend on the dataset. Therefore 𝑓 is a fixed Markov kernel that does not use any additional information about 𝑋 or 𝑋 ′ . By construction, for any dataset 𝑋 , we have d

M𝑆 (𝑋, 𝐿) = 𝑓 (M {𝑖 ∗ } (𝑋, 𝐿)), because the mechanism generates 𝑟𝑖 ∗ first and then produces all later 𝑟𝑖 via the same additive residual noises. The same holds for 𝑋 ′ . Applying the data processing inequality to the post-processing function 𝑓 yields

𝐷 M𝑆 (𝑋, 𝐿) M𝑆 (𝑋 ′, 𝐿) ≤ 𝐷 M {𝑖 ∗ } (𝑋, 𝐿) M {𝑖 ∗ } (𝑋 ′, 𝐿) . Thus the desired inequality holds.

𝑘 −1

𝑘

𝑘

1 + 𝑘𝑒 𝜖 𝑑 −1
𝜖 𝑑 −1
𝑘 −1 𝑒 + 𝑘 (1 + 𝑘𝑒 𝜖 )/(𝑘 + 1) = 𝑑 −1
. 𝑑 −1
𝜖 𝑘 𝑒 + 𝑘+1 1 = · 𝑑 −𝑘

Case 2 (𝑥 ∉ 𝑆 ′ ): For all 𝑦 ∈ 𝑆 ′ , we have 𝑥 ∉ 𝑆 ′ \ {𝑦}, so: 1 ∑︁ Pr[𝑟 ′ = 𝑆 ′ |𝑥] = Pr[𝑟 = 𝑆 ′ \ {𝑦}|𝑥] 𝑑 − 𝑘 𝑦 ∈𝑆 ′

Proof of Theorem 4.1

if the algorithm fails at any step, it outputs nothing and the failure event is independent of the true query answer 𝑞(𝑋 ) or the dataset 𝐷, thus the total privacy loss is 0. When the algorithm succeed, for any neighboring datasets 𝑋, 𝑋 ′ and any 𝑆 ⊆ [𝑚], let M𝑆 denote the subset {𝑟𝑖 }𝑖 ∈𝑆 of the algorithm’s output {𝑟𝑖 }𝑖 ∈ [𝑚] with input 𝑞(𝑋 ), and let M𝑆′ denote the subset {𝑟𝑖 }𝑖 ∈𝑆 of the algorithm’s output {𝑟𝑖 }𝑖 ∈ [𝑚] with input 𝑞(𝑋 ′ ). Let 𝑖 ∗ = min 𝑆 (the smallest index in 𝑆, we define a post-processing function 𝑓 : Y ↦→ Y |𝑆 | as follows:

Proof of Lemma 5.1

For any subset 𝑆 ′ ⊆ [𝑑] of size 𝑘 + 1, the probability that 𝑟 ′ = 𝑆 ′ can be computed by considering which element was added during expansion. There are exactly 𝑘 + 1 possible ways that 𝑆 ′ could have been generated. Specifically, for each 𝑦 ∈ 𝑆 ′ , there is exactly one subset 𝑆 ′ \ {𝑦} of size 𝑘 that could have been expanded to 𝑆 ′ by adding 𝑦. Thus, we have: ∑︁ 1 Pr[𝑟 ′ = 𝑆 ′ |𝑥] = Pr[𝑟 = 𝑆 ′ \ {𝑦}|𝑥] · . 𝑑 − 𝑘 𝑦 ∈𝑆 ′

= =

𝑘 +1

1 · 𝑑 −𝑘

𝑑 −1
𝜖 𝑑 −1
𝑘 −1 𝑒 + 𝑘

1 𝑑 −1
𝜖 𝑑 −1
𝑘 𝑒 + 𝑘+1

.

Now, for the target distribution 𝑆𝑢𝑏𝑠𝑒𝑡 (𝑥, 𝑘 + 1, 𝜖 ′ ) with 𝜖 ′ = 𝜖 𝑘+1 ln( 𝑒 𝑘+1 ), we have: ′  𝑒𝜖   (𝑑 −1)𝑒 𝜖 ′ + (𝑑 −1)  𝑘 𝑘+1 Pr[𝑆 |𝑥] =   𝑑 −1 𝑒 𝜖1′ + 𝑑 −1 ( 𝑘+1 ) ( 𝑘 )

′

if 𝑥 ∈ 𝑆 ′ if 𝑥 ∉ 𝑆 ′

d

Therefore, 𝑟 ′ = 𝑆𝑢𝑏𝑠𝑒𝑡 (𝑥, 𝑘 + 1, ln((1 + 𝑘𝑒 𝜖 )/(𝑘 + 1))).

C

Proof of Lemma 5.2

Let 𝑟 ′ = Rescale(𝑟, 𝛽). For any subset 𝑆 ⊆ [𝑑] of size 𝑘, the probability that 𝑟 ′ = 𝑆 can be computed by considering the two cases in the rescale operation: 1 Pr[𝑟 ′ = 𝑆 |𝑥] = 𝛽 · Pr[𝑟 = 𝑆 |𝑥] + (1 − 𝛽) · 𝑑
. 𝑘

Now consider two cases: Case 1 (𝑥 ∈ 𝑆): Using the probability distribution of 𝑆𝑢𝑏𝑠𝑒𝑡 (𝑥, 𝑘, 𝜖): 𝑒𝜖 1 Pr[𝑟 ′ = 𝑆 |𝑥] = 𝛽 · 𝑑 −1
+ (1 − 𝛽) · 𝑑
𝑑 −1
𝜖 𝑘 −1 𝑒 + 𝑘 𝑘 1−𝛽 𝛽𝑒 𝜖 = 𝑑 −1
+ 𝑑
𝑑 −1
𝜖 𝑘 −1 𝑒 + 𝑘 𝑘

Multi-tier Differential Private Query Release

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Case 2 (𝑥 ∉ 𝑆):

Consequently, we have:

Pr[𝑟 ′ = 𝑆 |𝑥] = 𝛽 · =

1 𝑑 −1
𝜖 𝑑 −1
𝑘 −1 𝑒 + 𝑘

𝛽 𝑑 −1
𝜖 𝑘 −1 𝑒 +

+ (1 − 𝛽) ·

1 𝑑
𝑘

1−𝛽 + 𝑑
𝑑 −1
𝑘

𝑘

The new probability ratio is then: 𝛽𝑒 𝜖 1−𝛽 𝑁 + 𝑀 1−𝛽 𝛽 𝑁 + 𝑀

=

𝑁 𝛽𝑒 𝜖 + 𝑀 (1 − 𝛽) 𝑁 (1 − 𝛽) 𝛽+𝑀

−1
𝜖 𝑁 where 𝑁 = 𝑑𝑘 −1 𝑒 + 𝑑 𝑘−1 and 𝑀 = 𝑑𝑘 . Using the identity 𝑀 = 𝑑 −1 𝑑 −𝑘 𝜖 (𝑘 −1) (𝑒 + 𝑘 ) 𝑘 𝜖 𝑑 −𝑘 𝑘𝑒 𝜖 +𝑑 −𝑘 = 𝑑 (𝑒 + 𝑘 ) = , we get the new privacy 𝑑 (𝑑𝑘 ) ′ level 𝜖 as: 𝑑𝛽𝑒 𝜖 + (1 − 𝛽)(𝑘𝑒 𝜖 + 𝑑 − 𝑘) ′ 𝑒𝜖 = 𝑑𝛽 + (1 − 𝛽)(𝑘𝑒 𝜖 + 𝑑 − 𝑘)

D

Proof of Theorem 5.3

Let 𝑘𝑖∗ denote the optimal subset size for the 𝜖𝑖 , we consider 4 cases about the privacy budget 𝜖𝑖 . Case 1: In the case of 𝜖𝑖 > ln(𝑑 −1), we have 𝑘𝑖∗ ≡ 1. It is handled in the step 1 with only rescale operations, then the corresponding result 𝑠 is distributionally equivalent to 𝑆𝑢𝑏𝑠𝑒𝑡 (𝜖𝑖 , 1). Therefore, we have E[∥𝑆𝑢𝑏𝑠𝑒𝑡𝑖𝐿 − 𝑥 ∥ 22 ] = 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ). Case 2: In the case of ln(𝑑 − 1) ≥ 𝜖𝑖 ≥ ln(𝑑/⌊(𝑑 − 1)/2⌋), we have ⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ ≥ 𝑘𝑖∗ ≥ ⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋. It is handled in the step 2 by the generated templates in Algorithm 3, the corresponding result 𝑠 has either size ⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋ (with tight privacy budget ln(𝑑/⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋ − 1)) or size ⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ (with tight privacy budget ln(𝑑/⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ − 1)). Since the following two inequality holds:

E[∥𝑆𝑢𝑏𝑠𝑒𝑡𝑖𝐿 − 𝑥 ∥ 22 ] ≤𝑉 (ln(𝑑/⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ − 1), ⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉) 𝑉 (ln(𝑑/⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ − 1), ⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉) · 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ) 𝑉 (ln(𝑑/⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋ − 1), ⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋) (7𝑑 − 16)(𝑑 − 2) 2 ≤ · 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ) (3𝑑 − 4)(𝑑 − 4) 2 (7 · 5 − 16)(5 − 2) 2 ≤ · 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ) (3 · 5 − 4)(5 − 4) 2 171 ≤ · 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ) 11 ≤

Case 3: In the case of 𝑑 is even and ln(𝑑/⌊(𝑑 − 1)/2⌋ − 1) > 𝜖𝑖 ≥ ln((𝑑 + 2)/⌊𝑑/2⌋ − 1). Note that this case only applies to when 𝑑 is even and 𝑑 ≥ 4. It is handled at the start of Step 3 (see lines 8-10 in Algorithm 2), and the corresponding result will matches to the resulting 𝑠 at line 10. Therefore, the following two inequalities hold: 𝑉 (ln((𝑑 + 2)/⌊𝑑/2⌋ − 1), ⌊𝑑/2⌋) ≥ 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ); 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ) ≥ 𝑉 (ln(𝑑/⌊(𝑑 − 1)/2⌋ − 1), ⌊(𝑑 − 1)/2⌋). Notice that when 𝑑 is even and 𝑑 ≥ 4 (the subcase 𝑑 = 2 is trivial as the optimal subset size is always 1), we have: 𝑉 (ln((𝑑 + 2)/⌊𝑑/2⌋ − 1), ⌊𝑑/2⌋) 𝑉 (ln(𝑑/⌊(𝑑 − 1)/2⌋ − 1), ⌊(𝑑 − 1)/2⌋) 𝑉 (ln(2(𝑑 + 2)/𝑑 − 1), 𝑑/2) = 𝑉 (ln(2𝑑/(𝑑 − 2) − 1), (𝑑 − 2)/2) 2 2(3 + 𝑑) =1 + + 𝑑 𝑑 (𝑑 − 1) − 4 2 2(3 + 4) ≤1 + + 4 4(4 − 1) − 4 ≤13/4.

𝑉 (ln(𝑑/⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ − 1), ⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉) ≥ 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ); 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ) ≥ 𝑉 (ln(𝑑/⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋ − 1), ⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋). −1),𝑘+1) Now consider a formula 𝑉 (ln(𝑑/(𝑘+1) , we have: 𝑉 (ln(𝑑/𝑘 −1),𝑘 )

Consequently, we have: 𝑉 (ln(𝑑/(𝑘 + 1) − 1), 𝑘 + 1) 𝑉 (ln(𝑑/𝑘 − 1), 𝑘) −4(1 + 𝑘) 2 + 𝑑 (3 + 4𝑘) . −4𝑘 2 + 𝑑 (−1 + 4𝑘) = . (𝑑 − 2(1 + 𝑘)) 2 (𝑑 − 2𝑘) 2 Let 𝐹 (𝑘) = ln( 𝜕𝐹 𝜕𝑘

≥ 0, √

𝜕2 𝐹 𝜕𝑘 2

−4𝑘 2 +𝑑 (−1+4𝑘 )

), for 𝑘 ∈ [1, ⌊(𝑑 − 1)/2⌋], we have √ 2 3𝑑 − 3(𝑑 2 −𝑑 ) ≤ 0 when 𝑘 ≤ , and 𝜕𝜕𝑘𝐹2 ≥ 0 when 6 (𝑑 −2𝑘 ) 2

3𝑑 − 3(𝑑 2 −𝑑 ) . Therefore, when ⌊(𝑑 − 1)/2⌋ ≥ 2 (i.e., 𝑑 ≥ 5), we 6

𝑘≥ have:

𝑉 (ln(𝑑/(𝑘 + 1) − 1), 𝑘 + 1) 𝑉 (ln(𝑑/𝑘 − 1), 𝑘) ≤ exp(𝐹 (𝑘 + 1) − 𝐹 (𝑘)) ≤ max{exp(𝐹 (2) − 𝐹 (1)), exp(𝐹 (⌊(𝑑 − 1)/2⌋) − 𝐹 (⌊(𝑑 − 1)/2⌋ − 1))} ≤

(7𝑑 − 16) (𝑑 − 2) 2 . (3𝑑 − 4) (𝑑 − 4) 2

E[∥𝑆𝑢𝑏𝑠𝑒𝑡𝑖𝐿 − 𝑥 ∥ 22 ] ≤𝑉 (ln((𝑑 + 2)/⌊𝑑/2⌋ − 1), ⌊𝑑/2⌋) 𝑉 (ln((𝑑 + 2)/⌊𝑑/2⌋ − 1), ⌊𝑑/2⌋) · 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ) 𝑉 (ln(𝑑/⌊(𝑑 − 1)/2⌋ − 1), ⌊(𝑑 − 1)/2⌋) 2 2(3 + 𝑑) ≤(1 + + ) · 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ) 𝑑 𝑑 (𝑑 − 1) 13 ≤ · 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ). 4 ≤

Case 4: In the case of 𝜖𝑖 < ln((𝑑 + 2)/⌊𝑑/2⌋ − 1) (if 𝑑 is even) or 𝑒 𝜖𝑖 + 1 < 𝑑/⌊(𝑑 − 1)/2⌋ (if 𝑑 is odd), we have 𝑘𝑖∗ = ⌊𝑑/2⌋ (if 𝑑 is even) or 𝑘𝑖∗ = ⌊(𝑑 − 1)/2⌋ (if 𝑑 is odd). It is handled in the Step 4, with only rescale operations, then the corresponding result 𝑠 is distributionally equivalent to 𝑆𝑢𝑏𝑠𝑒𝑡 (𝜖𝑖 , 𝑘𝑖∗ ). Therefore, we have E[∥𝑆𝑢𝑏𝑠𝑒𝑡𝑖𝐿 − 𝑥 ∥ 22 ] = 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ). In summary, we have the conclusion.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

E

Wang et al.

Proof of Theorem 5.4

even and 𝑑 ≥ 4. It is handled at the start of Step 3 (see lines 7-9 in Algorithm 2), and will match to the resulting 𝑠 at line 9. Therefore, the following two inequalities hold:

For any 𝑘, 𝑘 + 1 ∈ [𝑑], we have: 𝑉 (𝜖, 𝑘) − 𝑉 (𝜖, 𝑘 + 1) =

𝑉 (ln((𝑑 + 2)/⌊𝑑/2⌋ − 1), ⌊𝑑/2⌋) ≥ 𝑉 (𝜖𝑖 , 𝑘𝑖∗ );

(𝑑 − 1) 2 𝑑 2 − 𝑑 (2𝑘 + 1) − 𝑒 2𝜖 − 1 𝑘 (𝑘 + 1)

𝑉 (𝜖𝑖 , 𝑘𝑖∗ ) ≥ 𝑉 (ln(𝑑/⌊(𝑑 − 1)/2⌋ − 1), ⌊(𝑑 − 1)/2⌋).

, (𝑒 𝜖 − 1) 2 𝑘 (𝑘 + 1)(𝑑 − 𝑘 − 1)(𝑑 − 𝑘)

which implies that the optimal subset size 𝑘 ∗ is non-increasing with 𝜖 and the equality holds when: ! √︂ 𝑑 −𝑘 𝑑 −𝑘 −1 𝜖 (𝑘 ) = log · (3) 𝑘 𝑘 +1 Let 𝑘𝑖∗ denote the optimal subset size for the 𝜖𝑖 , we now consider 4 cases about the privacy budget 𝜖𝑖 . Case 1: In the case of 𝜖𝑖 > ln(𝑑 −1), we have 𝑘𝑖∗ ≡ 1. It is handled in the step 1 with only rescale operations, then the corresponding result 𝑠 is distributionally equivalent to 𝑆𝑢𝑏𝑠𝑒𝑡 (𝜖𝑖 , 1). Therefore, we have E[∥𝑆𝑢𝑏𝑠𝑒𝑡 1𝐿 (𝑥)𝑖 − 𝑥 ∥ 22 ] = 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ). Case 2: In the case of ln(𝑑 −1) ≥ 𝜖𝑖 ≥ ln(𝑑/⌊(𝑑 −1)/2⌋), we have ⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ ≥ 𝑘𝑖∗ ≥ ⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋, and there are three subcases: (I) In the first subcase that ⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ = ⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋, both values equal to 𝑘 ∗ and the matched result coresponds to the template with budget ln(𝑑/𝑘 ∗ − 1), thus E[∥𝑆𝑢𝑏𝑠𝑒𝑡 2𝐿 (𝑥)𝑖 − 𝑥 ∥ 22 ] = 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ). (II) In the second subcase that ⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ > ⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋ and ln((𝑑 + 1)/⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ − 1) ≥ 𝜖𝑖 ≥ ln(𝑑/⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ − 1), it is handled by the lines 9-13. Since 𝜖 ( ⌊𝑑/(𝑒 𝜖𝑖 +1) ⌋ ) ≥ ln((𝑑 +1)/⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ − 1), we have 𝑉 (𝜖𝑖 , ⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉) ≤ 𝑉 (𝜖𝑖 , ⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋), the 𝑘 ∗ = ⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ is an optimal subset size for 𝜖𝑖 . Consequently, the matched result for 𝜖𝑖 at the lines 9-13 is distributionally equivalent to 𝑆𝑢𝑏𝑠𝑒𝑡 (𝑑, ⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉, 𝜖𝑖 ), and thus E[∥𝑆𝑢𝑏𝑠𝑒𝑡 2𝐿 (𝑥)𝑖 − 𝑥 ∥ 22 ] = 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ). (III) In the third subcase that ⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ > ⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋ and ln(𝑑/⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋ − 1) ≥ 𝜖𝑖 ≥ ln((𝑑 − 1)/⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋ − 1), it is also handled by the lines 9-13. Since ln((𝑑 − 1)/⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋ − 1) ≥ 𝜖 ( ⌊𝑑/(𝑒 𝜖𝑖 +1) ⌋ ) , we have 𝑉 (𝜖𝑖 , ⌈𝑑/(𝑒 𝜖𝑖 +1)⌉) ≥ 𝑉 (𝜖𝑖 , ⌊𝑑/(𝑒 𝜖𝑖 +1)⌋), the 𝑘 ∗ = ⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋ is an optimal subset size for 𝜖𝑖 . Consequently, the matched result for 𝜖𝑖 at the lines 9-13 is distributionally equivalent to 𝑆𝑢𝑏𝑠𝑒𝑡 (𝑑, ⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋, 𝜖𝑖 ), and thus E[∥𝑆𝑢𝑏𝑠𝑒𝑡 2𝐿 (𝑥)𝑖 − 𝑥 ∥ 22 ] = 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ). (IV) In the fourth subcase that ⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ > ⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋ and ln((𝑑 − 1)/⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋ − 1) > 𝜖𝑖 > ln((𝑑 + 1)/⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ − 1). It will be matched to a result with budget ln((𝑑 + 1)/⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ − 1) and subset size ⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉. Since following two inequalities hold: 𝑉 (ln((𝑑 + 1)/⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉ − 1), ⌈𝑑/(𝑒 𝜖𝑖 + 1)⌉) ≥ 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ); 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ) ≥ 𝑉 (ln((𝑑 − 1)/⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋ − 1), ⌊𝑑/(𝑒 𝜖𝑖 + 1)⌋), we have: E[∥𝑆𝑢𝑏𝑠𝑒𝑡 2𝐿 (𝑥)𝑖 − 𝑥 ∥ 22 ] 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ) 𝑉 (ln((𝑑 + 1)/(𝑘 + 1) − 1), 𝑘 + 1) ≤ 𝑉 (ln((𝑑 − 1)/𝑘 − 1), 𝑘) (𝑑 − 𝑘) (2 + 𝑑 2 (3 + 4𝑘) + 𝑘 (7 + 4𝑘 (2 + 𝑘)) − 𝑑 (5 + 𝑘 (11 + 8𝑘))) = . (1 − 𝑑 + 𝑘) 2 (1 − 4𝑘 2 + 𝑑 (−1 + 4𝑘)) In the theorem, we use the formula with 𝑘 = ⌈𝑑/(𝑒𝑖𝜖 + 1)⌉ − 1. Case 3: In the case of 𝑑 is even and ln(𝑑/⌊(𝑑 − 1)/2⌋ − 1) > 𝜖𝑖 ≥ ln((𝑑 + 2)/⌊𝑑/2⌋ − 1). Note that this case only applies to when 𝑑 is

Notice that when 𝑑 is even and 𝑑 ≥ 4 (the subcase 𝑑 = 2 is trivial as the optimal subset size is always 1), we have: 𝑉 (ln((𝑑 + 2)/⌊𝑑/2⌋ − 1), ⌊𝑑/2⌋) 𝑉 (ln(𝑑/⌊(𝑑 − 1)/2⌋ − 1), ⌊(𝑑 − 1)/2⌋) 𝑉 (ln(2(𝑑 + 2)/𝑑 − 1), 𝑑/2) = 𝑉 (ln(2𝑑/(𝑑 − 2) − 1), (𝑑 − 2)/2) 2 2(3 + 𝑑) =1 + + 𝑑 𝑑 (𝑑 − 1) − 4 2(3 + 4) 2 ≤1 + + 4 4(4 − 1) − 4 ≤13/4. Consequently, we have: E[∥𝑆𝑢𝑏𝑠𝑒𝑡𝑖𝐿 − 𝑥 ∥ 22 ] ≤𝑉 (ln((𝑑 + 2)/⌊𝑑/2⌋ − 1), ⌊𝑑/2⌋) 𝑉 (ln((𝑑 + 2)/⌊𝑑/2⌋ − 1), ⌊𝑑/2⌋) · 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ) 𝑉 (ln(𝑑/⌊(𝑑 − 1)/2⌋ − 1), ⌊(𝑑 − 1)/2⌋) 2 2(3 + 𝑑) ≤(1 + + ) · 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ) 𝑑 𝑑 (𝑑 − 1) 13 ≤ · 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ). 4 Case 4: In the case of 𝜖𝑖 < ln((𝑑 + 2)/⌊𝑑/2⌋ − 1) (if 𝑑 is even) or 𝑒 𝜖𝑖 + 1 < 𝑑/⌊(𝑑 − 1)/2⌋ (if 𝑑 is odd), we have 𝑘𝑖∗ = ⌊𝑑/2⌋ (if 𝑑 is even) or 𝑘𝑖∗ = ⌊(𝑑 − 1)/2⌋ (if 𝑑 is odd). It is handled in the Step 4, with only rescale operations, then the corresponding result 𝑠 is distributionally equivalent to 𝑆𝑢𝑏𝑠𝑒𝑡 (𝜖𝑖 , 𝑘𝑖∗ ). Therefore, we have E[∥𝑆𝑢𝑏𝑠𝑒𝑡𝑖𝐿 − 𝑥 ∥ 22 ] = 𝑉 (𝜖𝑖 , 𝑘𝑖∗ ). In summary, we have the conclusion. ≤

F

Non-existence of Multi-tier Staircase Mechanism

In the staircase mechanism [14] for one-dimensional numerical queries with sensitivity Δ, the noise distribution is as follows :  𝑎(𝛾), 0 ≤ 𝑦 < 𝛾 Δ,      −𝜖  𝛾 Δ ≤ 𝑦 < Δ, 𝑎(𝛾)𝑒 ,  Pr[SC(𝜖) =𝑦] =   𝑒 −𝑘𝜖 Pr[SC(𝜖) =𝑦 −𝑘Δ], 𝑦 ∈ [𝑘Δ, (𝑘 +1)Δ), 𝑘 ∈ Z ≥0,       Pr[SC(𝜖) = −𝑦], 𝑦 < 0,  (4) where the normalization factor 1 − 𝑒 −𝜖 𝑎(𝛾) = , (5) 2Δ (𝛾 + 𝑒 −𝜖 (1 − 𝛾)) and the hyperparameter 𝛾 = 1/(𝑒 𝜖/2 + 1). Its characteristic function is:        Δ𝑡 1 𝑒 −3𝜖2 (𝑒 𝜖 − 1) 2 𝑒 𝜖 sin 𝑒 𝜖/2 + sin Δ 1 − 𝑡 𝜖/2 +1 𝑒 +1 Φ𝜖 (𝑡) := , 2Δ𝑡 (cosh(𝜖) − cos(Δ𝑡))

Multi-tier Differential Private Query Release

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

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   𝑀 := 𝑀𝑎,𝑏 𝑎,𝑏 ∈ [𝐶 ] , 𝑀𝑎,𝑏 := 𝑅(𝑡𝑎 − 𝑡𝑏 ), must be Hermitian positive semi-definite. Equivalently, all eigenvalues of 𝑀 must be non-negative. We construct a counterexample for the residual function 𝑅(𝑡) = Φ𝜖𝑖+1 (𝑡)/Φ𝜖𝑖 (𝑡) with 𝜖𝑖 = 2.8 and 𝜖𝑖+1 = 1. When 𝑡 takes values in {5𝜋 · (𝑘 −1)}𝑘 ∈ [2] , the Bochner matrix 𝑀 ∈ C2×2 with entries 𝑀𝑎,𝑏 = 𝑅(𝑡𝑎 − 𝑡𝑏 ) are as follow:   1 −1.43887 −1.43887 1 It has a smallest eigenvalue of approximately −0.43887 < 0. Therefore, 𝑀 is not positive semi-definite, the Φ𝜖𝑖+1 (𝑡)/Φ𝜖𝑖 (𝑡) is not a valid characteristic function, and no additive noise can transform from SC(2.8)) to SC(1.0).

G

Multi-tier Local Hash Mechanism

In this section, we extend the template-based framework to the Local Hash (LH) mechanism [33]. In LH, the domain [𝑑] is mapped to a smaller domain [𝑔] via a hash function, where the optimal 𝑔 depends on the privacy budget 𝜖 (e.g., 𝑔∗ = ⌊𝑒 𝜖 + 1⌋). To facilitate multi-tier transitions, we restrict the hash domain size to powers of two, i.e., 𝑔 ∈ {2𝑘 | 𝑘 ∈ Z+ }. Hierarchical Hash Functions. Let 𝐾 = ⌊log2 (𝑒 𝜖1 + 1)⌋ be the initial domain exponent for the highest privacy budget 𝜖1 . We define 𝐾 . Starting from a sequence of hash functions {𝐻𝑘 : [𝑑] → [2𝑘 ]}𝑘=1 a base universal hash function 𝐻𝐾 , the subsequent functions are defined as:

𝜖

𝑝 + 𝑞 = 𝑒 𝜖𝑒+2+1 𝑘 −1 . The probability of hitting any incorrect value 𝑧 ≠ 𝐻𝑘 −1 (𝑥) is 2𝑞 = 𝑒 𝜖 +22𝑘 −1 . The new privacy budget 𝜖 ′ satisfies ′

for 𝑘 = 𝐾, 𝐾 − 1, . . . , 2.

𝑑

𝐻𝑘 (i.e., 𝑟 = 𝐿𝐻 (𝑥, 2𝑘 , 𝐻𝑘 , 𝜖)). The merged result 𝑟 ′ = Merge(𝑟 ) is distributionally equivalent to an LH output over domain [2𝑘 −1 ] with budget 𝜖 ′ = ln((𝑒 𝜖 + 1)/2). That is, Merge(𝑟 ) = 𝐿𝐻 (𝑥, 2𝑘 −1, 𝐻𝑘 −1, ln((𝑒 𝜖 + 1)/2)). 𝑑

𝜖

𝑒 Proof. In the original domain [2𝑘 ], let 𝑝 = 𝑒 𝜖 +2 𝑘 −1 and 𝑞 = 1 ′ ∈ [2𝑘 −1 ], the probability of hitting the correct hash . For 𝑟 𝑒 𝜖 +2𝑘 −1 value is: Pr[𝑟 ′ = 𝐻𝑘 −1 (𝑥)] = Pr[𝑟 ∈ {2𝐻𝑘 −1 (𝑥) − 1, 2𝐻𝑘 −1 (𝑥)}] =

□

𝑑

Multi-ter Implementation. Build upon previous results, we present the the Multi-tier Local Hash mechanism in Algorithm 6, which generates middle-regime templates at reference levels where 𝑒 𝜖 = 2𝑘 − 1 for 𝑘 ∈ [2, 𝐾].

Algorithm 6: Multi-tier Local Hash Mechanism 𝐿𝐻 𝐿 (𝑥) Input : Privacy list 𝐿 = {𝜖1, . . . , 𝜖𝑚 }; true value 𝑥 ∈ [𝑑] Output : Query results {𝑟𝑖 }𝑖 ∈ [𝑚] // 1. Handle highest budget 𝜖 1 𝐾 ← ⌊log2 (𝑒 1 + 1)⌋ 𝐾 2 𝑠 ← LH(𝑥, 2 , 𝐻𝐾 , 𝜖 1 ) 𝜖 3 𝜌 ←𝑒 1 4 𝑅 ← {(𝜖 1 , 𝑠, 𝐾)} 5 𝑘 ←𝐾 // 2. Generate middle-budget templates 6 while 𝑘 > 1 do 7 𝜌 ′ ← 2𝑘 − 1 8 if 𝜌 > 𝜌 ′ then 10 11 12 13

(𝜌 ′ −1) (𝜌+2𝑘 −1)

𝑠 ← Rescale(𝑠, 𝑑 (𝜌 −𝜌 ′ ) 𝜌 ← 𝜌′ append (ln 𝜌, 𝑠, 𝑘) to 𝑅

)

𝑠 ← Merge(𝑠); 𝜌 ← (𝜌 + 1)/2; 𝑘 ←𝑘 −1

// 3. Handle low budget regime (k=1) append (ln 𝜌, 𝑠, 𝑘) to 𝑅 𝜖 15 for 𝜖𝑖 ∈ 𝐿 where 𝑒 𝑖 < 𝜌 do ′ 𝜖 𝑖 16 𝜌 ←𝑒 14

17 18 19

Lemma G.1 (Properties of Merge Operation). Let 𝑟 ∈ [2𝑘 ] be the output of a LH mechanism with budget 𝜖 using hash function

𝜖

𝐻𝑘 (i.e., 𝑟 = 𝐿𝐻 (𝑥, 2𝑘 , 𝐻𝑘 , 𝜖)). Then Rescale(𝑟, 𝛽) satisfies 𝜖 ′ -LDP with:   𝑘 𝜖  2 𝛽𝑒 + (1 − 𝛽)(𝑒 𝜖 + 2𝑘 − 1) 𝑑 Rescale(𝑟, 𝛽) = 𝐿𝐻 𝑥, 2𝑘 , 𝐻𝑘 , ln . 2𝑘 𝛽 + (1 − 𝛽)(𝑒 𝜖 + 2𝑘 − 1)

(6)

This construction ensures that if 𝐻𝑘 (𝑥) = 𝑗, then its projection in the smaller domain [2𝑘 −1 ] is deterministically 𝐻𝑘 −1 (𝑥). Primitive Operators: Pertained to the LH mechanism, we define two operators for adapting the hash domain size and privacy levels: • Merge Operator: Given a result 𝑟 ∈ [2𝑘 ] (𝑘 > 1), Merge(𝑟 ) := ⌈𝑟 /2⌉ ∈ [2𝑘 −1 ]. This operator effectively merges two adjacent hash buckets. • Rescale Operator: Given 𝑟 ∈ [2𝑘 ] with budget 𝜖, the operator Rescale(𝑟, 𝛽) outputs 𝑟 with probability 𝛽, and with probability 1 − 𝛽 samples a value uniformly from [2𝑘 ].

𝑝+𝑞

Lemma G.2 (Properties of Rescale Operation). Let 𝑟 ∈ [2𝑘 ] be the output of a LH mechanism with budget 𝜖 using hash function

9

𝐻𝑘 −1 (𝑥) = ⌈𝐻𝑘 (𝑥)/2⌉,

𝜖

𝑒 𝜖 = 2𝑞 = 𝑒 2+1 . Thus, 𝜖 ′ = ln( 𝑒 2+1 ).

(𝜌 ′ −1) (𝜌+2𝑘 −1)

𝑠 ← Rescale(𝑠, 𝑑 (𝜌 −𝜌 ′ ) 𝜌 ← 𝜌′ append (ln 𝜌, 𝑠, 𝑘) to 𝑅

)

// 4. Template matching {𝑟 1, . . . , 𝑟𝑚 } ← TemplateMatch(𝑅, 𝐿) 21 return {𝑟 1 , . . . , 𝑟𝑚 } 20

Theoretical Analysis. For each middle-regime template in the hierarchy 𝑘 (𝑘 ∈ [2, 𝐾]), the hash domain size 2𝑘 is optimal for its privacy level ln(2𝑘 − 1). The multiplicative error factor is upper bounded by the maximum ratio of variances between two consecutive templates (if we ignore the 𝜖1 ).

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

H

Discussions

Online privacy level requests. In some settings, the analysts may not arrive simultaneously, and query systems might have to handle online queries with diverse privacy levels. There is a simple strategy for solving this issue by pre-computing the results using a fine-grained privacy list 𝐿. We generate a privacy list 𝐿 in advance that covers the range of upcoming requests and has fine-grained gaps (i.e., 𝜖𝑖 − 𝜖𝑖+1 is sufficiently small). Then, we run our multitier algorithm on 𝐿 to obtain {𝑟𝑖 }𝑖 ∈𝐿 . For an incoming request with budget 𝜖, we find a result with a close but lower budget from {𝑟𝑖 }𝑖 ∈𝐿 . This strategy works for both multi-tier noise-adding mechanisms and the multi-tier Subset mechanism. Further template improvements. When the privacy list 𝐿 is given and fixed, there is still some room for utility improvement in the template-based multi-tier approach. For example, in the multi-tier Subset mechanism, when the largest budget 𝜖1 satisfies log((𝑑 + 1)/2 − 1) < 𝜖1 < log((𝑑 − 1)/1 − 1), the multi-tier Subset𝐿2 cannot exactly match the ideal single-tier Subset mechanism, since there is still a ’hole’ between 𝑘 = 1 and 𝑘 = 2. A simple strategy would be to skip the template 𝑘 = 1 with 𝜖1′ = log(𝑑/1 − 1) and directly generate the result for 𝜖 to match the ideal one exactly. More generally, when the optimal subset sizes of the target privacy list are sparse in [1, ⌊𝑑/2⌋], it is possible to skip some template 𝑘

Wang et al.

without using the rescale operator, so as to maintain a higher budget (i.e., 𝜌 in Algorithm 2) for the next target privacy level. In some cases, this could improve the overall utility. However, this heuristic could also harm the utility for the next target level in other cases: in the previous example, if the next target level is 𝜖2 = log(𝑑/2 − 1), transforming from the result for 𝜖1 will not be able to achieve an exact optimal match for 𝜖2 (if 𝜖1 < log((𝑑 − 2)/1 − 1)), whereas multi-tier Subset𝐿2 is capable of doing so. We leave such improvements for future research. Supporting more queries. This work mainly studies the most fundamental multi-tier count queries in the curator model and the local model of DP. Considering diverse types of queries in multianalyst databases, mobile services, and data markets, extending to other query types (e.g., numerical queries [14], selection queries [25]) is of great interest, though challenging: (i) the staircase mechanism [14] for numerical summation queries has optimal error rates but exhibits a staircase-style probability design with sharp transitions between stairs; (ii) numerical queries in LDP under the low privacy regime remain largely unexplored both from a theoretical perspective (e.g., optimal error rates) and in terms of optimal base mechanisms; (iii) selection queries with the exponential mechanism are considerably harder in the multi-tier setting, as the output space grows exponentially with the number of tiers. We leave these extensions for future work.

Related documents

• Differentially Private Model Merging#128230
• Dual Stack Hosts Using "Bump-in-the-API" (BIA)#135020
• Differentially private federated adversarial learning–based intrusion prevention for V2X communications#419393
• Distribution of transverse Hodge loci and applications#482555
• Privacy-preserving quantum federated learning via gradient hiding#177307