A False Sense of Privacy: Evaluating Textual Data Sanitization Beyond Surface-level Privacy Leakage

1. Problem Statement

The paper addresses a critical gap in data privacy for unstructured textual data (e.g., medical records, chat logs). Current sanitization methods typically rely on removing Personally Identifiable Information (PII) (names, addresses, dates) or generating synthetic data. However, these methods often provide a "false sense of privacy."

• The Core Issue: Even after explicit identifiers are removed, nuanced textual markers (contextual details, routine activities, semantic patterns) can be used by adversaries with auxiliary information (e.g., social media posts, public records) to re-identify individuals and infer sensitive attributes (e.g., mental health status, substance use, age).
• Limitations of Current Evaluation: Existing privacy evaluations rely heavily on lexical metrics (exact string matching, ROUGE) or simple PII detection. These fail to capture semantic leakage, where the meaning of sensitive information is preserved even if the specific words are changed. Furthermore, standard re-identification attacks assume a one-to-one mapping between original and sanitized records, which does not hold for dataset-level synthesis methods.

2. Methodology: The Re-identification Attack Framework

The authors propose a novel framework to quantify privacy risks by simulating a re-identification attack. The framework operates in two stages:

A. Data Decomposition (Atomization)

To handle the complexity of unstructured text, the framework uses FActScore principles to decompose each document into atomic claims (indivisible pieces of information).

• Example: A medical record is broken down into claims like "Patient is 24," "Patient uses marijuana," "Patient lost job."

B. Stage I: Linking

The adversary attempts to link auxiliary information ($\tilde{x}$) to records in the sanitized dataset ($D_{sanitized}$).

• Auxiliary Information: Simulated by randomly selecting a subset of atomic claims from the original record and paraphrasing them to mimic real-world information transmission (e.g., "Patient sleeps in" $\to$ "Patient starts day by sleeping in").
• Retrieval: A semantic retriever (GRIT) embeds the auxiliary claims and the sanitized documents into a high-dimensional vector space.
• Matching: The system performs independent similarity searches for each claim and uses majority voting to select the most likely linked record in the sanitized dataset.

C. Stage II: Semantic Scoring

Once a record is linked, the framework measures information leakage by comparing the linked sanitized record against the original private record at the atomic claim level.

• Metric ($\mu$): A Large Language Model (LLM) evaluates the semantic distance between the original claim and the sanitized claim on a 3-point scale:
  1. Identical information (Leakage).
  2. Different but similar information.
  3. Unsupported/No information (Privacy preserved).
• Privacy Score: Normalized to $[0, 1]$, where a lower score indicates higher leakage (failure) and a higher score indicates better privacy.

D. Utility Evaluation

To assess the Privacy-Utility Tradeoff, the framework measures:

• Task Utility: Accuracy on downstream tasks (e.g., answering medical questions based on sanitized profiles).
• Text Quality: Coherence and distribution preservation (evaluated via GPT-4o).

3. Experimental Setup

The framework was evaluated on two real-world datasets:

1. MedQA: Medical licensing exam questions with patient profiles.
2. WildChat: 1 million real user-ChatGPT interactions containing sensitive disclosures.

Sanitization Methods Evaluated:

• Identifier Removal (Sample-level):
  • Commercial PII removal (Azure AI).
  • LLM-based Iterative Anonymization (Staab et al.).
  • Span Sanitization (Dou et al.).
  • Sanitize & Paraphrase.
• Data Synthesis (Dataset-level):
  • Vanilla Synthesis (Fine-tuning without privacy).
  • Differentially Private (DP) Synthesis: Fine-tuning with DP guarantees at various privacy budgets ($\epsilon \in \{3, 64, 1024, \infty\}$).

4. Key Results

A. The "False Sense of Privacy" in Identifier Removal

• Lexical vs. Semantic Gap: Lexical metrics (ROUGE) consistently overestimate privacy. For example, Azure AI PII tool showed a lexical privacy score of 0.73 but a semantic privacy score of only 0.26.
• High Leakage: Despite removing names and dates, 74% of the original information in MedQA remained inferable using Azure's tool. Adversaries could successfully infer sensitive attributes like mental health status and substance use history from "innocuous" details like social habits or job loss.
• Mechanism Failure: Commercial tools focus on surface-level PII but fail to sanitize semantic categories (e.g., "Social History" or "History of Present Illness") that enable inference.

B. Data Synthesis and Differential Privacy

• Non-DP Synthesis: Standard data synthesis (without DP) still leaks 48% of information (semantic score 0.52 on MedQA).
• DP Effectiveness: Differential Privacy (DP) significantly improves privacy. At $\epsilon=3$, semantic privacy scores rose to 0.92 (MedQA), effectively preventing re-identification.
• The Utility Cost: The privacy gain from DP comes at a severe cost to utility.
  • On MedQA, DP-synthesized data had lower utility (0.42) than a baseline that simply removed the private notes (0.44).
  • Text coherence dropped significantly (e.g., from 3.28 to 1.63 on WildChat), resulting in semantically inconsistent or hallucinated medical records.

C. Robustness of the Framework

• Auxiliary Information: The framework remains effective even when auxiliary information is paraphrased, proving that lexical changes do not hide semantic leakage.
• Model Agnostic: Results were consistent across different LLMs used for evaluation (LLaMA 3.1 8B vs. GPT-4o).
• Human Validation: Human evaluations confirmed the LLM-based semantic scoring had a high correlation (Spearman $\rho \approx 0.95$) with human judgment, outperforming ROUGE ($\rho \approx 0.81$).

5. Key Contributions

1. New Evaluation Framework: Introduced a semantic-based, dataset-level re-identification attack framework that quantifies privacy leakage beyond surface-level identifiers.
2. Demonstration of Semantic Leakage: Proved that current state-of-the-art sanitization methods (including commercial PII tools) fail to protect against inference attacks using auxiliary information, leaving up to 74% of sensitive data inferable.
3. Privacy-Utility Tradeoff Analysis: Provided empirical evidence that while DP offers strong privacy, it currently degrades utility to the point of being unusable for complex tasks like medical diagnosis, whereas non-DP methods preserve utility but fail privacy.
4. Critique of Lexical Metrics: Showed that standard lexical metrics (ROUGE) create a false sense of security by ignoring semantic equivalence.

6. Significance and Conclusion

The paper fundamentally challenges the assumption that removing PII or using basic sanitization is sufficient for privacy in the era of Large Language Models.

• Implication for Practitioners: Organizations relying on commercial PII tools or simple text rewriting are likely exposing users to significant re-identification risks.
• Future Directions: The authors highlight the urgent need for semantic-level privacy protection methods that can preserve data utility while preventing inference attacks. Currently, Differential Privacy is the only method offering robust protection, but the field must advance to solve the utility degradation problem associated with it.

In summary, the paper argues that we must move from lexical assessment to semantic evaluation to truly understand and mitigate privacy risks in textual data releases.