PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Sai Aparna Aketi, Enayat Ullah, Shripad Gade

arXiv:2609.13499v1cs.CRcs.AIcs.LG

TL;DR

Whether protocol-valid candidate-bank manipulation can approach PE’s worst-case user-level privacy loss is unclear. The paper audits that gap with eight canary attacks using a committed shared bank. Natural-text attacks remain well below the theoretical bound, while nonce probes come closer.

  • Problem

    It is unclear whether a server following PE’s protocol can design the shared candidate bank so a user’s participation is as detectable as the worst-case DP guarantee permits.

    Source: §1 · p. 1

  • Method

    The audit commits to a shared candidate bank with canary probes and evaluates eight protocol-aware attack variants using a confidence-bounded privacy test.

    Source: §1 · p. 1, §2.1 · p. 3

  • Results

    Nonce-norm attains εlower 1.110 on Yelp and 1.088 on Sentiment140 (∼67% of εtheory), while natural-text attacks remain well below εtheory = 1.695.

    Source: §3 · pp. 3–4

  • Takeaways & Limitations

    The audit finds practical attacks fall well short of worst-case theory, though high-entropy nonce datasets bring empirical epsilon closer to theoretical epsilon.

    Source: §4 · p. 4

    Running a tight audit requires multiple trials, making it computationally expensive for production settings.

    Source: §4 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

Private Evolution’s user-level DP histogram is calibrated to the worst admissible user contribution, raising the question of whether protocol-following candidate-bank design can realize that privacy loss. The paper audits this gap with canary probes in a shared bank and compares the setting with prior privacy-auditing work.

1 Introduction

  • PE’s user-level DP histogram is calibrated to the worst admissible user contribution, leaving open whether protocol-following candidate-bank design can realize that loss.Source: §1 · p. 1
  • The audit replaces a fixed, predeclared fraction of the shared bank with canary probes, seeking confidence-bounded lower bounds while limiting disruption to output quality.Source: §1 · p. 1
  • Eight attacks freeze one bank before sampling, spanning unchanged-bank baselines, exact copies, plausible paraphrases, and synthetic nonce probes.Source: §1 · p. 1, Table 1 · p. 2
  • Unlike federated audits of client updates or individualized models, this setting probes one public candidate bank sent unchanged to all clients.Source: §1 · p. 2
  • Prior audits examine DP synthetic-data outputs [Annamalai et al., 2024, Meeus et al., 2025, Sun et al., 2025] or private ICL [Xia et al., 2025]; the authors know of no PE audit.Source: §1 · p. 2

2 Methodology

PE aggregates clipped user votes over a candidate bank into a noisy histogram, which guides later sample generation. The audit freezes a shared probe bank, models background participation, and tests for a canary’s hidden participation using calibrated confidence bounds.

2 Methodology

  • Each user’s records are routed to their top-k candidates, then the normalized histogram is clipped to threshold C to form that user’s contribution.Source: §2 · p. 2
  • PE adds user contributions with independent participation indicators and Gaussian noise; each released histogram costs privacy budget, while subsequent selection and generation are post-processing.Source: §2 · p. 2
  • The server follows PE’s protocol, commits to one ordered bank before hidden inclusion, sends it to every client, and observes only aggregate messages; public auxiliary users proxy the private-data distribution.Source: §2 · p. 2

2.1 Audit Mechanism

  • The audit tests randomly selected real-user canaries and synthetic users with independently generated high-entropy nonce records, using public auxiliary data to fix design and calibration choices before evaluation.Source: §2 · p. 2, §2.1 · p. 3
  • A background-aware greedy procedure constructs and freezes the probe bank after recomputing the canary’s exact top-k routing; public auxiliary samples estimate the canary-free histogram background and user-participation variation.Source: §2.1 · p. 3
  • The test scores the canary’s shift from background, marginalizes over its hidden participation probability q, then fixes a threshold on calibration data and uses held-out confusion bounds to lower-bound privacy loss.Source: §2.1 · p. 3
  • Each attack controls family-wise error at α = 0.05 across five canaries, and its empirical privacy bound is compared with a theoretical guarantee computed using matching q, σ, and δ.Source: §2.1 · p. 3

3 Experiments, Results & Discussions

Across Yelp and Sentiment140, attacks using natural text achieve lower empirical privacy-loss bounds than high-entropy nonce probes, which approach the theoretical budget. The audit also reports multi-round utility and privacy on Yelp and finds empirical ε insensitive to encoder capacity in this setup.

