Attack-Parameter-to-Budget Calibration for Differentially Private Query Systems: Beyond Count Aggregates Under Repeated, Adaptive, and Auxiliary-Information Attacks

Jia, Wu, Guo, Gao, Peng, Ran and Li (2019), in 'Database Query System with Budget Option for Differential Privacy Against Repeated Attacks', calibrate the differential-privacy budget of an interactive SQL query platform from administrator-specified attack parameters -- the maximum number of repeated queries N and the tolerable attacker success probability rho' -- by inverting a binomial majority-vote attack model derived only for counting queries under an adversary that naively repeats one fixed query. The paper's own Conclusions leave open extending this calibration to the aggregate functions except count and abstracting the complicated attacks in practice into detailed algorithmic models beyond the naive repeated-identical-query adversary; sum, average, and median, and adaptive or auxiliary-information attackers, are illustrative examples of these directions rather than enumerations by the paper. No resolution is known in the literature to date: an independent 2020 treatment covers sum/average-type global-sensitivity queries but not the median and retains the naive adversary, while mainstream composition theory bounds cumulative privacy loss rather than the operational attacker success probabilities this calibration targets. The precise open core -- per-aggregate attack-to-budget calibration for the aggregate functions except count, including those with data-dependent sensitivity such as the median, and operational success-probability calibration derived from detailed algorithmic models of the complicated attacks in practice -- remains open.

Background

An interactive statistical database answers queries about a sensitive dataset while trying not to reveal any individual record. Differential privacy (DP) is the standard formal guarantee: a randomized mechanism $M$ is $\varepsilon$-differentially private if, for any two databases $D$ and $D'$ differing in a single record, every event in the output space has probability ratio at most $e^\varepsilon$ between $M(D)$ and $M(D')$ (Dwork, McSherry, Nissim and Smith, 2006, doi:10.1007/11681878_14). The parameter $\varepsilon$, called the privacy budget, controls the privacy-utility trade-off: smaller $\varepsilon$ means stronger privacy and noisier answers. The workhorse Laplace mechanism adds Laplace-distributed noise to a query result with scale proportional to the query's global sensitivity, the maximum amount by which one record can change the answer. How to choose $\varepsilon$ in practice is a recognized open issue of its own (Hsu et al., 2014, doi:10.1109/CSF.2014.35; Ligett et al., 2017, arXiv:1705.10829).

Repeated queries are the classical threat to such systems: an attacker who can ask the same query many times can average away independent noise and reconstruct the underlying data (Dinur and Nissim, 2003, doi:10.1145/773153.773173; Dwork, Kenthapadi, McSherry, Mironov and Naor, 2006, doi:10.1007/11761679_29). DP's answer to repeated and even adversarially chosen queries is composition: if answers consume budgets $\varepsilon_1,\dots,\varepsilon_k$, the total privacy loss is at most their sum, and sharper bounds are known (Dwork, Rothblum and Vadhan, 2010, doi:10.1109/FOCS.2010.12; Kairouz, Oh and Viswanath, 2017, doi:10.1109/TIT.2017.2685505). Formally, the DP adversary is already assumed adaptive -- queries may depend on earlier answers -- and armed with arbitrary auxiliary information about the data; semantic and Bayesian formulations of DP make this explicit (Kasiviswanathan and Smith, 2014, doi:10.29012/jpc.v6i1.634), and frameworks such as Pufferfish quantify attackers with specific background knowledge (Kifer and Machanavajjhala, 2014, doi:10.1145/2514689). Privacy filters and odometers extend composition to fully interactive settings in which even the number of queries and their privacy parameters are chosen on the fly (Rogers, Roth, Ullman and Vadhan, 2016, arXiv:1605.08294; Whitehouse, Ramdas, Rogers and Wu, 2022, arXiv:2203.05481), and Gaussian differential privacy recasts the whole question as a hypothesis test between neighboring datasets (Dong, Roth and Su, 2022, doi:10.1111/rssb.12454). These results bound cumulative privacy loss, a worst-case quantity; they do not directly bound an operational attacker's probability of correctly inferring, for example, an individual's presence from repeated noisy aggregate answers.

