Conformal Privacy Auditing: Calibrated Re-identification Attacks with Statistical Guarantees
Abstract Overview
This paper introduces Conformal Privacy Auditing (CPA), a release-time privacy auditing framework for text that quantifies document-level re-identification risk under a declared attacker model. CPA applies split conformal prediction to attacker scores and outputs an ambiguity set of candidate identities for each released document, with a finite-sample guarantee that the true identity is included with user-chosen confidence under exchangeability. The framework is designed to work with both retrieval-based and LLM-assisted attackers, including sampling-only black-box APIs as well as models with score access. Experiments across several text release benchmarks show that CPA can provide calibrated, threat-model-specific certificates while exposing how auxiliary knowledge, release mechanisms, and candidate-pool assumptions change certified identifiability.
Novelty
The main novelty is framing text privacy auditing as conformal set prediction for identity linkage, yielding per-document statistical certificates rather than only empirical attack success rates. The method is also distinctive in supporting both logit-access and sampling-only attacker interfaces within a unified black-box auditing framework.
Results
Across multiple benchmarks and attacker configurations, CPA generally attains empirical coverage close to the target conformal level, indicating that its ambiguity sets are calibrated for the declared threat model. The reported certificates show that stronger auxiliary knowledge can collapse ambiguity sets, that LLM-assisted clue extraction can increase linkability in some settings but not uniformly across models, and that candidate-pool size or truncation can materially affect the certified risk.
Key Points
- CPA outputs conformal ambiguity sets whose size serves as an interpretable certificate of residual attacker uncertainty for each released document.
- The method supports retrieval-based and LLM-based re-identification pipelines, including sampling-only access for proprietary API models.
- Experiments indicate that certified identifiability depends strongly on the attacker configuration, especially available side information, model choice, and candidate-pool construction.