pith. sign in

arxiv: 2606.15543 · v3 · pith:JJEHBTTHnew · submitted 2026-06-14 · 💻 cs.CR

Multi-tier Differential Private Query Release

Shaowei Wang , Jinn Li , Yun Peng , Puning Zhao , Wenqi Ren , Changyu Dong , Jin Li , Jian Weng This is my paper

Pith reviewed 2026-06-27 04:43 UTC · model grok-4.3

classification 💻 cs.CR
keywords differential privacymulti-tier query releaseprivacy budget compositionnoise mechanismslocal differential privacystatistical query answeringcumulative privacy loss
0
0 comments X

The pith

A multi-tier differential privacy framework bounds cumulative privacy loss to the maximum budget while preserving single-tier utility.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a framework for releasing answers to the same statistical query under multiple different privacy budgets. It ensures that the total privacy loss across all releases is no more than the largest budget used, rather than the sum. The framework achieves this for both noise-adding mechanisms using characteristic functions of their noise distributions and for other mechanisms using custom budget transformation primitives. This addresses scenarios where multiple analysts query the same data with varying levels of privacy protection due to trust or payment differences. If correct, it allows better utility in multi-user privacy settings without additional privacy expenditure.

Core claim

Our framework for multi-tier DP query release simultaneously bounds the cumulative privacy loss by the maximum privacy budget among all queries and achieves optimal utility comparable to that of single-tier mechanisms. It applies to noise-adding mechanisms via characteristic functions and to others via mechanism-specific primitives for budget transformation.

What carries the argument

Characteristic functions of noise distributions for noise-adding mechanisms and mechanism-specific primitives for budget transformation in other mechanisms, which compose releases under different budgets to respect only the maximum budget.

If this is right

  • Cumulative privacy loss across multiple queries with different budgets is bounded by the highest individual budget.
  • Utility for each query matches the performance of a single-tier mechanism run at that query's own budget.
  • The approach works for count queries under the curator model with the two-sided Geometric mechanism.
  • The approach works for count queries under the local DP model with the Subset mechanism using a template-based strategy.
  • Experimental results confirm effectiveness across different privacy regimes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The framework could simplify privacy accounting when the same data serves analysts who differ in trust level or payment.
  • Similar budget transformations might apply to queries beyond simple counts without changing the max-budget guarantee.
  • Systems could serve heterogeneous privacy requests from a single data release process rather than separate runs.

Load-bearing premise

The characteristic functions of the noise distributions or the mechanism-specific primitives for budget transformation can be composed or transformed to enforce the max-budget bound without introducing extra privacy loss or utility degradation.

What would settle it

Applying the framework to count queries with two budgets where one is larger, then measuring whether an adversary can distinguish the outputs with advantage exceeding the max budget or whether answer accuracy falls below the single-tier baseline at the max budget.

Figures

Figures reproduced from arXiv: 2606.15543 by Changyu Dong, Jian Weng, Jin Li, Jinn Li, Puning Zhao, Shaowei Wang, Wenqi Ren, Yun Peng.