3 Experiments, Results & Discussions

  • Experiments use user-partitioned Yelp reviews and Sentiment140 tweets, with 100 participating users per round and default q = 0.1, σ = 1, and δ = 10−5.Unless otherwise stated, reported εlower values are 95%-confidence lower bounds.Source: §3 · p. 3
  • The passive ordinary baseline reaches εlower = 0.268 and 0.252 on Yelp and Sentiment140, respectively, about 15% of εtheory.The same attack trends hold across noise multipliers and sampling rates.Source: §3 · pp. 3–4, Figure 1 · p. 4
  • 0.560 and 0.682 for paraphrase-µeff and 1.110 and 1.088 for nonce-norm on Yelp and Sentiment140, respectively, versus εtheory = 1.695.Natural-text attacks remain below 40% of the theoretical budget, while nonce-norm reaches about 67%.Source: §3 · pp. 3–4, Table 2 · p. 4
  • Across PE rounds on Yelp, the audit preserves synthetic-data utility while providing reasonable empirical ε lower bounds.Figure 2 reports MAUVE utility and privacy parameters against PE round.Source: §3 · p. 4, Figure 2 · p. 4
  • Empirical ε is insensitive to encoder capacity for this setup across MiniLM-L6-v2, MiniLM-L12-v2, and MPNet-base-v2.The compared encoders range from 22.7M to 109M parameters; Table 3 reports εlower.Source: §3 · p. 4, Table 3 · p. 4

4 Conclusion and Limitations

The audit finds that practical attacks fall short of worst-case theory, while high-entropy nonce datasets bring empirical ε closer to theoretical ε. Multi-round PE releases user-level DP histograms, then uses their feedback for post-processing selection and generation; running a tight audit is computationally expensive.

4 Conclusion and Limitations

  • Practical attacks fall short of worst-case theory, while high-entropy nonce datasets bring empirical ε closer to theoretical ε.The authors identify computational expense from multiple trials as a constraint on production use and plan to explore one-run auditing.Source: §4 · p. 4

A Multi-Round Private Evolution Algorithm

  • Each PE round releases a user-level DP histogram; later selection and generation use that histogram and public information as post-processing.Because the candidate population evolves, the accountant must compose all T histogram releases under the declared sampling rule.Source: A Multi-Round Private Evolution… · p. 7

B Attack Variant Details

The attack variants use a shared, frozen candidate bank with reserved probe positions and disjoint canary, auxiliary, and test users. They range from passive or exact-copy attacks to optimized paraphrase and nonce probes, whose selection accounts for competing votes and, in one objective, background traffic.

B Attack Variant Details

  • All variants use one ordered shared bank; active attacks reserve 64 replacement positions, and canary, auxiliary, and final-test users are disjoint.The bank is frozen before membership trials; auxiliary users estimate background traffic, while final-test users evaluate the attack.Source: B Attack Variant Details · p. 7
  • Probe pools contain 512 candidates, with 64 selected; paraphrases rewrite real-canary records, while fresh high-entropy nonce strings are generated independently of natural text.Unoptimized variants choose directly; norm and µeff variants use greedy selection.Source: B Attack Variant Details · p. 7
  • For each trial set, the audit reroutes all 64 canary records among the five nearest entries and normalizes probe-vote counts by 320 total votes.Only selected probes need to be merged with each record’s five nearest base-bank entries to compute the final top five.Source: B Attack Variant Details · p. 8
  • Greedy forward selection is necessary because probes compete for top-five votes, so a candidate’s value depends on the other selected probes.The procedure recomputes routes and the complete score at each step; norm rewards concentrated canary votes, while µeff discounts background traffic using a frozen covariance estimate.Source: B Attack Variant Details · p. 8
  • The passive ordinary baseline leaves the bank unchanged; exact attacks inject copies, while paraphrase variants use unoptimized, norm, or µeff selection.The µeff paraphrase attack discounts coordinates with background traffic estimated from auxiliary users; the norm objective does not.Source: B Attack Variant Details · pp. 8–9
  • Nonce probes are independent audit markers, not hashes of private records, and approximate the mechanism ceiling by placing signal where natural users are unlikely to vote.Nonce-norm maximizes vote magnitude and concentration; nonce-µeff also accounts for background directions.Source: B Attack Variant Details · p. 9

C Complete Results

The complete-results table compares εlower across two datasets and two candidate-bank arms. Bank A uses label-only prompts; Bank B adds three public in-context examples to better match the private-user distribution.

C Complete Results

  • Table 4 compares εlower for two datasets and two candidate-bank arms, with εtheory = 1.695.Each entry is the maximum over five canaries; Bank A is label-only, while Bank B uses three public in-context examples.Source: Table 4 · p. 9, C Complete Results · p. 9

D Hyperparameter settings

The appendix specifies the user populations, trial budgets, and multi-round accounting used in the experiments.

D Hyperparameter settings

  • The single-release experiments use N = 1,000 eligible non-canary users and q = 0.1 unless swept, with 100 expected participants per release.The final-test users are separate from the 500 auxiliary and 500 calibration users.Source: D Hyperparameter settings · p. 9
  • The appendix uses 1M trials per hypothesis for Tables 2 and 4, and 5M for Figure 1 and the multi-round audit.The larger Figure 1 budget stabilizes Clopper–Pearson bounds when errors at the selected tail threshold are rare.Source: D Hyperparameter settings · p. 10
  • Figure 2 composes six Yelp releases at q = 0.1 and σ = 1.1088, with theoretical ε rising from 1.345 after release one to 2.000 after release six.The empirical audit composes each prefix by summing mixture log-likelihood ratios.Source: D Hyperparameter settings · p. 10

