Conformal Privacy Auditing: Calibrated Re-identification Attacks with Statistical Guarantees¶
Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM Safety
Keywords: conformal prediction, privacy auditing, identity re-identification, LLM safety, statistical guarantees
TL;DR¶
Addressing identity re-identification risks driven by large language models paired with auxiliary background knowledge, this paper proposes Conformal Privacy Auditing (CPA), a distribution-free black-box framework that outputs certified ambiguity sets with finite-sample coverage guarantees alongside an interpretable leakage proxy to inform document release decisions.
Background & Motivation¶
Organizations across healthcare, legal, and social domains frequently need to release text corpora, such as clinical case notes or judicial records, to enable research and downstream application development. Common de-identification practice relies on redacting explicit identifiers with generic symbolic placeholders. However, seemingly innocuous residual attributesโsuch as age, gender, medical specialty, and municipal locationโfrequently persist in sanitized narratives and collectively act as linkable quasi-identifiers. With modern large language models demonstrating exceptional capability in context reasoning and knowledge synthesis, malicious actors can exploit LLMs to extract salient implicit clues and cross-reference external registries, turning redacted documents into easily re-identifiable targets.
Existing paradigms for evaluating and enforcing text privacy fail to address this emerging threat effectively. On one end of the spectrum, Differential Privacy (DP) guarantees worst-case algorithmic stability through calibrated noise addition; nevertheless, injecting noise into natural language generation or unstructured document releases causes severe utility collapse, and its conservative global sensitivity bounds cannot capture document-specific, context-sensitive re-identification risks at release time. On the other end, empirical privacy auditing relies on attack-specific metrics such as Top-1 re-identification accuracy. While empirically informative, point-estimate attack success rates lack finite-sample theoretical validity, making it impossible to determine whether a measured risk generalizes to unseen documents or stronger adversaries.
This work addresses the core tension by framing release-time identity linkage auditing through the lens of conformal prediction, seeking finite-sample statistical certificates without requiring parametric distributional assumptions or white-box access to the attacker. Core idea: develop Conformal Privacy Auditing (CPA), a distribution-free framework using adaptive cumulative mass scores and split conformal calibration to produce candidate identity ambiguity sets guaranteed to cover the true individual with user-chosen confidence \(1-\alpha\), using certified set size as an interpretable leakage certificate for release control.
Method¶
Overall Architecture¶
CPA operates at the pre-release auditing stage. Given a candidate document \(x\) intended for release and a declared attacker threat configuration \(w\) (encompassing candidate profile registries, external corpora, LLM-based clue extraction prompts, and query modes), the system queries the declared attacker pipeline to obtain a candidate distribution or ranking. Split conformal calibration maps this output to a certified ambiguity set \(C_\alpha(x, w)\) that contains the true subject with probability at least \(1-\alpha\) under exchangeability. The reciprocal of the set size defines a normalized leakage proxy \(L(x, w)\) to directly support operational release decisions.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Released Document & Attacker Knowledge Base"] --> B["Adaptive Cumulative Mass Scoring<br/>Accumulate candidate probabilities in sorted order"]
B --> C["Black-Box Split Conformal Calibration<br/>Compute order-statistic quantile on held-out calibration set"]
C --> D["Open-World Truncation & Ambiguity Certification<br/>Output certified identity set and leakage proxy"]
D --> E["Release or Further Redaction Decision"]
Key Designs¶
1. Adaptive Cumulative Mass Scoring: Quantifying Attacker Uncertainty over Candidates Conventional conformal prediction operates over predefined discrete class labels, whereas realistic privacy adversaries generate continuous similarity metrics, temperature-scaled softmax pseudo-posteriors, or sampled empirical frequencies. To establish an exchangeable scalar nonconformity measure across diverse attacker interfaces, CPA adapts Adaptive Prediction Sets (APS) to candidate identity pools. Given released document \(x\), candidate identity \(y\), and threat configuration \(w\), let \(\pi_1, \pi_2, \dots\) denote candidate profiles sorted by descending attacker confidence \(p_A(\cdot | x, w)\). The nonconformity score measures the cumulative probability mass required to include identity \(y\): $\(s(x, y; w) := \sum_{j: p_A(\pi_j|x, w) \ge p_A(y|x, w)} p_A(\pi_j | x, w)\)$ The score strictly takes values in \((0, 1]\). A concentrated belief on the true subject yields a near-zero score (high linkage certainty), while diffuse belief yields a large score. For proprietary black-box APIs lacking logit access, CPA queries the attacker \(m\) times via forced-choice prompts to estimate empirical frequencies \(\hat{p}_m\), computing an empirical plug-in score \(\hat{s}_m\) that preserves exchangeability without requiring internal model parameters.
2. Black-Box Split Conformal Calibration: Providing Finite-Sample Coverage Certificates Instead of ad-hoc threshold tuning that overfits held-out sets without future validity guarantees, CPA deploys split conformal prediction to achieve distribution-free marginal coverage for any declared threat configuration \(w\). Given an exchangeable calibration split \(\{(X_i, Y_i, W_i)\}_{i=1}^n\), the auditor computes the nonconformity score at the ground-truth identity \(T_i = s(X_i, Y_i; w)\) for each calibration instance. Sorting these scores as \(T_{(1)} \le \dots \le T_{(n)}\), the conformal cutoff at miscoverage level \(\alpha \in (0, 1)\) is defined by the order statistic: $\(\hat{q}_\alpha := T_{(k)}, \quad \text{where } k = \lceil(n+1)(1-\alpha)\rceil\)$ For an unseen document \((X_{n+1}, W_{n+1})\), the calibrated ambiguity set retains all candidates whose nonconformity score falls below the cutoff: \(C_\alpha(x, w) = \{y \in \mathcal{Y}(x, w) : s(x, y; w) \le \hat{q}_\alpha\}\). Under the exchangeability of calibration and evaluation samples, the true identity is guaranteed to reside in \(C_\alpha(X_{n+1}, w)\) with probability at least \(1-\alpha\).
3. Open-World Truncation & Ambiguity Certification: Bridging Adversarial Constraints and Release Rules Practical attackers facing vast candidate registries often truncate scoring to top-\(K\) retrieved candidates due to compute budgets, violating closed-world assumptions. CPA formalizes this open-world failure via candidate-miss probability \(\rho(w) := \Pr(Y \notin \mathcal{Y}(X, w))\). The framework proves that conditional on retaining the true candidate, coverage holds exactly, while unconditional coverage degrades gracefully: \(\Pr(Y \in C_\alpha(X, w)) \ge (1 - \rho(w))(1 - \alpha) \ge 1 - (\rho(w) + \alpha)\). To translate certified sets into operational policies, CPA introduces the inverse ambiguity leakage proxy \(L(x, w) := 1 / \max\{1, |C_\alpha(x, w)|\}\). Unlike uncalibrated Top-1 accuracy, \(|C_\alpha(x, w)|\) directly quantifies the remaining suspect pool size at statistical confidence \(1-\alpha\), aligning naturally with regulatory thresholds (e.g., the 0.09 re-identification threshold established by the Information and Privacy Commissioner of Ontario).
A Worked Example¶
Consider a healthcare provider preparing to release a clinical narrative describing a "45-year-old female nephrologist treated for a rare hematologic disorder in Brisbane", where the external reference registry contains 1,000 potential subjects. The provider selects confidence \(1-\alpha = 0.95\) and computes the conformal cutoff \(\hat{q}_{0.05} = 0.25\) over 100 held-out cases. 1. Weak Attacker (Demographic metadata only): The attacker queries coarse demographic attributes. Candidate similarity scores are diffuse across dozens of local physicians. Accumulating mass to the true patient requires summing hundreds of candidates, pushing the score well past 0.25. The resulting ambiguity set spans 320 candidates (\(|C_{0.05}| = 320\), \(L \approx 0.003\)), certifying high residual ambiguity and allowing release. 2. LLM-Augmented Attacker (Reasoning over rare disease and regional registries): The attacker employs Llama-3 to extract clinical nuances and match them against hospital directories. The top-3 candidates concentrate 0.10, 0.08, and 0.06 of the probability mass. Because the true patient is ranked second (cumulative score \(0.18 \le 0.25\)), the certified ambiguity set shrinks to only 3 individuals (\(|C_{0.05}| = 3\), \(L = 0.333\)). The auditor flags an unacceptable privacy violation and withholds the record for further generalization.
Key Experimental Results¶
Main Results¶
The authors evaluated CPA across four benchmark corpora: TAB (court cases), WikiBio (biographies), TextWash (person descriptions), and the Blog Authorship corpus. The table below reports auditing results on TAB under direct document release versus quasi-identifier redaction across three auxiliary knowledge levels (K1 metadata only, K2 extracted keywords, K3 case text) and LLM-assisted clue extraction (\(\alpha = 0.05\)).
| Attacker Setting | Top-1 Acc | Coverage (Cov.) | Median |C| | Mean |C| | Mean 1/|C| |
|---|---|---|---|---|---|
| TAB-Direct | |||||
| K1 metadata / direct | 0.052 | 0.929 | 1268 | 1179.5 | 0.000957 |
| K2 keywords / direct | 0.973 | 0.973 | 1 | 1.0 | 1.0000 |
| K3 case-text / direct | 0.994 | 0.994 | 1 | 1.0 | 1.0000 |
| K2 keywords / LLM-clues | 0.715 | 0.970 | 20 | 20.1 | 0.0499 |
| TAB-Direct (Quasi-ID) | |||||
| K1 metadata / direct | 0.003 | 0.932 | 1268 | 1173.6 | 0.0017 |
| K2 keywords / direct | 0.872 | 0.953 | 4 | 3.7 | 0.2717 |
| K3 case-text / direct | 0.964 | 0.964 | 1 | 1.0 | 1.0000 |
| K2 keywords / LLM-clues | 0.615 | 0.945 | 27 | 27.1 | 0.0369 |
Ablation Study¶
The table below compares different nonconformity score constructors (APS mass score, rank-based score, and raw model probability) across WikiBio, Blog Authorship, and TAB at nominal coverage level \(\alpha = 0.05\):
| Benchmark Suite / Attacker | Score Constructor | Empirical Coverage | Median |C| | Mean |C| |
|---|---|---|---|---|
| WikiBio + Llama-3.1-8B | APS mass | 0.950 | 189 | 186.87 |
| WikiBio + Llama-3.1-8B | Rank-based | 0.950 | 179 | 179.00 |
| WikiBio + Llama-3.1-8B | Raw probability | 0.960 | 212 | 209.43 |
| Blog W10 + Llama | APS mass | 0.950 | 8 | 8.34 |
| Blog W10 + Llama | Rank-based | 0.962 | 9 | 9.00 |
| TAB K3 + LLM-clues | APS mass | 0.967 | 31 | 30.80 |
| TAB K3 + LLM-clues | Raw probability | 0.951 | 19 | 24.47 |
Key Findings¶
- Statistical Validity Holds Across Threat Configurations: Across benchmarks and attacker configurations, empirical coverage reliably reaches the nominal \(1-\alpha = 0.95\) target, proving the validity of split conformal calibration in unstructured text settings.
- Privacy Leakage is Co-Determined by Release Design and Auxiliary Knowledge: On TAB, under K1 metadata, certified ambiguity spans nearly the entire registry (median \(|C| = 1268\)), confirming robust privacy preservation despite weak redaction; under K2/K3 text profiles, ambiguity collapses to singletons (\(|C| = 1\)), revealing severe identity exposure.
- LLM Clue Extraction Amplification is Highly Context-Dependent: In TextWash fictional descriptions where external web context is absent, LLM clues from GPT-5 or Llama do not reduce ambiguity; on famous individuals, however, Llama clue extraction shrinks the median ambiguity set from 120 to 90, demonstrating that LLM reasoning specifically amplifies re-identification when correlated world knowledge exists.
- Constructor Flexibility Extends to Ranking-Only Attackers: The score ablation demonstrates that rank-based nonconformity achieves 0.950 coverage matching APS (median \(|C| = 179\) vs 189 on WikiBio), confirming that auditors can certify adversaries that output strictly ordered candidate lists without access to numerical scores.
Highlights & Insights¶
- Transforms Uncalibrated Attack Success into Finite-Sample Certificates: Traditional empirical auditing reports noisy point estimates; CPA turns arbitrary attacker rankings into a certified short-list of suspects with guaranteed marginal coverage.
- Seamless Black-Box Integration for Proprietary LLMs: By sampling forced-choice responses to estimate empirical frequencies, CPA provides rigorous privacy certificates for proprietary API models without requiring logit access.
- Provides an Interpretable Operational Dial: The miscoverage rate \(\alpha\) offers an explicit trade-off between statistical confidence and certified set tightness, allowing organizations to operationalize numeric safety rules against declared threat models.
Limitations & Future Work¶
- Certificates Bound to Declared Threat Models: Conformal validity relies strictly on exchangeability within the declared candidate pool, auxiliary knowledge level, and prompt pipeline. Distribution shifts (e.g., unexpected web snapshots or prompt drift) violate calibration and lead to under-coverage, as demonstrated in stress tests.
- Computational Scalability in Open-World Search: For massive candidate pools exceeding millions of individuals, scoring all entities is computationally prohibitive; top-\(K\) truncation introduces open-world candidate misses that lower unconditional coverage.
- Future Directions: Extending the framework to weighted conformal prediction under covariate shifts, subgroup-conditional Mondrian conformal prediction, and applying conformal auditing to membership inference attacks.
Related Work & Insights¶
- vs Differential Privacy (DP): DP enforces algorithmic stability via randomized mechanisms during training or generation, often destroying text utility; CPA provides post-hoc, task-level risk auditing without modifying released documents or compromising utility.
- vs Empirical Privacy Auditing: Standard empirical audits rely on point-estimate attack success rates that fail to generalize; CPA produces distribution-free set-valued certificates with finite-sample statistical coverage.
- vs Statistical Disclosure Control (SDC) & \(k\)-Anonymity: Classical \(k\)-anonymity evaluates structured microdata tables using frequency-based population assumptions; CPA reformulates \(k\)-anonymity for unstructured natural text under modern LLM-assisted adversaries.
Rating¶
- Novelty: โญโญโญโญโญ Formulates release-time text privacy auditing as conformal prediction, bridging empirical attacks and statistical guarantees.
- Experimental Thoroughness: โญโญโญโญโญ Comprehensive evaluations across four benchmarks, open/closed LLMs, knowledge ladders, distribution shifts, and sample-size ablations.
- Writing Quality: โญโญโญโญโญ Mathematically rigorous, well-structured, with clear theoretical proofs and intuitive empirical discussions.
- Value: โญโญโญโญโญ Provides an operational tool for organizations releasing sensitive text under stringent privacy compliance requirements.