Conformal Privacy Auditing: Calibrated Re-identification Attacks with Statistical Guarantees

Shuo Huang; Gholamreza Haffari; Xingliang Yuan; Ting Yu; Lizhen Qu

cs.CRSep 18, 2026

Conformal Privacy Auditing: Calibrated Re-identification Attacks with Statistical Guarantees

Authors: Shuo Huang, Gholamreza Haffari, Xingliang Yuan, Ting Yu, Lizhen Qu

Organizations: Monash University · The University of Melbourne · Mohamed bin Zayed University of Artificial Intelligence

Abstract

Empirical identity leakage from released text is increasingly driven by attackers that combine large language models (LLMs) with auxiliary knowledge to link documents to individuals. Existing audits typically report success rates for specific attack pipelines but lack finite-sample statistical guarantees, while training-time protections such as differential privacy are difficult to translate into release-time decisions for individual natural-language documents. We introduce Conformal Privacy Auditing(CPA), a distribution-free calibration framework that provides a statistical certificate of re-identification risk for each released document against LLM-empowered adversaries. CPA outputs a conformal ambiguity set of candidate identities that is guaranteed to contain the true identity with user-chosen confidence under exchangeability, together with an interpretable leakage proxy derived from set size. CPA supports both logit-access and sampling-only attackers, enabling audits of open-source models and proprietary API models in a unified framework. Across multiple release benchmarks and attacker configurations, CPA achieves calibrated coverage and reveals sharp shifts in certified identifiability as auxiliary knowledge, LLM augmentation, and release mechanisms vary, providing a statistically grounded basis for reporting and comparing release-time linkage risk across attacker configurations, datasets, and release mechanisms alike.

Figures & tables

Figure 1: CPA auditing vs. top-1 prediction. A conventional attack pipeline (top) outputs a single point prediction; CPA (bottom) calibrates the same attacker into a conformal ambiguity set that contains the true identity with probability at least $1-\alpha$ under the declared threat configuration.

Attacker setting	Top-1	Cov.	Med. $\|C\|$	Mean $\|C\|$	Mean $1/\|C\|$
TAB-Direct
K1 meta / direct	0.052	0.929	1268	1179.5	9.57e-04
K2 keywords / direct	0.973	0.973	1	1	1.0000
K3 case-text / direct	0.994	0.994	1	1	1.0000
K2 keywords / LLM-clues	0.715	0.970	20	20.1	0.0499
TAB-Direct (Quasi-ID)

Table 1: TAB linkage auditing (

\alpha=0.05

). Smaller ambiguity sets indicate higher certified identifiability. direct uses the released document as the retrieval query; LLM-clues uses an LLM to extract a short clue string from the released document before retrieval. meta/keywords/case-text describe which fields are available in the candidate profile database. All suites use split conformal calibration with disjoint calibration/test partitions; the full declared threat configuration per suite is summarized in Table 8 in Appendix D .

Attacker setting	Top-1	Coverage	Median $\|C_{\alpha}\|$	Mean $\|C_{\alpha}\|$	$\mathbb{E}[1/\|C_{\alpha}\|]$	$\hat{q}_{\alpha}$
Direct query	0.362	0.956	264	254.98	0.00466	0.277
LLM clues (Llama-3.1-8B)	0.420	0.950	189	186.87	0.00562	0.2
LLM clues (Qwen3-8B)	0.380	0.958	265	255.69	0.00465	0.277

Table 2: Retrieval-CPA on WikiBio (500 released bios; 1k candidates) under direct query vs LLM-assisted clue extraction (

\alpha=0.05

), with split conformal calibration over disjoint calibration/test partitions of the released bios; the full declared threat configuration is summarized in Table 8 in Appendix D .

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

s(x,y;w)=\sum_{\begin{subarray}{c}y^{\prime}\in\mathcal{Y}(x,w):\\ p_{A}(y^{\prime}\mid x,w)\geq p_{A}(y\mid x,w)\end{subarray}}p_{A}(y^{\prime}\mid x,w).

Appendix

Algorithm 1 Split Conformal Privacy Auditing (CPA)

Dataset	Unit	Total	Split / subset	Avg. words
TAB (ECHR)	documents	1,268	train/dev/test = 1014/127/127	train 1343.4; dev 874.6; test 843.4
TextWash	biographies	1,202 orig + 1,202 anon	famous 401, semifamous 400, fiction/other 401	orig 130.5; anon 127.7
Blog Authorship	authors	19,320	balanced male/female author roster	9.74 posts/author
WikiBio	biographies	1,000	one category in the prepared audit slice	orig 102.7; anon 101.9

Appendix

Table 3: Dataset statistics for the release-audit experiments. For TAB we report split sizes from the benchmark JSON files; for TextWash we report file counts from the original and anonymized person-description trees; for Blog we report author-level XML statistics; and for WikiBio we report the prepared audit slice used by the canonical experiment runner in all reported WikiBio suites and ablations.

