Protecting De-identified Documents from Search-based Linkage Attacks

Pierre Lison; Mark Anderson

cs.CLOct 7, 2025

Protecting De-identified Documents from Search-based Linkage Attacks

Authors: Pierre Lison, Mark Anderson

Organizations: Norwegian Computing Center Oslo, Norway

Abstract

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.

Figures & tables

Figure 1: To prevent search-based linkages between a de-identified document and its original source, we first identify all N-grams occurring less than

k

times in the collection, and then use an instruction-tuned LLM to reformulate each of those N-grams (in their local context) until the linkages are averted.

Figure 2: Distinct posting lists in the index built from the ECHR court cases, distributed according to the posting list length (=nb of documents associated with a particular N-gram) and the size of the N-gram, from 1 to 8 words. The Y-axis is displayed in log scale. Longer N-grams dominate the posting lists, as expected since the number of distinct N - grams grows combinatorially with N. The posting lists are in this case quite short, particularly for longer N-grams: 60% of posting lists for unigrams have one single document, while this proportion reaches 93% for

N=8

	Proportion of		Semantic		Perplexity
	linkable N-grams		Similarity
Approaches:	arity $=1$	arity $\leq 3$	distilroberta	GTE	( Gemma3 )
Baseline LLM-based rewriting	0.597	0.695	0.974	0.979	12.6
(without specified spans to rephrase)
Handcrafted paraphrasing	0.348	0.615	0.992	0.979	20.4
DP-based rewriting ( $\epsilon=10$ )	0.001	0.001	0.358	0.617	2736

Table 1: Evaluation results on the ECHR court cases according to three criteria: linkage risk (either for single N-grams or N-grams combinations of arity

\leq

3), semantic integrity and fluency . The first two columns indicate the proportion of N-grams that remain linkable to the original document

d

after rewriting for a value

k=2

, which corresponds to the risk of singling out. Semantic integrity is measured through cosine similarities between the document embeddings of the text before and after rewriting. The embeddings are respectively obtained with paraphrase-distilroberta-base-v2 and GTE-ModernBERT . Finally, perplexity is measured with gemma 3-1B-pt . All LLM-based rewriting approaches are based on Qwen3-4B (see prompts in Appendix). Results obtained with a single run.

	Proportion of		Semantic		Perplexity
	linkable N-grams		Similarity
Approaches:	arity $=1$	arity $\leq 3$	distilroberta	GTE	( Gemma3 )
Baseline LLM-based rewriting	0.485	0.553	0.989	0.994	10.7
(without specified spans to rephrase)
Handcrafted paraphrasing	0.256	0.355	0.952	0.978	19.17
DP-based rewriting ( $\epsilon=10$ )	0.008	0.009	0.268	0.608	2122

Table 2: Evaluation results on the dataset of Wikipedia biographies according to same metrics as Table 1 .

Figure 3: Frequency of original text

d

appearing in the top-

k

list among all documents in collection

\mathcal{D}

when sorted on cosine similarity with rewritten doc

d^{\prime}

, as a function of the proportion of words redacted in

d^{\prime}

. The results are averaged on the dataset of court cases. The shaded areas represent the Wilson CI. We can observe that the original text

d

remains semantically very close to the rewritten document

d^{\prime}

until a large proportion of words (around 50%) are redacted.

Privacy-Preserving Language Models

Privacy-preserving language models protect sensitive data during training, inference, personalization, and information sharing.

See all 178 papers

AgentDoxx: Agentic Re-identification of Anonymized Text with Web Search
Oct 4, 2026Jianing Wen, Tianshi LiPrivacy Leakage in Language Models AI Agent Security Benchmarks
Khoury College of Computer Sciences Northeastern University Boston, MA
Thunder-DeID+: Boundary-Aware Korean De-identification from Court Judgments to Broader Sensitive Documents
Oct 15, 2026Gyuseong Lee, Gyeongje Cho, Jongmin Kim +8Legal NLP Subword Tokenization
Dept. of Data Science, Seoul National University · Dept. of Computer Science and Engineering, Seoul National University
Conformal Privacy Auditing: Calibrated Re-identification Attacks with Statistical Guarantees
Sep 18, 2026Shuo Huang, Gholamreza Haffari, Xingliang Yuan +2Privacy Auditing Privacy Leakage in Language Models
Monash University · The University of Melbourne · Mohamed bin Zayed University of Artificial Intelligence

Oct 4, 2026J/K move · Enter open · S save

AgentDoxx: Agentic Re-identification of Anonymized Text with Web Search

Jianing Wen, Tianshi Li

Khoury College of Computer Sciences Northeastern University Boston, MA

Privacy Leakage in Language Models AI Agent Security Benchmarks

Open paper AskPDF arXiv

As Large Language Models (LLMs) gain tool use capabilities such as web search, they can retrieve and cross-reference public information, creating privacy risks beyond memorization. One manifestation is re-identification: linking an anonymized interview transcript to a named individual. Yet without ground-truth identities, the coverage of such attacks and the protection offered by a defense cannot be reliably measured. We introduce AgentDOXX, an evaluation suite of 822 synthetic interview transcripts grounded in public information about real individuals with known identities. We evaluate fifteen configurations of open-weight and proprietary models, isolating the effect of web search, and analyze their search trajectories to distinguish retrieval-driven from parametric identifications. Ground-truth identities reveal that re-identification risk is distributed across an agent's execution: retrieval and parametric recall both contribute, with open-weight models identifying 15-28% of transcripts without search; identification succeeds in over 88% of cases once the target appears in a retrieved result; entity masking leaves at least one attacker successful on 85.3% of a stratified sample; and privacy instructions suppress naming but not retrieval, with configurations scoring 0% accuracy yet retrieving the subject in up to 62% of transcripts. We further show that observed attack trajectories can provide supervision for localizing identifying spans, offering a path toward attack-informed anonymization.

Abstract

Privacy-Preserving Language Models

Explore similar work

AgentDoxx: Agentic Re-identification of Anonymized Text with Web Search

Thunder-DeID+: Boundary-Aware Korean De-identification from Court Judgments to Broader Sensitive Documents

Conformal Privacy Auditing: Calibrated Re-identification Attacks with Statistical Guarantees