Obfuscation for Privacy-preserving Syntactic Parsing (2020)

Abstract: The goal of homomorphic encryption is to encrypt data such that another party can operate on it without being explicitly exposed to the content of the original data. We introduce an idea for a privacy-preserving transformation on natural language data, inspired by homomorphic encryption. Our primary tool is obfuscation , relying on the properties of natural language. Specifically, a given English text is obfuscated using a neural model that aims to preserve the syntactic relationships of the original sentence so that the obfuscated sentence can be parsed instead of the original one. The model works at the word level, and learns to obfuscate each word separately by changing it into a new word that has a similar syntactic role. The text obfuscated by our model leads to better performance on three syntactic parsers (two dependency and one constituency parsers) in comparison to an upper-bound random substitution baseline. More specifically, the results demonstrate that as more terms are obfuscated (by their part of speech), the substitution upper bound significantly degrades, while the neural model maintains a relatively high performing parser. All of this is done without much sacrifice of privacy compared to the random substitution upper bound. We also further analyze the results, and discover that the substituted words have similar syntactic properties, but different semantic content, compared to the original words.

## introduction we consider the case in which there is a powerful server with nlp technology deployed on it, and a set of clients who would like to access it to get output resulting from input text taken from problems such as syntactic parsing, semantic parsing and machine translation. in such a case, the server models and an obfuscated version of the sentence (words at bottom), both having identical syntactic structure. the obfuscated sentence hides the identity of the person who performs the action and the action itself. may have been trained on large amounts of data, yielding models that cannot be deployed on the client machines either for efficiency or licensing reasons. we ask the following question: how can we use the nlp server models while minimizing the exposure of the server to the original text? can we exploit the fact we work with natural language data to reduce such exposure? conventional encryption schemes, including public-key cryptography which is the one widely used across the internet, are not sufficient to answer this question. they encrypt the input text before it is transferred to the server side. however, once the server decrypts the text, it has full access to it. this might be unacceptable if the server itself is not necessarily trustworthy. the cryptography community posed a similar question much earlier, in the 1970s @xcite with partial resolutions proposed to solve it in later research @xcite @xcite . these solutions al-low the server to perform computations directly on encrypted data to get the desired output without ever decrypting the data. this cryptographic protocol is known as homomorphic encryption, where a client encrypts a message, then sends it to a server which performs potentially computationally intensive operations and returns a new data, still encrypted, which only the client can decipher. all of this is done without the server itself ever being exposed to the actual content of the encrypted input data. while solutions for generic homomorphic encryption have been discovered, they are either computationally inefficient @xcite or have strong limitations in regards to the depth and complexity of computation they permit @xcite . in this paper, we consider a softer version of homomorphic encryption in the form of obfuscation for natural language. our goal is to identify an efficient function that stochastically transforms a given natural language input (such as a sentence) into another input which can be further fed into an nlp server. the altered input has to preserve intra-text relationships that exist in the original sentence such that the nlp server, depending on the task at hand, can be successfully applied on the transformed data. there should be then a simple transformation that maps the output on the obfuscated data into a valid, accurate output for the original input. in addition, the altered input should hide the private semantic content of the original data. this idea is demonstrated in figure 1 . the task at hand is syntactic parsing. we transform the input sentence john phoned the terrorists to the sentence paul scared the children -both of which yield identical phrase-structure trees. in this case, the named entity john is hidden, and so are his actions. in the rest of the paper, we focus on this problem for dependency and constituency parsing. we consider a neural model of obfuscation that operates at the word level. we assume access to the parser at training time: the model learns how to substitute words in the sentence with other words (in a stochastic manner) while maintaining the highest possible parsing accuracy. this learning task is framed as a latent-variable modeling problem where the obfuscated words are treated as latent. direct optimization of this model turns out to be intractable, so we use continuous relaxations @xcite to avoid explicit marginalization. our experimental results on english demonstrate that the neural model performs better than a strong random-based baseline (an upper bound; in which a word is substituted randomly with another word with the same part-of-speech tag). we vary the subset of words that are hidden and observe that the higher the obfuscation rate of the words, the harder it becomes for the parser to retain its accuracy. degradation is especially pronounced with the random baseline and is less severe with our neural model. the improved results for the neural obfuscator come at a small cost to the accuracy of the attacker aimed at recovering the original obfuscated words. we also observe that the neural obfuscator is effective when different parsers or even different syntactic formalisms are used in training and test time. this relaxes the assumption that the obfuscator needs to have access to the nlp server at training time. our results also suggest that the neural model tends to replace words with ones that have similar syntactic properties. ## homomorphic obfuscation of text our problem formulation is rather simple, demonstrated in generality in figure 2 . let t be some natural language task, such as syntactic parsing, where x is the input space and z is the output space. let f t : @xmath0. note that f is trained as usual on labeled data. given a sentence @xmath1, we aim to learn a function that stochastically transforms x into @xmath2, if not identical, to f t (y), or at the very least, we would like to be able to recover f t (x) from f t (y) using a simple transformation. to ground this in an example, consider the case in which t is the problem of dependency parsing and z is the set of dependency trees. if we transform a sentence x to y in such a way that it preserves the syntactic relationship between the indexed words in the sentences, then we can expect to easily recover the dependency tree for x from a dependency tree for y. note that we would also want to stochastically transform x into a y in such a way that it is hard to recover a certain type of information in x from y (otherwise, we could just set y ← x). furthermore, we are interested in hiding information such as named entities or even nouns and verbs. in our formulation, we also assume that the sentence x comes with a function t(x) that maps each token in the sentence with its corresponding part-of-speech tag (predicted using a pos tagger). ## neural obfuscation model in this section we describe the neural model used to obfuscate the sentence. we note that the model has to be simple and efficient, as it is being run by the obfuscating party. if it is more complicated than parsing the text, for example, then the obfuscating party might as well directly parse the text. foot_0 ## training in our experiments, we focus on obfuscation for the goal of syntactic parsing. we assume the existence of a conditional parsing model p 0 (z | x) where z is a parse tree and x is a sentence. this is the base model which is trained offline, and to which we have read-only access and cannot change its parameters. as we will see in experiments, the obfuscator can be trained using a different parser from the one used at test time (i.e. from the one hosted at the nlp server). let (x (1) , z (1) ), . . . , (x (n) , z (n) ) be a set of training examples which consists of sentences and their corresponding parse trees. considering eq. 1, we would be interested in maximizing the following log-likelihood objective with respect to θ: this objective maximizes the log-likelihood of the parsing model with respect to the obfuscation model. maximizing the objective l 0 is intractable due to summation over all possible obfuscations. we use jensen's inequality foot_1 to lower-bound the cost function l 0 by the following objective: intuitively, the objective function maximizes the accuracy of an existing parser while using as an input the sentences after their transformation. note that the accuracy is measured with respect to the gold-standard dependency parse tree. 3 this is possible because the sentence length of the original sentence and the obfuscated sentence are identical, and the mapping between the words in each version of the sentence is bijective. to encourage stochasticity, we also tried including an entropy term that is maximized with respect to θ in the following form: however, in our final experiments we omitted that term because (a) it did not seem to affect the model stochasticity to a significant degree; (b) the performance has become very sensitive to the entropy weight λ. while we can estimate the objective l using sampling, we cannot differentiate through samples to estimate the gradients with respect to the obfuscator parameters θ. in order to ensure end-toend differentiabilty, we use a continuous relaxation, the gumbel-softmax estimator @xcite , and the reparamterization trick @xcite . more formally, the i-th token is represented by the random variable with categorical probability distribution cat(p i ) that has support v t i . to sample the word we first draw u k ∼ uniform(0, 1) and transform it to the gumbel noise g @xmath3, then we calculate during the training of our neural model, the parser only backpropagates the gradient from the objective of maximizing the parsing accuracy (i.e. minimum cross-entropy loss of the correct head and label for each word), and hence its parameters are always fixed and are not updated during the optimization. ## attacker approaches we test the efficiency of our obfuscation model by developing two independent attacker models. their goal is to recover the original words by inspecting only the obfuscated sentence. the attacker models may have access to all data that the parser and the obfuscator models were trained and developed on. this is perhaps unlike other scenarios in which the training set is assumed to be inaccessible to any attacker. we note that ideally, we would want to show that our obfuscation model retains privacy universally for any attacker. however, this is quite a difficult task, and we follow @xcite in presenting two strong attackers which may represent possible universal attackers. in our attacker experiments, we assume that it is known which words in the sentence are obfuscated. as such, the results we provide for attacking our obfuscation are an upper bound. in practice, an attacker would also have to identify which words were substituted for new words, which may lead to a small decrease in its accuracy. ## experiments in this section, we describe our experiments with our obfuscation model. we first describe the experimental setting and then turn to the results. foot_5 ## related work there has been a significant increase in interest in the topic of privacy in the nlp community in recent years. for example, @xcite focused on obfuscation of gender features from social media text, while @xcite , @xcite and @xcite focused on the removal of private information from neural representations such as named entities and demographic information. unlike the latter work, we are interested in preserving the privacy of the inputs themselves, while requiring no extra work from deployed nlp software which processes these inputs. @xcite , for example, perform multi-document summarization on an approximate version of the original documents. differential privacy @xcite which aims to protect the privacy of information contained in a dataset has also been actively researched. recent research brings differential privacy into natural language processing, for example, the work by @xcite that targets the removal of authorship identity in a text classification dataset. with homomorphic encryption being a longstanding important topic in cryptography, it has also made its way into the field of privacy in machine learning, particularly in terms of designing neural networks which enable homomorphic operations over encrypted data @xcite . for example, @xcite designed a fully homomorphic encrypted convolutional neural network that was able to solve the mnist dataset with practical efficiency and accuracy. the scheme of direct homomorphic encryption @xcite is constrained by the multiplication depth degree in the circuit, which makes deep models intractable. other schemes were developed in recent years @xcite @xcite , but achieving satisfactory performance is still a challenge. to the best of our knowledge, no prior work has demonstrated that homomorphic encryption could be directly applied to the design of recurrent neural networks or discrete tokens as input. ## conclusions we presented a model and an empirical study for obfuscating sentences so that the obfuscated sentences transfer syntactic information from the original sentence. our neural model outperforms in parsing accuracy a strong random baseline when many of the words in the sentence are obfuscated. in addition, the neural model tends to replace words in the original sentence with words which have a closer syntactic function to the original word than a random baseline.