TLDR: This paper introduces a two-step method to protect de-identified documents from search-based linkage attacks. It uses an inverted index to find rare N-grams (word sequences) that could uniquely link a document to its source, then iteratively rewrites these N-grams using a Large Language Model (LLM) to preserve semantic integrity while preventing linkages. Experiments on court cases show it effectively reduces linkage risk while maintaining text quality.
In today’s data-driven world, protecting personal information is paramount. Organizations frequently de-identify documents to comply with privacy regulations and share data responsibly. However, a significant challenge remains: the risk of “linkage attacks.” These attacks involve mapping de-identified text back to its original source, even after sensitive information has been masked.
A recent research paper, “Protecting De-identified Documents from Search-based Linkage Attacks,” by Pierre Lison and Mark Anderson from the Norwegian Computing Center, introduces a novel method to counter these search-based linkage attacks while maintaining the meaning of the text. The authors highlight that while traditional de-identification focuses on concealing individual identities, it often overlooks the potential for unique phrases within a document to act as identifiers, allowing an adversary to link the de-identified text back to its original, unedited version.
The Problem: Search-Based Linkage Attacks
Imagine a document where names, dates, and other personal details are removed. An attacker could still extract unique phrases from this de-identified document and search for them in a larger collection of original documents. If a phrase, or a combination of phrases, appears only once or a very limited number of times in the entire collection, it can act as a “fingerprint,” linking the de-identified document directly to its source. This is particularly effective with longer N-grams (sequences of words) which are often unique.
The Proposed Solution: An Iterative LLM-Based Rewriting Method
Lison and Anderson’s method tackles this problem in two main steps. First, they build an “inverted index” of N-grams (sequences of words) found in the entire collection of original documents. This index allows them to quickly identify which N-grams appear in fewer than a specified number of documents (e.g., less than ‘k’ documents). These rare N-grams are the ones that pose a linkage risk.
Second, an instruction-tuned Large Language Model (LLM) is used to iteratively rewrite the identified risky N-grams within the de-identified document. The LLM is given the specific N-grams to rephrase along with their surrounding context, ensuring that the changes are subtle and preserve the overall semantic integrity and fluency of the text. This process is repeated until no N-grams or combinations of N-grams remain that could uniquely link the document back to its source. The paper provides a detailed explanation of this process, including examples of rewritten texts. For more technical details, you can refer to the full paper: Protecting De-identified Documents from Search-based Linkage Attacks.
Experimental Results and Effectiveness
The researchers tested their method on a dataset of 13,759 English-language court cases from the European Court of Human Rights (ECHR). They evaluated the approach based on three criteria: linkage risk, semantic integrity, and fluency. The results were promising: the proposed method drastically reduced linkage risks (around 99.8% of N-gram linkages were eliminated) while largely preserving the semantic content and fluency of the documents. This contrasts sharply with baseline methods, such as LLM rewriting without specific span guidance or differential privacy-based techniques, which either failed to prevent linkages effectively or significantly distorted the text.
Also Read:
- Enhancing Privacy in AI Interactions: A New Framework for Minimizing User Data
- Poison-to-Poison: A New Strategy to Secure Large Language Models from Backdoor Attacks
Limitations and Ethical Considerations
The authors acknowledge that their method primarily focuses on phrase-based search linkage attacks and may not address more sophisticated attacks that rely on semantic similarity. They also note that the approach assumes access to a collection of original documents for building the inverted index. Furthermore, they emphasize that de-identification, even with this enhanced protection, does not provide absolute anonymity and should be seen as a privacy-enhancing technique rather than a guarantee of full anonymization.
Overall, this research offers a practical and effective solution for a critical privacy challenge, enabling safer sharing and publication of de-identified textual data in sensitive domains like legal and medical contexts.