Attacker setting	Top-1	Coverage	Median $\|C_{\alpha}\|$	Mean $\|C_{\alpha}\|$	$\mathbb{E}[1/\|C_{\alpha}\|]$	$\hat{q}_{\alpha}$
W=1 posts/author	0.087	0.946	222	200.50	0.00566	0.948
W=3 posts/author	0.143	0.956	210	191.82	0.00604	0.903
W=10 posts/author	0.209	0.946	176	147.14	0.00677	0.763

Appendix

Table 4: Retrieval-CPA on Blog Authorship under increasing attacker side information (number of posts per author;

\alpha=0.05

), with split conformal calibration over disjoint calibration/test partitions of the released posts; the full declared threat configuration is summarized in Table 8 in Appendix D .

fiction
Attacker	Top-1	Cov.	Med. $\|C_{\alpha}\|$	Mean $\|C_{\alpha}\|$
Direct query	0.500	0.970	169.5	172.44
GPT-5 clues	0.500	0.970	169.5	172.44
Llama clues	0.600	0.970	171.0	174.26
semifamous
Direct query	0.380	0.910	155.0	167.12

Appendix

Table 5: TextWash Retrieval-CPA under matched budgets. Retrieval-CPA on TextWash under direct retrieval vs. LLM-assisted clue extraction (

\alpha=0.05

). All attackers are evaluated on the same capped split with

n_{\mathrm{cal}}=n_{\mathrm{test}}=100

per category, so certified set sizes are directly comparable across attackers; LLM rows use cached clue outputs throughout.

Symbol	Meaning
$x,X$	Released document (possibly anonymized/rewritten)
$y,Y$	True identity of the document subject
$\mathcal{U}$	Reference population of identities
$w,W$	Attacker knowledge level / threat configuration (side information and tooling)
$\mathcal{Y}(x,w)$	Finite candidate pool available to the attacker
$K$	Top- $K$ truncation level of the candidate pool (engineering choice)

Appendix

Table 6: Notation used throughout the paper.

Level	Attacker access / capability
K1 (weak)	Profiles contain only coarse structured fields (e.g., occupation bucket, coarse location, age range). Retrieval query uses released text directly.
K2 (medium)	Profiles add additional non-identifying evidence facts (e.g., coarsened events/keywords). Retrieval uses released text; no LLM assistance.
K3 (strong)	LLM-assisted clue extraction from released text produces a query expansion (optional), and/or profile is augmented (RAG/web search).

Appendix

Table 7: Knowledge ladder (side information

W

) used to instantiate attacker pipelines in our experiments.

Suite	Candidate pool (size)	Query mode	LLM/web aug.	World
TAB K1–K3	case records (1268)	direct	none	closed
TAB K2/K3 + clues	case records (1268)	direct+clues	LLM clues	closed
WikiBio direct	profile rows (1000)	direct	none	closed
WikiBio + clues	top- $K{=}200$ of 1000	direct+clues	LLM clues	top- $K$ truncated
Blog W $\in\{1,3,10\}$	author registry	direct	none	closed
TextWash direct (matched)	category ( $\approx$ 400)	direct	none	closed

Appendix

Table 8: Declared threat configuration for each experimental suite. “direct” uses the released text as the retrieval query; “direct+clues” appends LLM-extracted clues. The matched TextWash suites use

n_{\mathrm{cal}}{=}n_{\mathrm{test}}{=}100

per category (Table 5 ), and the

m

-ablation sweeps the per-document sampling budget

m\in\{1,3,5,10\}

(Table 13 ).

Panel of Figure 2 — Figure 2: Effect of the miscoverage level $\alpha$ on TAB (direct retrieval, quasi-identifier release): mean leakage proxy $\mathbb{E}[1/|C_{\alpha}|]$ (left), empirical coverage (center), and median certified set size $|C_{\alpha}|$ (right). Smaller $\alpha$ certifies residual ambiguity more conservatively; larger $\alpha$ yields smaller sets with weaker statistical protection.

Cal. $\rightarrow$ test	Cov.	Med. $\|C_{\alpha}\|$	Mean $\|C_{\alpha}\|$
TAB direct $\rightarrow$ direct	0.965	1	1.000
TAB direct $\rightarrow$ quasi-ID	0.923	1	1.000
TAB quasi-ID $\rightarrow$ quasi-ID	0.965	3	2.658
Blog W10 $\rightarrow$ W10	0.940	176	175.691
Blog W10 $\rightarrow$ W1	0.835	176	175.224

Appendix

Table 9: Exchangeability stress tests (

\alpha=0.05

). Matched calibration/test configurations achieve target coverage; shifted configurations under-cover, so recalibration is the operational protocol under suspected attacker-side or release-side drift.

Suite	$K$	Miss	Cond.	Uncond.	Med.
TW fiction direct	50	0.160	1.000	0.840	50
TW fiction direct	100	0.080	1.000	0.920	100
TW fiction direct	200	0.000	0.970	0.970	169.5
TW famous direct	50	0.110	1.000	0.890	50
TW famous direct	100	0.030	1.000	0.970	100
WB + Llama clues	50	0.118	1.000	0.882	50