The source paper (Jia et al., 2019, doi:10.1007/978-3-030-21373-2_5) builds a practical DP database query system in this landscape. Its query pipeline answers general SQL queries by adding Laplace noise scaled by a smoothed version of elastic sensitivity -- an efficiently computable approximation of local sensitivity (the sensitivity at the actual database rather than in the worst case), introduced for SQL by Johnson, Near and Song (2018, doi:10.1145/3187009.3177733). Its distinctive feature is budget calibration from attack parameters: instead of choosing $\varepsilon$ by hand, the administrator specifies the maximum number of repeated attacks $N$ and an acceptable upper bound $\rho'$ on the attacker's success probability, and the system inverts a binomial majority-vote attack model to obtain $\varepsilon$. That model is derived only for a counting query, an integer-valued answer with unit sensitivity $\Delta f = 1$: the source's adversary knows the true count is $y$ or $y+1$, issues $N=2n+1$ copies of the query, and casts each noisy answer as a vote for $y$ or for $y+1$ according as it falls below or above the threshold $y+L$, so each noisy answer supports a correct majority vote with the one-sided cumulative probability $p=F(\mu+L)=1-\tfrac{1}{2}e^{-L\varepsilon/\Delta f}$ evaluated at position parameter $\mu=0$ (the source's Eq. (5); $p=1-\tfrac{1}{2}e^{-L\varepsilon}$ for counts), where $L$ is the half-length of the source's fault-tolerant interval ($L=0.5$ in the source system). The two-sided fault-tolerant interval around the true answer is the source's single-query leakage concept -- an answer falling inside it exposes the true count -- and is distinct from the one-sided per-trial criterion the calibration uses. An adversary who majority-votes over the $N$ copies succeeds with probability $\sum_{i=n+1}^{N}\binom{N}{i}p^{i}(1-p)^{N-i}$, which the system drives to at most $\rho'$ by numerical inversion for $\varepsilon$, yielding an upper bound on the admissible privacy budget. A per-client query budget is meant to enforce the assumption of at most $N$ queries.

The aggregate functions beyond count behave very differently under this program. A sum or average over an attribute with a known bounded range still has a finite global sensitivity, so the tolerance-interval analysis extends mechanically: the source's per-trial formula already carries a general sensitivity $\Delta f$, and substituting the aggregate's global sensitivity $\Delta q$ for the unit count sensitivity gives per-trial success $1-\tfrac{1}{2}e^{-L\varepsilon/\Delta q}$; an independent later treatment derives fault-tolerance-interval epsilon selection for the Laplace mechanism with general global sensitivity (Sun, 2020, doi:10.1155/2020/8845038). The median is the hard case: its global sensitivity is enormous, since one record can move the median across the whole value range, so global-sensitivity Laplace noise destroys utility. Usable private medians instead rely on data-dependent sensitivity notions such as the inverse-sensitivity mechanism, which draws noise according to how much the database must change for a different value to become the true answer (Smith, 2011, doi:10.1145/1993636.1993743); such mechanisms do not emit i.i.d. Laplace noise, and the independence structure behind the binomial majority-vote analysis breaks down. In parallel, modern privacy auditing estimates empirical privacy parameters from observed attack success rates (Jagielski, Ullman and Oprea, 2020, arXiv:2006.07709; Steinke, Nasr and Jagielski, 2023, arXiv:2305.08846) -- the inverse of the forward calibration this system performs -- and repeated-query attacks have been quantified in machine-learning settings (Rahimian, Orekondy and Fritz, 2020, arXiv:2009.00395), but neither line supplies per-aggregate attack-to-budget calibrations for interactive query systems.

Problem Statement

