Canaries in the Bank: Auditing User-Level Privacy in Private Evolution

Sai Aparna Aketi; Enayat Ullah; Shripad Gade

cs.CRSep 11, 2026

Canaries in the Bank: Auditing User-Level Privacy in Private Evolution

Authors: Sai Aparna Aketi, Enayat Ullah, Shripad Gade

Organizations: Meta Platforms, Inc. Menlo Park, USA.

Abstract

Private Evolution (PE) generates high-fidelity synthetic data in federated settings without exposing users' raw data. It aggregates clipped user votes over a shared candidate bank into a differentially private histogram, with noise calibrated to the worst-case user contribution. However, it is unclear whether an adversary can realize this worst-case privacy loss while following the PE protocol. We introduce a protocol-aware empirical audit in which the server commits to a single shared candidate bank and replaces roughly 1% of its entries with probes derived from a known, non-private canary. We evaluate eight attacks, including an unchanged-bank baseline, exact copies, plausible paraphrases, and high-entropy synthetic nonces. Experiments on Yelp and Sentiment140 show that natural-text attacks remain substantially below the theoretical DP bound, while nonce-based attacks yield considerably stronger bounds and come closest to the mechanism's privacy ceiling. These results quantify the gap between formal worst-case privacy and leakage achievable through protocol-valid candidate-bank manipulation.

Figures & tables

Attack variant	Canary type	Candidate selection
ordinary	random real user	use the original bank; inject no probes
exact	random real user	inject exact copies of the canary records
paraphrase	random real user	inject paraphrases spread across canary records
paraphrase-norm	random real user	select paraphrases maximizing canary probe votes
paraphrase- $\mu_{\mathrm{eff}}$	random real user	maximize canary votes and minimize user votes on probes
nonce	synthetic nonce user	inject a random subset of nonce probes

Table 1: The eight audit attack variants. Nonce samples are independently generated high-entropy strings unrelated to natural text. Appendix B describes each construction in detail.

Dataset	ordinary	exact	paraphrase	paraphrase-norm	paraphrase- $\mu_{\mathrm{eff}}$	nonce	nonce-norm	nonce- $\mu_{\mathrm{eff}}$	$\varepsilon_{\mathrm{theory}}$
Yelp Open Dataset	0.268	0.371	0.276	0.316	0.560	1.049	1.110	1.110	1.695
Sentiment140	0.252	0.363	0.599	0.327	0.682	1.052	1.088	1.086	1.695

Table 2:

\varepsilon_{\mathrm{lower}}

for attacks with the label-only bank. Each entry is the maximum over five canaries with

\alpha=0.05

, each evaluated at

\alpha/5

with

1M

trials per hypothesis.

Figure 1: Sentiment140 ablations (one canary, label-only bank,

5M

trials); bands are 95% CIs.

Figure 2: Multi-round PE on Yelp: utility and privacy parameters (theory vs audit) against PE-round.

Attack	Yelp Open Reviews			Sentiment140 Tweets
Attack	MiniLM-L6	MiniLM-L12	MPNET-Base-V2	MiniLM-L6	MiniLM-L12	MPNET-Base-V2
ordinary	0.268	0.232	0.273	0.252	0.272	0.249
exact	0.371	0.357	0.387	0.363	0.341	0.245
nonce	1.049	1.105	1.087	1.052	1.088	1.078

Table 3: Embedding model ablation (

\varepsilon_{\mathrm{lower}}

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Attack variant	Yelp A	Yelp B	Sentiment140 A	Sentiment140 B
ordinary	0.247	0.295	0.475	0.429
exact	0.313	0.304	0.363	0.587
paraphrase	0.276	0.297	0.599	0.759
paraphrase-norm	0.316	0.457	0.327	0.871
paraphrase- $\mu_{\mathrm{eff}}$	0.560	0.439	0.682	0.932
nonce	1.038	1.047	1.018	1.014

Appendix

Table 4:

\varepsilon_{\mathrm{lower}}

for two datasets and two candidate-bank arms. Each entry is the maximum over five canaries with

\alpha=0.05

, each evaluated at

\alpha/5=0.01

and

1M

trials per hypothesis;

\varepsilon_{\mathrm{theory}}=1.695

Privacy Auditing

Privacy auditing evaluates whether data, models, and AI systems expose sensitive information under realistic adversaries and use.

See all 81 papers

Understanding Private Evolution as Learning-Augmented Clustering
Sep 29, 2026Audra McMillan, Kunal Talwar, Felix ZhouDifferentially Private Synthetic Data Generation Synthetic Data Generation
Apple · Yale University
Detectability without Interference: Efficient Canary Design for Privacy Auditing in One Run
May 26, 2026Mathieu Dagréou, Valentin Dorseuil, Mohammad Yaghini +2Privacy Auditing Membership Inference Attacks
PreMeDICaL team, Inria Idesp, Inserm, Univ. de Montpellier
Advancing the State-of-the-Art in Empirical Privacy Auditing
Jun 9, 2026Nicole Mitchell, Galen Andrew, Arun Ganesh +2Data Leakage Privacy Auditing
Google Research San Francisco, CA · Google Research Seattle, WA

Sep 29, 2026J/K move · Enter open · S save

Understanding Private Evolution as Learning-Augmented Clustering

Audra McMillan, Kunal Talwar, Felix Zhou

Apple · Yale University

Differentially Private Synthetic Data Generation Synthetic Data Generation Differential Privacy Learning-Augmented Algorithms

Open paper AskPDF arXiv

Private Evolution (PE) is a differentially private algorithm for synthetic data generation. While it can be viewed as a Wasserstein learning algorithm, it performs much better in practice than worst-case Wasserstein analyses would predict. We recast PE as generative model-augmented Wasserstein learning. We show theoretically that when we take into account the use of a generative model that is able to capture something about the true distribution, then we can obtain much better performance bounds. For example, if the generator gives samples in the same low-dimensional space as the distribution, then sample complexity depends on intrinsic, not ambient, dimension. We also show that standard variants of PE can fail to converge on simple well-clustered instances, and propose a new geometry-aware version of PE with provable convergence on such instances. Experimentally, we show that our new algorithm is competitive with standard baselines and can improve recall.

Abstract

Privacy Auditing

Explore similar work

Understanding Private Evolution as Learning-Augmented Clustering

Detectability without Interference: Efficient Canary Design for Privacy Auditing in One Run

Advancing the State-of-the-Art in Empirical Privacy Auditing