E Additional Mathematical Details

The appendix derives the audit’s background and canary distributions, then approximates the background with a Gaussian to obtain a fixed-inclusion likelihood ratio.

E.1 Background aggregate and its moments

  • The background aggregate sums sampled non-canary users’ inspected-coordinate contributions with Gaussian noise; user vectors are fixed after the bank, routing, and clipping are frozen.Off-diagonal covariance entries capture correlated voting when one user contributes to multiple inspected coordinates.Source: §E.1 · p. 10

E.2 Three cases

  • The canary contribution v is deterministic because the bank and canary records are fixed before each trial.Source: §E.2 · p. 10
  • The absent-canary and fixed-inclusion distributions have means m0 and m0 + v with covariance Σ, while eligibility yields mean m0 + qv and covariance Σ + q(1 − q)vv⊤.The eligible-canary case is a mixture because its sampling indicator J is Bernoulli(q); independent sampling leaves the background unchanged.Source: §E.2 · pp. 10–11

E.3 Gaussian approximation and fixed-inclusion likelihood ratio

  • The audit approximates the Bernoulli-weighted, Gaussian-noise background aggregate with a Gaussian, while equality of the component covariances remains exact.The Gaussian shape is the approximation; equal covariance makes the fixed-inclusion log-likelihood score linear in y.Source: §E.3 · p. 11
  • With equal component covariances, the shared quadratic term cancels when forming the fixed-inclusion likelihood ratio.Source: §E.3 · p. 11

E.4 Whitening and effective separation

The appendix characterizes how background variance affects component separation and how hidden canary participation changes the likelihood ratio and test signal.

E.4 Whitening and effective separation

  • Mahalanobis signal-to-noise ratio weights high-background-variance directions less and signal on quieter coordinates more.The distance between component means is the signal being weighted.Source: §E.4 · p. 12
  • The conditional Gaussian separation has a ceiling, but that ceiling is not itself an (ε, δ)-DP formula.Source: §E.4 · p. 12

E.5 Hidden participation and the mixture likelihood ratio

  • Because an eligible canary is sampled only with probability q, the alternative remains a mixture rather than a single Gaussian.The mixture identity is exact for a true component likelihood ratio, but the audit inherits the Gaussian approximation used to obtain it.Source: §E.5 · p. 12
  • For a single release, ℓ and ℓmix rank observations identically, but only ℓmix is the likelihood-ratio value for the eligible-canary hypothesis.The test-rate difference obeys TPR − FPR = q (TPRinc − FPR).Source: §E.5 · p. 12

E.6 From test errors to an empirical privacy lower bound

The appendix converts audit test errors into a conservative empirical privacy lower bound using one-sided confidence bounds and a threshold fixed before final evaluation.

E.6 From test errors to an empirical privacy lower bound

  • The empirical privacy lower bound uses lower confidence bounds for TPR and TNR and upper confidence bounds for FPR and FNR.The rates are estimated from finitely many final-evaluation trials using one-sided Clopper–Pearson endpoints.Source: §E.6 · p. 13
  • A branch whose lower-confidence numerator is at most δ supplies no positive empirical privacy lower bound.Source: §E.6 · p. 13
  • The audit allocates overall α = 0.05 across five canaries per attack and four one-sided rate bounds per canary.Source: §E.6 · p. 13
  • The calibration split is independent of final evaluation, freezing event A and its threshold before final confusion counts are observed.Source: §E.6 · p. 13

E.7 Auxiliary moment estimation

The audit estimates auxiliary moments from clipped contributions, shrinking noisy off-diagonal terms before constructing plug-in estimates. Across rounds, mixture scores can be summed only when each is conditioned on the realized earlier transcript.

E.7 Auxiliary moment estimation

  • Because finite n_aux makes off-diagonal entries noisy, diagonal shrinkage preserves diagonal second moments while multiplying estimated off-diagonal terms by 0.9.The shrinkage is 0.9c_MP + 0.1 diag(diag(c_MP)).Source: §E.7 · p. 14
  • The plug-in estimators set b_m0 = qN b_μP and b_ΣP to the shrunken auxiliary moment scaled by q(1 − q)N, plus Gaussian-noise covariance and a numerical ridge.The Gaussian-noise covariance is already present in the released histogram; no noise is added to public auxiliary data, and 10^-9I stabilizes inversion.Source: §E.7 · p. 14

E.8 Conditional composition across rounds

  • Per-round mixture scores can be summed when each is the conditional likelihood ratio given the realized earlier transcript; unconditional marginal scores are not generally valid for adaptive banks.Formal DP accounting remains valid under adaptive composition because candidate retention and public generation are post-processing, while each new private histogram is separately composed.Source: §E.8 · p. 14
Loading 2609.13499v1…