The system of Jia et al. (2019) calibrates the privacy budget of an interactive differentially private database query system from administrator-specified attack parameters -- the maximum number of repeated attacks $N$ and the tolerable attacker success probability $\rho'$ -- but the repeated-attack model and the $\varepsilon$-inversion behind this calibration were derived only for counting queries, under an adversary that simply repeats one fixed counting query and majority-votes. Extend this attack-parameter-to-budget calibration so that: (i) it covers the aggregate functions except count that the system is asked to serve -- sum, average, and median being the required minimum (these three suffice; further non-count aggregates are optional), the median the hard data-dependent-sensitivity case -- meaning, for each such aggregate, an explicit attack model, a derivation of the attacker's success probability as a function of the mechanism's privacy parameter $\varepsilon$, the number of queries, and the relevant sensitivity of the query (the fixed global sensitivity for count, sum, and average, the data-dependent sensitivity for the median), and an inversion (exact or algorithmic) that selects $\varepsilon$ so the modeled success probability stays at most $\rho'$, in the form of an upper bound on the admissible $\varepsilon$ as in the source calibration; and (ii) the naive repeated-identical-query adversary is replaced by precise algorithmic models of the complicated attacks in practice -- adversaries that adaptively choose queries based on previously received answers, or that exploit auxiliary (background) information, being the required adversary families (these two suffice; further adversary classes are optional) -- with the corresponding privacy-budget calibrations derived from those models in the same operational success-probability terms. The single objective uniting these deliverables, both of which are required, is a budget-calibrated query system whose protection is faithful to the aggregates it actually serves and to the adversaries it actually faces.

References