Appendix

Table 10: Candidate-pool / top-

K

truncation stress tests (

\alpha=0.05

). TW = TextWash, WB = WikiBio. “Miss” is the empirical candidate-miss rate; “Cond.”/“Uncond.” are coverage conditional on the true identity being retained in the truncated pool and unconditional coverage; “Med.” is the median certified set size

|C_{\alpha}|

over the evaluated test split.

Attacker	Score	Cov.	Med.	Mean
WikiBio + Llama	APS	0.950	189	186.870
WikiBio + Llama	rank	0.950	179	179.000
WikiBio + Llama	prob.	0.960	212	209.434
Blog W10 + Llama	APS	0.950	8	8.341
Blog W10 + Llama	rank	0.962	9	9.000
TAB K3 + clues	APS	0.967	31	30.803

Appendix

Table 11: Score-constructor ablation for cached LLM-clue attackers (

\alpha=0.05

). “Med.”/“Mean” refer to

|C_{\alpha}|

. All constructors achieve valid coverage; efficiency (certified set size) varies moderately across constructors and across the different attacker pipelines.

$n_{\mathrm{cal}}$	Avg. coverage	Avg. median $\|C_{\alpha}\|$
50	0.962	151.2
100	0.957	148.2
150	0.927	140.3

Appendix

Table 12: Calibration-set-size ablation on matched TextWash direct retrieval (

\alpha=0.05

n_{\mathrm{test}}=100

), averaged over the three TextWash categories.

$m$	Top-1	Cov.	Med. $\|C_{\alpha}\|$	Mean $\|C_{\alpha}\|$
1	0.490	0.980	120	120.020
3	0.510	0.970	83	82.590
5	0.510	0.970	82	82.110
10	0.490	0.970	78	78.060

Appendix

Table 13: Sampling-budget ablation with Llama-3.1-8B-Instruct on TextWash famous (

\alpha=0.05

n_{\mathrm{cal}}=n_{\mathrm{test}}=100

, candidate-miss rate

0

). Coverage stays above target while larger budgets yield tighter certified sets at the same nominal coverage level.

Privacy Auditing

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

See all 81 papers

Natural Identifiers for Privacy and Data Audits in Large Language Models
Jun 23, 2026Lorenzo Rossi, Bartłomiej Marek, Franziska Boenisch +1Privacy Auditing LLM Auditing
CISPA Helmholtz Center for Information Security
Beyond Direct Identifiers: Probabilistic Privacy Risk Estimation for Privacy-Conscious LLM Query Delegation
Aug 10, 2026Li Siyan, Zhou Yu, Julia HirschbergPrivacy-Preserving Language Models Privacy Leakage in Language Models
Department of Computer Science Columbia University
AgentDoxx: Agentic Re-identification of Anonymized Text with Web Search
Oct 4, 2026Jianing Wen, Tianshi LiPrivacy Leakage in Language Models AI Agent Security Benchmarks
Khoury College of Computer Sciences Northeastern University Boston, MA

Jun 23, 2026J/K move · Enter open · S save

Natural Identifiers for Privacy and Data Audits in Large Language Models

Lorenzo Rossi, Bartłomiej Marek, Franziska Boenisch, Adam Dziedzic

CISPA Helmholtz Center for Information Security

Privacy Auditing LLM Auditing Differential Privacy

Open paper AskPDF arXiv

Assessing the privacy of large language models (LLMs) presents significant challenges. In particular, most existing methods for auditing differential privacy require the insertion of specially crafted canary data during training, making them impractical for auditing already-trained models without costly retraining. Additionally, dataset inference, which audits whether a suspect dataset was used to train a model, is infeasible without access to a private non-member held-out dataset. Yet, such held-out datasets are often unavailable or difficult to construct for real-world cases since they have to be from the same distribution (IID) as the suspect data. These limitations severely hinder the ability to conduct scalable, post-hoc audits. To enable such audits, this work introduces natural identifiers (NIDs) as a novel solution to the above-mentioned challenges. NIDs are structured random strings, such as cryptographic hashes and shortened URLs, naturally occurring in common LLM training datasets. Their format enables the generation of unlimited additional random strings from the same distribution, which can act as alternative canaries for audits and as same-distribution held-out data for dataset inference. Our evaluation highlights that indeed, using NIDs, we can facilitate post-hoc differential privacy auditing without any retraining and enable dataset inference for any suspect dataset containing NIDs without the need for a private non-member held-out dataset.

Abstract

Privacy Auditing

Explore similar work

Natural Identifiers for Privacy and Data Audits in Large Language Models

Beyond Direct Identifiers: Probabilistic Privacy Risk Estimation for Privacy-Conscious LLM Query Delegation

AgentDoxx: Agentic Re-identification of Anonymized Text with Web Search