Multi-tier Differential Private Query Release

Computer Science > Cryptography and Security [Submitted on 14 Jun 2026] Multi-tier Differential Private Query Release Shaowei Wang, Jinn Li, Yun Peng, Puning Zhao, Wenqi Ren, Changyu Dong, Jin Li, Jian Weng 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. Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2606.15543 [cs.CR]   (or arXiv:2606.15543v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2606.15543 Focus to learn more Submission history From: Shaowei Wang [view email] [v1] Sun, 14 Jun 2026 02:10:22 UTC (3,064 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-06 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)