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 ≤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 ( ϵ=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 ≤ 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 ≤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 ( ϵ=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 D when sorted on cosine similarity with rewritten doc d′ , as a function of the proportion of words redacted in d′ . 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′ until a large proportion of words (around 50%) are redacted.
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.
Jianing Wen, Tianshi Li
Khoury College of Computer Sciences Northeastern University Boston, MA
This study examines the transferability of a de-identification model developed for Korean court judgments to a broader range of sensitive documents, focusing on boundary precision, label granularity, and recall. The agglutinative structure of Korean causes Byte Pair Encoding (BPE) tokenizers to frequently merge Personally Identifiable Information (PII) with adjacent particles, which complicates accurate span recovery. Furthermore, current PII taxonomies lack sufficient granularity for legal texts. To address these issues, this study introduces Thunder-DeID+, which integrates a refined three-tier PII taxonomy with a boundary-aware tokenizer. The tokenizer enhances a pretrained BPE vocabulary by incorporating N-gram and boundary-scoring components to better align token and PII span boundaries. The proposed approach is evaluated using a tokenizer-independent word-segment-level protocol. On full-length judgments, the tokenizer consistently improves W. Strict Typed F1-score from 0.76-0.77 to 0.87-0.88 across four model sizes (150M, 395M, 750M, and 1B), mainly by increasing precision rather than model scale. With fine-tuning on 1,000 broader sensitive documents, the judgment-trained model further achieves 0.93 W. Strict Typed F1-score, indicating effective transfer beyond court judgments.
Gyuseong Lee, Gyeongje Cho, Jongmin Kim +8
Dept. of Data Science, Seoul National University · Dept. of Computer Science and Engineering, Seoul National University
Empirical identity leakage from released text is increasingly driven by attackers that combine large language models (LLMs) with auxiliary knowledge to link documents to individuals. Existing audits typically report success rates for specific attack pipelines but lack finite-sample statistical guarantees, while training-time protections such as differential privacy are difficult to translate into release-time decisions for individual natural-language documents. We introduce Conformal Privacy Auditing(CPA), a distribution-free calibration framework that provides a statistical certificate of re-identification risk for each released document against LLM-empowered adversaries. CPA outputs a conformal ambiguity set of candidate identities that is guaranteed to contain the true identity with user-chosen confidence under exchangeability, together with an interpretable leakage proxy derived from set size. CPA supports both logit-access and sampling-only attackers, enabling audits of open-source models and proprietary API models in a unified framework. Across multiple release benchmarks and attacker configurations, CPA achieves calibrated coverage and reveals sharp shifts in certified identifiability as auxiliary knowledge, LLM augmentation, and release mechanisms vary, providing a statistically grounded basis for reporting and comparing release-time linkage risk across attacker configurations, datasets, and release mechanisms alike.
Shuo Huang, Gholamreza Haffari, Xingliang Yuan +2
Monash University · The University of Melbourne · Mohamed bin Zayed University of Artificial Intelligence