Protecting De-identified Documents from Search-based Linkage Attacks

The gist The proposed method counters search-based linkage attacks by constructing an inverted index to identify N-grams occurring less than k times and then iteratively querying an LLM to reformulate those spans until linkages are averted

Threat Model

The threat model assumes an adversary with access to the original collection of documents seeks a linkage between a de-identified text d' and its original text d in three consecutive steps The adversary first extracts substrings Sd' from d', then searches for their occurrence in D to find the subset D(Sd') of documents containing those strings, and finally considers the linkage successful if D(Sd') < k, where k is a minimum threshold Such search-based linkages can be carried out by adversaries with minimal technical skills

Extraction of N-grams to Rephrase

The method relies on an inverted index to efficiently determine which N-grams occur in less than k documents To find a list of single N-grams to rephrase, the procedure involves:

1. Extracting a set Sd' of N-grams occurring in d', limiting the maximum length to 8 words and excluding those crossing punctuation markers or [REDACTED] PIIs

2. Sorting the N-grams in Sd' by their length and filtering out overlapping N-grams, resulting in a set Smin d' representing the minimal set of N-grams that need to be considered as potential linkage points

3. Checking the number of documents associated with each N-gram in the inverted index I; if the length of the posting list I(s) is < k, s is added to the Ngrams to rephrase

b. For each combination c ∈ C m Smin d', extracting the posting lists and intersecting them; if the result has a length < k, the shortest N-gram in c is added to the Ngrams to rephrase

In-context Rewriting

Once the set of N-grams S∗d' to rephrase is extracted, an instruction-tuned LLM is queried to generate a reformulated text d't+1 ← LLM(d't, S∗d') The LLM is provided with the local context surrounding the N-grams to rephrase and few-shot examples of rewritten sentences The rewriting procedure is repeated for several passes until the set of N-grams S∗d' becomes empty

Experimental Evaluation and Results

The approach is evaluated on two datasets: ECHR court cases and Wikipedia biographies The evaluation criteria are linkage risk, semantic integrity, and fluency For the ECHR dataset with k=2 (risk of singling out), the proposed method eliminates around 99.8% of N-gram linkages However, a small number persists when the LLM is repeatedly unable to find suitable rephrasing The results show that the approach can drastically reduce linkage risks while remaining faithful to the original content of the document

Limitations

The proposed text rewriting approach is focused on preventing search-based linkages rather than linkages based at the level of latent representations such as document embeddings This focus means the method does not prevent the possibility of semantic linkages Furthermore, semantics-based linkages are conditioned on adversaries with access to the original documents in full text in order to compute embedding vectors The prevention of semantics-based linkages requires drastic alterations to the document, with at least half the words needing to be redacted

Conclusion

The proposed method provides the most effective balance between precluding search-based linkages and preserving the semantic content of the document The rewriting operations also acts as a broader privacy-enhancing measure by effectively limiting the occurrence of rare or atypical terms in de-identified documents However, more sophisticated attacks remain possible, notably based on latent semantic representations derived from the texts While the approach limited to the rephrasing of single linkable N-grams (arity=1) produces a rewritten text that is semantically closer to its input, it fails against linkages due to N-gram combinations The method does not provide a robust protection against such semantics-based linkages

Ethical Considerations

There is an inherent risk that such approach might give a false sense of security of the level of privacy it provides De-identification is a privacy-enhancing technique but does not provide a strong privacy guarantee or equate full anonymisation While de-identification can help conceal a large number of PIIs expressed in a document, they remain imperfect and prone to various errors and omissions De-identification is a privacy-enhancing technique but does not provide a strong privacy guarantee or equate full anonymisation

Appendix Details

The LLM rewriting prompt instructs the model to edit the text such that EVERY span in the list is replaced, ensuring the original span no longer appears as such in the text The prompt specifies that if a span is a named entity or another highly specific term impossible to rephrase, it should be replaced by [REDACTED] This baseline approach maintains semantic content but can lead to suboptimal or wrong replacements, such as battery and robbery being replaced by bombardment and looting The DP-based rewriting model performs poorly when using a high epsilon value (ϵ = 100), producing disfluent texts with weak semantic ties to the source This approach requires at least half the words needing to be redacted to prevent semantics-based linkages The method took an average of 15.5 (±12.8) secs per document to avert linkages with single N-grams The method took 52.6 (±37.

1. Improved search-based linkage prevention via an inverted index and LLM rewriting: The system can construct an inverted index of N-grams to determine which N-grams occur in less than k documents, and then use an instruction-tuned LLM to iteratively reformulate those spans until linkage is no longer possible. This allows the system to prevent search based linkages while preserving the semantic integrity of the text.

2. Improved handling of N-gram combinations: The system can extend its prevention capability by generating and querying the LLM with combinations of N-grams up to an arity of 3, effectively addressing indirect linkage risks. This ensures that indirect linkages can also be removed (arity ≤ 3), although at the cost of more extensive edits.

3. Improved robustness against semantic linkage attacks: The system can be designed to handle latent semantic representations by monitoring cosine similarities between the de-identified text and the original collection, although it must acknowledge that the proposed method does not [provide] a robust protection against such semantics-based linkages.

While de-identification models can help conceal the identity of the individuals mentioned in a document, they fail to address linkage risks, defined as the potential to map the de-identified text back to its source. One straightforward way to perform such linkages is to extract phrases from the de-identified document and check their presence in the original dataset. This paper presents a method to counter search-based linkage attacks while preserving the semantic integrity of the text. The method proceeds in two steps. We first construct an inverted index of the N-grams occurring in the text collection, making it possible to efficiently determine which N-grams appear in fewer than k documents, either alone or in combination with other N-grams. An LLM-based rewriter is then iteratively queried to reformulate those spans until linkage is no longer possible. Experimental results on two datasets (court cases and Wikipedia biographies) show that the rewriting method can effectively prevent search-based linkages while remaining faithful to the original content. However, we also highlight that linkages remain feasible with the help of more advanced, semantics-oriented approaches.