Figure 1
Figure 1. Figure 1: Application scenarios of multi-tier differentially private queries. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Procedures of multi-tier DP noises adding from [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Procedure demonstration of multi-tier subset mechanism with [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Heatmap of theoretical multiplicative factor upper bounds of Theorem 5.3 and Theorem 5.4, under varying categories [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: MSE result of count queries under grid budgets. [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 7
Figure 7. Figure 7: Total MSE result of LDP categorical queries with [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Total MSE result of LDP categorical queries with [PITH_FULL_IMAGE:figures/full_fig_p011_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Total MSE result of LDP categorical queries with [PITH_FULL_IMAGE:figures/full_fig_p011_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Total MSE result of LDP categorical queries with [PITH_FULL_IMAGE:figures/full_fig_p012_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Maximum MSE ratio result of LDP categorical [PITH_FULL_IMAGE:figures/full_fig_p012_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Maximum MSE ratio result of LDP categorical [PITH_FULL_IMAGE:figures/full_fig_p012_12.png] view at source ↗
read the original abstract

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 single-tier 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript proposes a framework for multi-tier differential private query release that bounds cumulative privacy loss by the maximum privacy budget across queries while achieving per-tier utility matching that of corresponding single-tier mechanisms. For noise-adding mechanisms it uses characteristic functions of the noise distributions to construct additional noise whose convolution produces the required marginals; for other mechanisms (e.g., local DP Subset) it supplies mechanism-specific budget-transformation primitives and a template strategy. Experimental results are reported to demonstrate effectiveness.

Significance. If the technical claims are correct, the work would be a meaningful contribution to practical differential privacy, removing the usual tension between multi-tier budget allocation and either excessive composition loss or degraded utility. The construction appears to preserve exact marginal optimality while enforcing the joint max-ε guarantee via post-processing, which is a clean and useful property for curator and local models alike.

minor comments (2)
  1. [Abstract] Abstract: the high-level description of the characteristic-function construction would benefit from one additional sentence stating that the convolution is exact and therefore introduces no extra privacy loss or utility degradation.
  2. The experimental section should report the precise privacy budgets used for each tier and the corresponding single-tier baselines so that the 'comparable utility' claim can be directly verified from the tables or figures.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the accurate summary of our framework, and the recommendation for minor revision. We are pleased that the contribution is viewed as meaningful for practical differential privacy.

Circularity Check

0 steps flagged

No significant circularity; construction is self-contained via post-processing and convolution

full rationale

The paper's central claim rests on an explicit construction: for noise-adding mechanisms, characteristic functions are used to derive additional noise whose convolution with the max-budget noise produces exactly the target marginal for each lower tier. Lower-tier outputs are defined as post-processings of the max-tier output, so the joint mechanism satisfies only the maximum epsilon by the post-processing property of DP. Per-tier utility matches the corresponding single-tier mechanism exactly by the choice of the added noise distribution. This reduction is mathematical (convolution and post-processing) and does not rely on fitted parameters, self-citations, or definitions that presuppose the result. No load-bearing step reduces to its own inputs by construction. The framework is therefore self-contained against external DP primitives.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review based solely on abstract; no explicit free parameters, invented entities, or non-standard axioms are stated. The work relies on standard differential privacy definitions and properties of existing mechanisms.

axioms (1)
  • standard math Standard definitions and composition properties of differential privacy
    Invoked implicitly when discussing privacy budgets, cumulative loss, and mechanism classes.

pith-pipeline@v0.9.1-grok · 5735 in / 1165 out tokens · 40905 ms · 2026-06-27T04:43:43.510786+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

42 extracted references · 2 linked inside Pith

  1. [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

    2019

  2. [2]

    Naman Agarwal, Peter Kairouz, and Ziyu Liu. 2021. The skellam mechanism for differentially private federated learning.Advances in neural information processing systems34 (2021), 5052–5064

    2021

  3. [3]

    Daniel Alabi, Sainyam Galhotra, Shagufta Mehnaz, Zeyu Song, and Eugene Wu

  4. [4]

    InCompanion of the 2025 International Conference on Management of Data

    Privacy and security in distributed data markets. InCompanion of the 2025 International Conference on Management of Data. 775–787

    2025

  5. [5]

    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

    2021

  6. [6]

    Santiago Andrés Azcoitia and Nikolaos Laoutaris. 2022. A survey of data market- places and their business models.ACM SIGMOD Record51, 3 (2022), 18–29

    2022

  7. [7]

    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)

    Pith/arXiv arXiv 2018

  8. [8]

    David Blackwell. 1953. Equivalent comparisons of experiments.The annals of mathematical statistics(1953), 265–272

    1953

  9. [9]

    2005.Harmonic analysis and the theory of probability

    Salomon Bochner. 2005.Harmonic analysis and the theory of probability. Courier Corporation

    2005

  10. [10]

    Clément L Canonne, Gautam Kamath, and Thomas Steinke. 2020. The discrete gaussian for differential privacy.Advances in Neural Information Processing Systems33 (2020), 15676–15688

    2020

  11. [11]

    Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting telemetry data privately.Advances in neural information processing systems30 (2017)

    2017

  12. [12]

    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

    2018

  13. [13]

    Cynthia Dwork. 2006. Differential privacy. InInternational colloquium on au- tomata, languages, and programming. Springer, 1–12

    2006

  14. [14]

    Cynthia Dwork. 2008. Differential privacy: A survey of results. InInternational conference on theory and applications of models of computation. Springer, 1–19

    2008

  15. [15]

    Quan Geng and Pramod Viswanath. 2015. Staircase mechanism in differential privacy. InIEEE International Symposium on Information Theory. 2376–2380

    2015

  16. [16]

    Badih Ghazi, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. 2025. Private Hyperparameter Tuning with Ex-Post Guar- antee. InThe Thirty-ninth Annual Conference on Neural Information Processing Systems

    2025

  17. [17]

    Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. 2012. Universally utility-maximizing privacy mechanisms.SIAM J. Comput.41, 6 (2012), 1673–1693

    2012

  18. [18]

    Charlie Harrison and Pasin Manurangsi. 2025. Infinitely Divisible Noise for Differential Privacy: Nearly Optimal Error in the High𝜀 Regime. In6th Symposium on Foundations of Responsible Computing (FORC 2025). Schloss Dagstuhl–Leibniz- Zentrum für Informatik, 12–1

    2025

  19. [19]

    Apple Inc. 2017. Differential Privacy. https://www.apple.com/privacy/docs/ Differential_Privacy_Overview.pdf. [Accessed 29-03-2026]

    2017

  20. [20]

    Google Inc. 2024. Advances in private training for production on-device language models — research.google. https://research.google/blog/advances-in-private- training-for-production-on-device-language-models/. [Accessed 28-03-2026]

    2024

  21. [21]

    Google Inc. 2024. Improving Gboard language models via private federated analytics — research.google. https://research.google/blog/improving-gboard- language-models-via-private-federated-analytics/. [Accessed 28-03-2026]

    2024

  22. [22]

    Peter Kairouz, Keith Bonawitz, and Daniel Ramage. 2016. Discrete distribution estimation under local privacy. InInternational Conference on Machine Learning. PMLR, 2436–2444

    2016

  23. [23]

    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)

    2016

  24. [24]

    Zitao Li, Tianhao Wang, Milan Lopuhaä-Zwakenberg, Ninghui Li, and Boris Škoric. 2020. Estimating numerical distributions under local differential privacy. InProceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 621–635

    2020

  25. [25]

    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 Systems30 (2017)

    2017

  26. [26]

    Frank McSherry and Kunal Talwar. 2007. Mechanism design via differential privacy. In48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07). IEEE, 94–103

    2007

  27. [27]

    Ilya Mironov. 2012. On significance of the least significant bits for differential pri- vacy. InProceedings of the 2012 ACM conference on Computer and communications security. 650–661

    2012

  28. [28]

    2022.Information Theory: From Coding to Learning

    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

    2022

  29. [29]

    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 Confidentiality11, 3 (2021)

    2021

  30. [30]

    Neil G Shephard. 1991. From Characteristic Function to Distribution Function: A Simple Framework for theTheory.Econometric theory7, 4 (1991), 519–529

    1991

  31. [31]

    Ning Wang, Xiaokui Xiao, Yin Yang, Jun Zhao, Siu Cheung Hui, Hyejin Shin, Junbum Shin, and Ge Yu. 2019. Collecting and analyzing multidimensional data Conference acronym ’XX, June 03–05, 2018, Woodstock, NY Wang et al. with local differential privacy. In2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 638–649

    2019

  32. [32]

    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 Systems30, 9 (2019), 2046–2059

    2019

  33. [33]

    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)

    Pith/arXiv arXiv 2016

  34. [34]

    Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. 2017. Locally differentially private protocols for frequency estimation. In26th USENIX security symposium (USENIX Security 17). 729–745

    2017

  35. [35]

    Stanley L Warner. 1965. Randomized response: A survey technique for eliminating evasive answer bias.J. Amer. Statist. Assoc.(1965)

    1965

  36. [36]

    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 Systems35 (2022), 11217–11228

    2022

  37. [37]

    Xiaokui Xiao, Yufei Tao, and Minghua Chen. 2009. Optimal random perturbation at multiple privacy levels.Proc. VLDB Endow.2, 1 (2009), 814–825

    2009

  38. [38]

    Min Ye and Alexander Barg. 2018. Optimal schemes for discrete distribution estimation under locally differential privacy.IEEE Transactions on Information Theory64, 8 (2018), 5662–5676

    2018

  39. [39]

    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 Engineering31, 4 (2018), 655–669

    2018

  40. [40]

    Haifei Yu and Mengxiao Zhang. 2017. Data pricing strategy based on data quality. Computers & Industrial Engineering112 (2017), 1–10

    2017

  41. [41]

    Bing Zhang, Vadym Doroshenko, Peter Kairouz, Thomas Steinke, Abhradeep Thakurta, Ziyin Ma, Eidan Cohen, Himani Apte, and Jodi Spacek. 2024. Differen- tially Private Stream Processing at Scale.Proceedings of the VLDB Endowment17, 12 (2024), 4145–4158

    2024

  42. [42]

    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 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 privac...

    2023