Closing the privacy-accounting gap for linear queries in interactive differential-privacy query systems (detection, composition semantics, partial-knowledge robustness, and formal defenses against sample-amplification attacks)

Huang, Zhou and Liao (IEEE TIFS 2021) showed that an attacker with sufficient background knowledge can obtain $m$ independent noisy answers to one and the same linear query from a differentially private mechanism while the mechanism's own accounting, based on parallel composition over record-disjoint subqueries, charges only a fraction of the budget the attacker effectively consumes. The paper presents the attack and its success-rate analysis but no remedy. The open problem is the one their vulnerability leaves behind, with four linked aspects: (1) how should a curator-side mechanism or privacy-accounting system be designed to detect or correctly account for such linear-property reconstructions under realistic black-box access, where the curator cannot see the attacker's exact complementary knowledge; (2) which interpretation of the parallel-composition requirement — disjoint actual records versus disjoint query domains — is sound and should be standard in practical systems, and how this interacts with answer caching and query-domain definitions; (3) how effective the attack remains when the attacker's background knowledge is partial, noisy, or yields non-unique query intersections; and (4) the construction of formal defenses (accounting rules, query-answering policies, or modified composition theorems) that provably prevent the sample amplification while preserving utility of linear-query answering.

Background

Differential privacy (DP) is a formal guarantee for statistical data release: a randomized mechanism $M$ satisfies $\epsilon$-DP if the probability distribution of its output changes by at most a multiplicative factor $e^\epsilon$ when any single record is added to or removed from the dataset. The privacy budget $\epsilon$ bounds how much information about any individual the released answers can carry, and smaller $\epsilon$ means stronger protection. For numerical queries the standard construction is the Laplace mechanism, which returns the true answer plus noise drawn from a Laplace distribution whose scale is the query's sensitivity (the maximum amount one record can change the answer) divided by $\epsilon$. A linear query — counting and sum queries are the canonical examples — satisfies the linearity property $q(D)=q(D_1)+q(D_2)$ whenever $D=D_1\cup D_2$ with $D_1\cap D_2=\emptyset$.

When many queries are answered, privacy loss accumulates according to two composition theorems. Sequential composition says that answering $k$ queries with budgets $\epsilon_1,\dots,\epsilon_k$ costs $\sum_i\epsilon_i$ in total. Parallel composition says that if the queries act on pairwise disjoint parts of the data, the total cost is only $\max_i\epsilon_i$. Practical interactive systems — from McSherry's Privacy Integrated Queries (PINQ) platform to modern DP-SQL engines — implement a budget meter that applies these theorems to the stream of submitted queries and refuses further answers once a threshold is reached, and they typically cache answers so that a repeated identical query returns the same noisy value rather than a fresh draw.

Two further strands frame the question. First, reconstruction attacks go back to Dinur and Nissim (PODS 2003): enough answers to overlapping linear queries, each perturbed with too little noise, allow reconstructing the underlying database, which is why interactive systems meter the total budget at all. Second, DP was explicitly designed to be insensitive to attackers' background knowledge, a claim critically examined by Kifer and Machanavajjhala's "no free lunch in data privacy" analysis (SIGMOD 2011). A membership inference attack — deciding whether a given target record $x$ is in the protected dataset $D$ — is the standard yardstick for empirically testing such guarantees; it is typically implemented as a hypothesis test that separates the two cases "$x\in D$" and "$x\notin D$" using the distribution of observed answers.

