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

Rui Xin, Niloofar Mireshghallah, Shuyue Stella Li, Michael Duan, Hyunwoo Kim, Yejin Choi, Yulia Tsvetkov, Sewoong Oh, Pang Wei Koh

TL;DR

Current text sanitization methods—ranging from simple PII removal to advanced LLM-based synthesis—often provide a "false sense of privacy" by focusing on surface-level identifiers while ignoring semantic markers. This paper introduces a novel evaluation framework that uses semantic retrieval and atomic claim verification to prove that even "sanitized" data remains highly vulnerable to re-identification attacks using minimal auxiliary information.

What Problem Does This Paper Address?

When researchers or companies share sensitive text data (like medical records or chat logs), they usually "sanitize" it by removing Personally Identifiable Information (PII) like names, dates, and addresses. The assumption is that once the explicit identifiers are gone, the individual's privacy is protected.

However, the authors argue this is an illusion. Text contains nuanced contextual markers—unique combinations of social activities, medical histories, or behavioral patterns—that can act as "quasi-identifiers." If an adversary has even a small amount of external "auxiliary information" about a person (e.g., from social media), they can link that person to a specific record in a sanitized dataset.

Furthermore, traditional privacy metrics rely on lexical similarity (like ROUGE scores), which only check if the exact words are the same. These metrics fail to capture semantic leakage, where the same sensitive information is present but expressed in different words.

Methods

The authors propose a two-stage re-identification attack framework to quantify privacy risks:

  1. Stage I: Linking. The framework simulates an adversary who has "auxiliary information" (a few facts about an individual). It uses a state-of-the-art semantic retriever (GRIT) to find the most likely match for this information within the sanitized dataset.
  2. Stage II: Semantic Scoring. Once a record is linked, the framework uses an LLM (LLaMA 3.1 8B) to break the original private document into "atomic claims." It then checks how many of these sensitive claims can still be inferred from the sanitized version.
Fig. 1: Our privacy evaluation framework overview. For a given sanitization method, we obtain the (2) sanitized dataset by applying the method to the (1) original dataset. In the linking stage, we use (3) auxiliary information to find potential matches in the sanitized dataset using a semantic retriever to obtain the (5) linked record. Next, in the semantic scoring stage, we analyze the linked record against the corresponding (4) original record to identify semantic information leakage. In the linked record, text highlighted in yellow indicates detected leakage, and in cyan indicates content used for the linking process. The framework calculates utility scores to measure the practical value of the sanitized dataset and a privacy score based on the detected information leakage.

The authors evaluated two main categories of sanitization:

  • Identifier Removal: Tools like Azure AI PII detection and LLM-based anonymizers that mask specific spans of text.
  • Data Synthesis: Generating entirely new synthetic text based on the original data, including versions using Differential Privacy (DP) to provide formal mathematical guarantees.

Datasets

The framework was tested on two diverse, real-world datasets:

  • MedQA: A dataset of medical case summaries. This represents high-stakes, specialized data where privacy is legally mandated (HIPAA).
  • WildChat: A collection of 1 million real-world user-ChatGPT interactions, containing diverse conversational styles and varied sensitive personal disclosures.

Key Insights and Ideas

  • The Lexical-Semantic Gap: Lexical metrics consistently overestimate privacy. A sanitization method might change every word in a sentence (resulting in a high "privacy" score lexically), but if the underlying facts remain the same, the semantic privacy score will correctly identify a failure.
  • Commercial Tools Fall Short: Industry-standard tools like Azure’s PII remover are excellent at finding names but ignore categories like "History of Present Illness" or "Social History," which contain the very details that make a record unique and linkable.
  • The Utility Tax of True Privacy: Differential Privacy (DP) was the only method that effectively blocked semantic leakage. However, it comes at a massive cost to utility. At high privacy settings, the generated text often becomes incoherent or factually contradictory.
Fig. 2: Overview of the data sanitization techniques evaluated using our framework. We evaluate two main categories: identifier removal methods and data synthesis methods. Identifier removal methods operate at the sample level, maintaining a one-to-one correspondence between original and sanitized records. In contrast, data synthesis methods operate at the dataset level, where each sanitized record may derive information from multiple original records.

Key Results

  • Azure AI PII Tool Failure: In the MedQA dataset, Azure's tool failed to protect 74% of the original information. While it removed names, the medical context was so rich that re-identification remained trivial.
  • Synthesis without DP is insufficient: Even generating "new" synthetic text without formal privacy constraints still leaked 48% of the information.
  • DP Trade-offs: As shown in the table below, while decreasing the privacy budget ($\epsilon$) increases the Semantic Distance (better privacy), it causes a sharp drop in Task Utility and Text Coherence. For MedQA, utility dropped from 0.61 to 0.41 when moving from vanilla synthesis to strong DP.
TABLE II: Privacy-utility comparison of data synthesis using differential privacy, with different levels of privacy budget ε, across datasets. For the WildChat dataset, the task utility is measured as the chi-squared distance between the synthesized data’s label distribution and the original dataset’s distribution. Values below 0 indicate that the synthesized distribution deviates substantially from the original distribution. Lower values of ε provide stronger privacy guarantees. Results demonstrate that differential privacy effectively prevents privacy leakage but yields lower utility scores compared to other methods.

Limitations and Future Work

  • Lower Bound on Risk: The authors emphasize that their framework provides a lower bound on information leakage. A low score proves a dataset is unsafe, but a high score doesn't guarantee it is safe against every possible future attack.
  • Hallucinations: In rare cases, especially with DP-generated text, the LLM evaluator might "hallucinate" a match that isn't actually there, slightly skewing scores.
  • Contextual Relevance: The current metric treats all atomic claims as equally sensitive. Future work could involve weighting claims based on how "private" they actually are in a given context (e.g., a rare disease vs. a common cold).
  • Scope: The study did not cover "model unlearning" techniques, which is a growing area of interest for privacy in LLMs.

Summary updated

Abstract

Sanitizing sensitive text data typically involves removing personally identifiable information (PII) or generating synthetic data under the assumption that these methods adequately protect privacy; however, their effectiveness is often only assessed by measuring the leakage of explicit identifiers but ignoring nuanced textual markers that can lead to re-identification. We challenge the above illusion of privacy by proposing a new framework that evaluates re-identification attacks to quantify individual privacy risks upon data release. Our approach shows that seemingly innocuous auxiliary information -- such as routine social activities -- can be used to infer sensitive attributes like age or substance use history from sanitized data. For instance, we demonstrate that Azure's commercial PII removal tool fails to protect 74\% of information in the MedQA dataset. Although differential privacy mitigates these risks to some extent, it significantly reduces the utility of the sanitized text for downstream tasks. Our findings indicate that current sanitization techniques offer a \textit{false sense of privacy}, highlighting the need for more robust methods that protect against semantic-level information leakage.
BibTeX
@inproceedings{xin2024false,
  author = {Rui Xin and Niloofar Mireshghallah and Shuyue Stella Li and Michael Duan and Hyunwoo Kim and Yejin Choi and Yulia Tsvetkov and Sewoong Oh and Pang Wei Koh},
  title = {{A False Sense of Privacy: Evaluating Textual Data Sanitization Beyond Surface-level Privacy Leakage}},
  booktitle = {RegML @ NeurIPS},
  year = {2024},
  url = {https://openreview.net/forum?id=p9KIxJmKpy},
}
Figure