When differential privacy meets NLP : The devil is in the detail (2021)

Abstract: Differential privacy provides a formal approach to privacy of individuals. Applications of differential privacy in various scenarios, such as protecting users’ original utterances, must satisfy certain mathematical properties. Our contribution is a formal analysis of ADePT, a differentially private auto-encoder for text rewriting (Krishna et al, 2021). ADePT achieves promising results on downstream tasks while providing tight privacy guarantees. Our proof reveals that ADePT is not differentially private, thus rendering the experimental results unsubstantiated. We also quantify the impact of the error in its private mechanism, showing that the true sensitivity is higher by at least factor 6 in an optimistic case of a very small encoder’s dimension and that the amount of utterances that are not privatized could easily reach 100% of the entire dataset. Our intention is neither to criticize the authors, nor the peer-reviewing process, but rather point out that if differential privacy applications in NLP rely on formal guarantees, these should be outlined in full and put under detailed scrutiny.

## introduction the need for nlp systems to protect individuals' privacy has led to the adoption of differential privacy (dp). dp methods formally guarantee that the output of the algorithm will be 'roughly the same' regardless of whether or not any single individual is present in the central dataset; this is achieved by employing randomized algorithms @xcite . local dp, a variant of dp, mitigates the need for a central dataset and applies randomization on each individual's datapoint. local dp thus guarantees that its output for an individual a will be 'almost indistinguishable' from the output of any other individuals b or c. 1 this level of privacy protection makes local dp an ideal framework for nlp applications that operate on sensitive user input which should not be collected and processed globally by an untrusted party, e.g., users' verbatim utterances. when the utterances are 'privatized' by local dp, any future post-processing or adversarial attack cannot reveal more than allowed by the particular local dp algorithm's properties (namely the ε parameter; see later sec. 2). adept, a local dp algorithm recently published at eacl by @xcite from amazon alexa, proposed a differentially private autoencoder for text rewriting. in summary, adept takes an input textual utterance and re-writes it in a way such that the output satisfies local dp guarantees. unfortunately, a thorough formal analysis reveals that adept is in fact not differentially private and the privatized data do not protect privacy of individuals as formally promised. in this short paper, we shed light on adept's main argument, the privacy mechanism. we briefly introduce key concepts from differential privacy (dp) and present a detailed proof of the laplace mechanism (sec. 2). section 3 introduces @xcite architecture and its main privacy argument. we formally prove that the proposed adept's mechanism is in fact not differentially private (sec. 4) and determine the actual sensitivity of its private mechanism (sec. 5). we sketch to which extent adept breaches privacy as opposed to the formal dp guarantees (sec. 6) and discuss a potential adversary attack (appendix c). ## theoretical background from a high-level perspective, dp works with the notion of individuals whose information is contained in a database (dataset). each individual's datapoint (or record), which could be a single bit, a number, a vector, a structured record, a text document, or any arbitrary object, is considered private and cannot be revealed. moreover, even whether or not any particular individual a is in the database is considered private. definition 2.1. let x be a 'universe' of all records and x, @xmath0. we say that x and y are neighboring datasets if they differ in one record. for example, let dataset x consist of |x| documents where each document is associated with an individual whose privacy we want to preserve. let y differ from x by one document, so either |y| = |x| ± 1, or |y| = |x| with i-th document replaced. then by definition 2.1, x and y are neighboring datasets. ## adept by krishna et al. (2021) let u be an input text (a sequence of words or a vector, for example; this is not key to the main argument). enc is an encoder function from input u to a latent representation vector @xmath1. dec is a decoder from the latent representation back to the original input space (again, a sequence of words or a vector). what we have so far is a standard auto-encoder, such that @xmath2. proof. @xcite refers to the proof of theorem 3.6 by @xcite , which is the proof of the laplace mechanism. first, v i in eq. 10 is ambiguous as it 'semantically' relates to v which is the decoded vector that comes first after drawing a random value; moreover η and v have different dimensions. given that the authors employ laplacian noise and base their proofs on theorem 3.6 from @xcite , we believe that eq. 10 is the standard laplace mechanism fix the clipping constant @xmath3, set dimensions to @xmath4. let r @xmath5, 2 3 c) be the input y of the clipping function f from eq. 13. similarly, let r @xmath6, -2 3 c) be input x, for which we get analogically f (x) = (-2 3 c, -2 3 c). then in general, it is the inequality x 1 ≥ x 2 that makes adept fail the dp proof. ## actual sensitivity of adept theorem 5.1. let f : r @xmath7. 13. the sensitivity ∆f of this function is 2c √ n. proof. see appendix b. corollary 5.1. since 2c √ @xmath8, adept could be differentially private only if the encoder's latent representation @xmath9. since @xcite do not specify the dimensionality of their encoder's output, we can only assume some typical values in a range from 32 to 1024, so that the true sensitivity of adept is ≈ 6 to 32 times higher than reported. ## magnitude of non-protected data how many data points actually violate the privacy guarantees? without having access to the trained model and its hyper-parameters (c, in particular), it is hard to reason about properties of the latent space, where privatization occurs. we thus simulated the encoder's 'unclipped' vector outputs r by sampling 10k vectors from two distributions: 1) uniform within (-c, +c) for each dimension, and 2) zero-centered normal with σ 2 = 0.1 • c. especially the latter one is rather optimistic as it samples most vectors close to zero. in reality these latent space vectors are unbounded. each pair of such vectors in the latent space after clipping but before applying dp (eq. 13) is 'neighboring datasets' so their ℓ 1 distance must be bound by sensitivity (2c as claimed in theorem 3.2) in order to satisfy dp with the laplace mechanism. we ran the simulation for an increasing dimensionality of the encoder's output and measured how many pairs violate the sensitivity bound. 5 fig. 1 shows the 'curse of dimensionality' for norms. even for a considerably small encoder's vector size of 32 and unbounded encoder's latent space, almost none of the data points would be protected by adept's laplace mechanism. ## discussion local dp differs from centralized dp in such a way that there is no central database and once the privatized data item 'leaves' an individual, it stays so forever. this makes typical membership inference attacks unsuitable, as no matter what happens to the rest of the world, the probability of inferring the individual's true value after observing their privatized data item is bounded by exp(ε). for example, the atis dataset used in adept contains 5,473 utterances of lengths 1 to 46 tokens, with a quite limited vocabulary of 941 words. in theory, the search space of all possible utterances would be of size 941 46 ≈ 6 × 10 136 , and under ε-dp all of them are multiplicatively indistinguishable -for example, after observing "on april first i need a ticket from tacoma to san jose departing before 7 am" from adept's autoencoder privatized output, the true input might well have been "on april first i need a flight going from phoenix to san diego" or "monday morning i would like to fly from columbus to indianapolis" and our posterior certainty of any of those is limited by the privacy bound. however, since outputs of adept are leaking privacy, attacks are possible. we sketch a potential scenario in appendix c. there are two possible remedies for adept. either the latent vector clipping in eq. 9 could use ℓ 1norm, or the laplacian noise in eq. 10 could use the correct sensitivity as determined in theorem 5.1. in either case, the utility in the downstream tasks as presented by @xcite are expected to be worse due to a much larger amount of required noise. ## conclusion this paper revealed a potential trap for nlp researchers when adopting a local dp approach. we believe it contributes to a better understanding of the exact modeling choices involved in determining the sensitivity of local dp algorithms. we hope that dp will become a widely accessible and wellunderstood framework within the nlp community. satyapriya krishna, rahul gupta, and christophe dupuy. 2021. adept: auto-encoder based differentially private text transformation. in proceedings of the 16th conference of the european chapter of the association for computational linguistics: main volume, pages 2435-2439, online. association for computational linguistics. ilya mironov. 2017. rényi differential privacy. in 2017 ieee 30th computer security foundations symposium (csf), pages 263-275, santa barbara, ca, usa. ieee. teng wang, xuefeng zhang, jingyu feng, and xinyu yang. 2020. a comprehensive survey on local differential privacy toward data statistics and analysis. sensors, 20(24):7030. stanley l. warner. 1965. randomized response: a survey technique for eliminating evasive answer bias. journal of the american statistical association, 60(309):63-69.