Against this background, Huang, Zhou and Liao (IEEE TIFS 16:3123–3137, 2021) exhibited a gap in the accounting of interactive DP mechanisms that answer linear queries. An attacker who knows a set $D_{know}$ of records and a target record $x$ submits $m$ subqueries with query conditions $s_i$ whose datasets are $D_{s_i}=D_i\cup\{x\}$, where $D_1,\dots,D_m$ are pairwise disjoint subsets of $D_{know}$. Because every submitted condition contains $x$, the curator treats the queries as unrelated, but by adding the self-computed exact complements $q(D_{know}\setminus D_i)$ to the noisy answers the attacker reconstructs $m$ independent, identically distributed samples of the answer to the single target query $q((D_{know}\cup\{x\})\cap D)$, each perturbed with fresh Laplace noise. From the attacker's perspective the total consumed budget is $m\epsilon$ (sequential composition), and the $m$ samples power a hypothesis test for membership of $x$ whose success rate the authors derive in closed form. From the mechanism's perspective, however, the accounting is data-dependent: if $x\notin D$ the subqueries actually evaluate over disjoint record sets $D_i\cap D$, so parallel composition suggests a total charge of only $\epsilon$; if $x\in D$ the queried record sets all share $x$ and the charge is $m\epsilon$. The paper demonstrates the resulting discrepancy and the membership-inference attack, but presents no countermeasure and no corrected accounting. A later framework of Smith, Asghar, Gioiosa, Mrabet, Gaspers and Tyler (PoPETs 2022) computes "maximum overlap" of queries on the data domain to decide when parallel composition may be applied — a domain-disjointness reading under which the attack's query set would be charged $m\epsilon$ — but that work neither analyzes this attack nor addresses caching, partial attacker knowledge, or the standardization of the two interpretations.

Problem Statement

How can differentially private systems that answer linear queries be secured against adversaries who exploit the linear property of queries to amplify sampling? The single scientific objective is to close the gap, identified by Huang, Zhou and Liao (IEEE TIFS 2021), between what a curator's privacy accounting charges and what a background-informed attacker actually learns, so that the accounting is sound for any implementable system. That single objective has four linked facets:

1. Sound accounting and detection. An accounting rule or mechanism-level countermeasure for interactive (black-box) DP query answering that correctly bounds the attacker's true information gain under the subquery-reconstruction attack — in particular under the realistic setting where the curator cannot observe the attacker's exact complementary knowledge $D_{know}$ — together with an analysis of how answer caching (returning the same noisy value for repeated identical queries) and query-domain definitions enter the rule.
2. Composition semantics. A determination of which interpretation of the parallel-composition requirement — queries covering disjoint subsets of the actual records versus disjoint subsets of the data domain — is sound for interactive systems, with justification: the attack's budget discrepancy exists only under the record-disjointness reading, and the source's mechanism-side accounting is data-dependent (it differs according to whether the target record lies in the dataset), so the answer must say which semantics a deployable, data-independent budget meter should use and what each choice costs.
3. Robustness to partial attacker knowledge. A quantification (analytic or empirical with reproducible protocol) of the attack's membership-inference success when the attacker's assumptions hold only partially: background-knowledge sets smaller or noisier than the attack requires, or query intersections that do not uniquely isolate the target record.
4. Formal defense with utility guarantee. A defense — an accounting rule, query-answering policy, or modified composition theorem — with a provable differential-privacy guarantee that blocks the sample-amplification construction while preserving the utility of linear-query answering, and a characterization of the resulting privacy–utility trade-off (e.g., the noise inflation or query-volume reduction the defense imposes relative to an unprotected meter).

A sound, data-independent accounting rule (or equivalent mechanism-level countermeasure) that provably bounds the attacker's information gain while preserving the utility of linear-query answering addresses both facets 1 and 4. Facet 2 requires the rule's composition semantics (record- versus domain-disjointness) to be settled with justification, and facet 3 requires the attack's effectiveness under partial attacker knowledge to be quantified.

References

