The Limits of Word Level Differential Privacy (2022)

Abstract: As the issues of privacy and trust are receiving increasing attention within the research community, various attempts have been made to anonymize textual data. A significant subset of these approaches incorporate differentially private mechanims to perturb word embeddings, thus replacing individual words in a sentence. While these methods represent very important contributions, have various advantages over other techniques and do show anonymization capabilities,they have several shortcomings. In this paper, we investigate these weaknesses and demonstrate significant mathematical constraints diminishing the theoretical privacy guaranteeas well as major practical shortcomings with regard to the protection against deanonymization attacks, the preservation of content of the original sentences as well as the quality of the language output. Finally, we propose a new method for text anonymization based on transformer based language models fine-tuned for paraphrasing that circumvents most of the identified weaknesses and also offers a formal privacy guarantee. We evaluate the performance of our method via thourough experimentation and demonstrate superior performance over the discussed mechanisms.

## introduction computational authorship attribution approaches ranging from rule-based methods measuring character-level n-gram frequencies @xcite to models incorporating deep learning @xcite make it possible to identify the authors of a given text. while these technologies enable valuable applications such as supporting historians in their research, they can potentially be exploited by attackers to identify the originators of sensitive data and thus diminish the privacy of individuals. to protect the anonymity of users whose data is being shared online and used by companies and researchers, methods that anonymize the writer of given texts are necessary and of interest within the research community and a variety of industries, specifically those handling personal information such as healthcare or financial services. previous work in the field of authorship obfuscation mainly focuses on two different tasks, namely learning anonymous textual vector representations for downstream tasks @xcite @xcite @xcite and the development of mechanisms that transform the input sentence to remove properties revealing the author and thus output human-readable text. works within the second category @xcite @xcite typically follow a common word level framework which is characterized by the differentially private individual perturbation of word embeddings and the subsequent sampling of new words that are close to the perturbed vectors in the embedding space. also, the majority of recent work proposing new methods for authorship obfuscation deals with the optimization and calibration of noise sampling mechanisms @xcite or the definition of new distributions to sample noise from @xcite as opposed to the development of entirely new methods. in this paper, we thoroughly investigate the capabilities of word level anonymization from the theoretical perspective of differential privacy (dp) (section 3.1), in terms of the language quality of its output (section 3.2) as well as from a utilitarian perspective considering the ability to protect the privacy of people whose data is being used. specifically, we extend the experimentation in papers proposing the discussed methods by testing their capability to mitigate deanonymization attacks using state-of-the-art methods on the widely used imdb movie review and yelp business review datasets (section 5). we find that the technical constraints applied to fulfill dp in the local model cause strong limitations, and, more importantly, observe that, despite the formal guarantees, such methods offer little protection against advanced deanonymization attacks. for this reason, we advocate for approaches granting more flexibility to the text generation process and, motivated by experiments showing that human rewritings of texts gathered through crowdsourcing successfully anonymize the original authors @xcite , propose an anonymization approach based on paraphrasing (section 4) that maintains the advantages and the theoretical privacy guarantee of the discussed methods, evades most of the identified drawbacks and outperforms word level mechanisms in our experiments. ## background the majority of proposed text anonymization methods rely on a common framework that applies dp on a per-word level by perturbing individual word embeddings @xcite @xcite . in this section, we introduce the concept of dp and give an overview of the commonly used word level framework. ## anonymization through paraphrasing while existing works on text anonymization that focus on word level perturbations represent very important contributions, they have some significant weaknesses as described in section 3. in the following, we attempt to address the identified problems by proposing fine-tuning of large language models for paraphrasing as an alternative text anonymization method. ## evaluation we argue that despite formal guarantees, the privacy preservation capabilities of mechanisms that are deployed in real world applications should also be tested from a practical standpoint. previous works measure anonymization capabilities using a variety of evaluation metrics: feyisetan et al. (2020) use the privacy auditor proposed by @xcite , whereas @xcite measure the ability of an adversary to reconstruct the original sentence, and @xcite count the amount of changed words. unfortunately, these methods are rarely tested under the scenario of a strong attacker aiming to identify the authors of the obfuscated texts. while @xcite measure the identification performance of an authorship attribution model, their adversary @xcite only relies on counting character 4-grams and does not adequately reflect the capabilities of a strong attacker who can train more powerful classifiers. besides, attacks are almost always evaluated only in a static (non-adaptive) setting, meaning that the attack model is only trained on the original data and cannot adapt to the perturbed data. since any serious method should avoid "security (or privacy) by obscurity", we must assume that the obfuscation mechanism is known to the attacker who can easily create perturbed data themselves. in the following evaluation, we consider two exemplary methods following the word level framework, namely perturbing euclidean glove embeddings @xcite through laplace noise as proposed by @xcite , the perturbation of hierarchical poincaré embeddings @xcite through hyperbolic noise as proposed by @xcite , as well as our paraphrasing approach proposed in section 4. to address the discussed issues in previous evalua-tion methodologies, we employ recent state-of-theart methods to compare the privacy-utility tradeoffs and analyze the performance of the approaches not only in a static, but also in an adaptive setting. ## related work other dp mechanisms for text earlier mechanisms for differentially private text obfuscation settled for simpler output representations: weggenmann and kerschbaum (2018); @xcite employ bag-of-words (bow) models and produce term-frequency vectors as output. similarly, obfuscated dense vector representations are obtained in @xcite by perturbing the output of an encoder network. while not humanreadable, these vector representations can be shared for automated processing, such as topic or sentiment inference and machine learning. to generate human-readable text, @xcite employ an encoder-decoder model similar to ours, but without paraphrasing, and sample output words using (a two-set variant of) the exponential mechanism @xcite . @xcite propose a differentially private variation of the variational autoencoder and use it as a sequenceto-sequence architecture for text anonymization. authorship obfuscation without dp approaches not following dp range from rule-based algorithms relying on human-engineered text perturbations such as synonym replacements or word removals @xcite to methods incorporating deep learning. models of the latter typically incorporate discriminator networks to penalize generating author-revealing information @xcite . similar to dp mechanisms, previous work is concerned with learning private text vector representations @xcite . differentially private optimization differentially private optimization algorithms such as dp-sgd and related methods @xcite @xcite have emerged as effective methods for protecting the training data of a model. recent work has shown that both generative and discriminative language models can effectively be trained with these optimization approaches @xcite and there-fore represent an important contribution for protecting against data leakage of language models @xcite . these methods can be seen as complementary to the approaches discussed in this paper which protect data during inference. ## conclusion we discussed and demonstrated the weaknesses of word level dp mechanisms and proposed a paraphrasing model circumventing most of these. we find that our approach outperforms word level mechanisms in terms of protection against adaptive adversaries, while the latter should be favored against weaker adversaries. future work could address integrating auxiliary adversarial losses to paraphrasing systems or enabling paraphrases that better preserve the core information of the source text.