1. Jingyu Jia, Yuduo Wu, Yue Guo, Jiqiang Gao, Jin Peng, Peng Ran, Min Li, 'Database Query System with Budget Option for Differential Privacy Against Repeated Attacks', in Security and Privacy in New Computing Environments, Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, Springer, 2019, pp. 46-57, doi:10.1007/978-3-030-21373-2_5, https://doi.org/10.1007/978-3-030-21373-2_5
2. Pan Jun Sun, 'Research on Selection Method of Privacy Parameter ε', Security and Communication Networks, vol. 2020, Article 8845038, 2020, pp. 1-12, doi:10.1155/2020/8845038, https://doi.org/10.1155/2020/8845038
3. Irit Dinur, Kobbi Nissim, 'Revealing Information While Preserving Privacy', Proceedings of the 22nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2003), 2003, pp. 202-210, doi:10.1145/773153.773173, https://doi.org/10.1145/773153.773173
4. Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, Moni Naor, 'Our Data, Ourselves: Privacy Via Distributed Noise Generation', Advances in Cryptology - EUROCRYPT 2006, Lecture Notes in Computer Science, Springer, 2006, pp. 486-503, doi:10.1007/11761679_29, https://doi.org/10.1007/11761679_29
5. Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith, 'Calibrating Noise to Sensitivity in Private Data Analysis', Theory of Cryptography (TCC 2006), Lecture Notes in Computer Science, Springer, 2006, pp. 265-284, doi:10.1007/11681878_14, https://doi.org/10.1007/11681878_14
6. Cynthia Dwork, Guy N. Rothblum, Salil Vadhan, 'Boosting and Differential Privacy', 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), 2010, pp. 51-60, doi:10.1109/FOCS.2010.12, https://doi.org/10.1109/FOCS.2010.12
7. Peter Kairouz, Sewoong Oh, Pramod Viswanath, 'The Composition Theorem for Differential Privacy', IEEE Transactions on Information Theory, vol. 63, no. 6, 2017, pp. 4037-4049, doi:10.1109/TIT.2017.2685505, https://doi.org/10.1109/TIT.2017.2685505
8. Shiva Prasad Kasiviswanathan, Adam Smith, 'On the 'Semantics' of Differential Privacy: A Bayesian Formulation', Journal of Privacy and Confidentiality, vol. 6, no. 1, 2014, doi:10.29012/jpc.v6i1.634, https://doi.org/10.29012/jpc.v6i1.634
9. Daniel Kifer, Ashwin Machanavajjhala, 'Pufferfish: A Framework for Mathematical Privacy Definitions', ACM Transactions on Database Systems, vol. 39, no. 1, 2014, Article 3, pp. 1-36, doi:10.1145/2514689, https://doi.org/10.1145/2514689
10. Ryan Rogers, Aaron Roth, Jonathan Ullman, Salil Vadhan, 'Privacy Odometers and Filters: Pay-as-you-Go Composition', Advances in Neural Information Processing Systems 29 (NIPS 2016), 2016, arXiv:1605.08294, https://arxiv.org/abs/1605.08294
11. Justin Whitehouse, Aaditya Ramdas, Ryan M. Rogers, Zhiwei Steven Wu, 'Fully Adaptive Composition in Differential Privacy', 2022, arXiv:2203.05481, https://arxiv.org/abs/2203.05481
12. Jinshuo Dong, Aaron Roth, Weijie J. Su, 'Gaussian Differential Privacy', Journal of the Royal Statistical Society Series B: Statistical Methodology, vol. 84, no. 1, 2022, pp. 3-37, doi:10.1111/rssb.12454, https://doi.org/10.1111/rssb.12454
13. Noah Johnson, Joseph P. Near, Dawn Song, 'Towards Practical Differential Privacy for SQL Queries', Proceedings of the VLDB Endowment, vol. 11, no. 5, 2018, pp. 526-539, doi:10.1145/3187009.3177733, https://doi.org/10.1145/3187009.3177733
14. Justin Hsu, Marco Gaboardi, Andreas Haeberlen, Sanjeev Khanna, Arjun Narayan, Benjamin C. Pierce, Aaron Roth, 'Differential Privacy: An Economic Method for Choosing Epsilon', IEEE 27th Computer Security Foundations Symposium (CSF 2014), 2014, pp. 398-410, doi:10.1109/CSF.2014.35, https://doi.org/10.1109/CSF.2014.35
15. Katrina Ligett, Seth Neel, Aaron Roth, Bo Waggoner, Zhiwei Steven Wu, 'Accuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained ERM', Advances in Neural Information Processing Systems 30 (NIPS 2017), 2017, arXiv:1705.10829, https://arxiv.org/abs/1705.10829
16. Adam Smith, 'Privacy-Preserving Statistical Estimation with Optimal Convergence Rates', Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC 2011), 2011, pp. 813-822, doi:10.1145/1993636.1993743, https://doi.org/10.1145/1993636.1993743
17. Matthew Jagielski, Jonathan Ullman, Alina Oprea, 'Auditing Differentially Private Machine Learning: How Private is Private SGD?', Advances in Neural Information Processing Systems 33 (NeurIPS 2020), 2020, arXiv:2006.07709, https://arxiv.org/abs/2006.07709
18. Thomas Steinke, Milad Nasr, Matthew Jagielski, 'Privacy Auditing with One (1) Training Run', Advances in Neural Information Processing Systems 36 (NeurIPS 2023), 2023, arXiv:2305.08846, https://arxiv.org/abs/2305.08846
19. Shadi Rahimian, Tribhuvanesh Orekondy, Mario Fritz, 'Sampling Attacks: Amplification of Membership Inference Attacks by Repeated Queries', 2020, arXiv:2009.00395, https://arxiv.org/abs/2009.00395
20. Xiaoguang Li, Hui Li, Hui Zhu, Muyang Huang, 'The Optimal Upper Bound of the Number of Queries for Laplace Mechanism Under Differential Privacy', Information Sciences, vol. 503, 2019, pp. 219-237, doi:10.1016/j.ins.2019.07.001, https://doi.org/10.1016/j.ins.2019.07.001
21. Benedetta Gottardelli, Roberto Gatta, Leonardo Nucciarelli, Andrada Mihaela Tudor, Erica Tavazzi, Mauro Vallati, Stefania Orini, Nicoletta Di Giorgi, Andrea Damiani, 'GEN-RWD Sandbox: bridging the gap between hospital data privacy and external research insights with distributed analytics', BMC Medical Informatics and Decision Making, vol. 24, 2024, Article 170, doi:10.1186/s12911-024-02549-5, https://doi.org/10.1186/s12911-024-02549-5
22. Leong Mei Han, Yang Zhao, Jun Zhao, 'POSTER: Blockchain-Based Differential Privacy Cost Management System', Proceedings of the 15th ACM Asia Conference on Computer and Communications Security (AsiaCCS 2020), 2020, pp. 925-927, doi:10.1145/3320269.3405446, https://doi.org/10.1145/3320269.3405446
23. Yu Wei, Jingyu Jia, Yuduo Wu, Changhui Hu, Changyu Dong, Zheli Liu, Xiaofeng Chen, Yun Peng, Shaowei Wang, 'Distributed Differential Privacy via Shuffling Versus Aggregation: A Curious Study', IEEE Transactions on Information Forensics and Security, vol. 19, 2024, pp. 2501-2516, doi:10.1109/TIFS.2024.3351474, https://doi.org/10.1109/TIFS.2024.3351474