1. Wen Huang, Shijie Zhou, Yongjian Liao. Unexpected Information Leakage of Differential Privacy Due to the Linear Property of Queries. IEEE Transactions on Information Forensics and Security 16:3123–3137, 2021. DOI: 10.1109/TIFS.2021.3075843, https://doi.org/10.1109/TIFS.2021.3075843 (preprint: arXiv:2010.08958, https://arxiv.org/abs/2010.08958).
2. Josh Smith, Hassan Jameel Asghar, Gianpaolo Gioiosa, Sirine Mrabet, Serge Gaspers, Paul Tyler. Making the Most of Parallel Composition in Differential Privacy. Proceedings on Privacy Enhancing Technologies 2022(1):253–273, 2022. DOI: 10.2478/popets-2022-0013, https://petsymposium.org/popets/2022/popets-2022-0013.php
3. Wen Huang, Zhishuo Zhang, Weixin Zhao, Jian Peng, Wenzheng Xu, Yongjian Liao, Shijie Zhou, Ziming Wang. Auditing privacy budget of differentially private neural network models. Neurocomputing 614:128756, 2025. DOI: 10.1016/j.neucom.2024.128756, https://doi.org/10.1016/j.neucom.2024.128756
4. Weixin Zhao, Zhishuo Zhang, Wen Huang, Jian Peng, Wenzheng Xu, Yongjian Liao, Chang Liu. PGAI-Audit: A Precise and General Method to Audit Privacy Budget of Differentially Private Artificial Intelligence Models. IEEE Transactions on Industrial Informatics 21(11):8717–8726, 2025. DOI: 10.1109/TII.2025.3586056, https://doi.org/10.1109/TII.2025.3586056
5. Hunter D. Moore, Andrew Stephens, William Scherer. An Understanding of the Vulnerability of Datasets to Disparate Membership Inference Attacks. Journal of Cybersecurity and Privacy 2(4):882–906, 2022. DOI: 10.3390/jcp2040045, https://doi.org/10.3390/jcp2040045
6. Ming Zhuo, Wen Huang, Leyuan Liu, Shijie Zhou, Zhiwen Tian. A High-Utility Differentially Private Mechanism for Space Information Networks. Remote Sensing 14(22):5844, 2022. DOI: 10.3390/rs14225844, https://doi.org/10.3390/rs14225844
7. Shuwen Liang, Zhi Qiao, Tianyu Bai, Ying He, Dong'er Chen, Song Fu. A System-Level Framework for Evaluating Privacy in Hybrid LLM Deployments. Algorithms 19(6):500, 2026. DOI: 10.3390/a19060500, https://doi.org/10.3390/a19060500
8. Wen Huang, Shijie Zhou, Tianqing Zhu, Yongjian Liao, Chunjiang Wu, Shilin Qiu. Improving Laplace Mechanism of Differential Privacy by Personalized Sampling. 2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), pp. 623–630, 2020. DOI: 10.1109/TrustCom50675.2020.00088, https://doi.org/10.1109/TrustCom50675.2020.00088
9. Wen Huang, Shijie Zhou, Tianqing Zhu, Yongjian Liao. Improving Utility of Differentially Private Mechanisms through Cryptography-based Technologies: a Survey. arXiv:2011.00976, 2020. https://arxiv.org/abs/2011.00976
10. Irit Dinur, Kobbi Nissim. Revealing Information While Preserving Privacy. Proceedings of the 22nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pp. 202–210, 2003. DOI: 10.1145/773153.773173, https://doi.org/10.1145/773153.773173
11. Daniel Kifer, Ashwin Machanavajjhala. No free lunch in data privacy. Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, pp. 193–204, 2011. DOI: 10.1145/1989323.1989345, https://doi.org/10.1145/1989323.1989345
12. Frank D. McSherry. Privacy Integrated Queries: An Extensible Platform for Privacy-Preserving Data Analysis. Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, pp. 19–30, 2009. DOI: 10.1145/1559845.1559850, https://doi.org/10.1145/1559845.1559850
13. Hinata Sekiguchi, Shun Takagi, Satoshi Hasegawa, Masato Oguchi. Auditing Unexpected Leakage in Label Differential Privacy. 2026 IEEE 50th Annual Computers, Software, and Applications Conference (COMPSAC), pp. 664–674, 2026. DOI: 10.1109/COMPSAC69091.2026.00093, https://doi.org/10.1109/COMPSAC69091.2026.00093