{'fraction_non_alphanumeric': 0.04480675393075672, 'fraction_numerical': 0.011695453489272712, 'mean_word_length': 3.892478211443729, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Boundary Between Privacy and Utility in Data Anonymization

We consider the privacy problem in data publishing: given a relation I containing sensitive information 'anonymize' it to obtain a view V such that, on one hand attackers cannot learn any sensitive information from V, and on the other hand legitimate users can use V to compute useful statistics on I. These are conflicting goals. We use a definition of privacy that is derived from existing ones in the literature, which relates the a priori probability of a given tuple t, Pr(t), with the a posteriori probability, Pr(t | V), and propose a novel and quite practical definition for utility. Our main result is the following. Denoting n the size of I and m the size of the domain from which I was drawn (i.e. n<m) then: when the a priori probability is Pr(t) = Omega(n/sqrt(m)) for some t, there exists no useful anonymization algorithm, while when Pr(t) = O(n/m) for all tuples t, then we give a concrete anonymization algorithm that is both private and useful. Our algorithm is quite different from the k-anonymization algorithm studied intensively in the literature, and is based on random deletions and insertions to I.


Introduction
The need to preserve private information while publishing data for statistical processing is a widespread problem. By studying medical data, consumer data, or insurance data, analysts can often derive very valuable statistical facts, sometimes benefiting the society at large, but the concerns about individual privacy prevents the dissemination of such databases. Today's state of the art in data anonymization is the k-anonymity method [10]: the privacy (or lack thereof) of k-anonymity has been studied and improved recently [9,8,7,6,11], but this method fails to offer any formal guarantees for computing statistical properties, which limits the use of k-anonymized data.
Clearly, any anonymization method needs to trade off between privacy and utility: removing all items from the database achieves perfect privacy, but total uselessness, while publishing the entire data unaltered is at the other extreme. In this paper we study the tradeoff between the privacy and the utility of any anonymization method, as a function of the attacker's background knowledge. When the attacker has too much knowledge, we show that no anonymization method can achieve both. But for practical purposes one can often assume that there is a bound on the amount of knowledge the attacker has, and then we show that the tradeoff can be achieved by a new, and very simple anonymization algorithm.

Background
To place our work in context we describe here the problem and some of the issues raised by the k-anonymization.
Consider a database I of English test scores as shown in Table 1. It would be useful to make some form of this data publicly available, for example in order to allow researchers in public education to study correlations between various ages, nationalities, and test scores, without releasing the test scores of individual people. While names have already been removed from the table, we don't want to publish this data unchanged because an attacker may use some of the age-nationality values to uniquely identify an individual (this was first shown by Sweeney [10]): for example, he may know that Joe is 21 years old and of Indian Nationality and, since only one entry in the database matches this age and nationality, the attacker can learn Joe's test score. The problem is to anonymize the data: more precisely to compute a view V that perturbs the data to make individual identifications impossible. However, we need to do this such as to allow legitimate users to compute answers to "statistical queries". Examples of such queries are: How many people in the age group 20-30 have score greater Age Nationality Score  25  British  99  27  British  97  21  Indian  82  32  Indian  90  33  American  94  36 American 94 than 90 ? or How many people in a particular country have score less than 90 ? Users evaluate multiple queries like these then combine their answers to derive important correlation between age, score, and nationality: they don't need to see individual scores. The data anonymization problem has been studied intensively in recent years. Virtually all techniques described in the literature are variations of the k-anonymity method [10,9,8,7,6,11], which we illustrate next. Note that the anonymization problem is different from the query perturbation problem, studied elsewhere [4,3,2]. Figure 2 shows the k-anonymity method and several variations described in the literature, for the instance I in Table 1. k-anonymization is based on generalizing attribute values, e.g. replacing age 27 with an interval 21 − 30, or even with a wildcard * . Table 2(a) shows the original idea in k-anonymization [9]: generalize the attribute values such that every tuple occurs in the data at least k times, in our case k = 2. Our hypothetical attacker is no longer able to learn Joe's score, since now there are 2 tuples that match Joe's age and nationality (in general: k tuples). But by generalizing the score values one arguably reduces the utility of the data, and for that reason researchers have proposed to differentiate between the sensitive attribute (the score in our example) and the quasi-identifiers (age, nationality in our case), and to anonymize only the latter: this is illustrated in our example in Table 2(b), which is still a 2-anonymous table but on the quasi-identifiers only, while the scores are unchanged. One problem with this approach (which is not addressed in the literature) is that it is not always obvious how to classify attributes into quasi-identifiers and sensitive attributes, and this is presumably left to the application: for that reason, in our paper we do not require such a classification of attributes. Continuing our illustration, observe that by keeping the sensitive attribute unaltered one runs the risk of major privacy breaches (as first noted in [8]). This is illustrated in Table 2(b) in the third group: all scores in this group are 94, hence an attacker who knows that (say) Jane is an American can learn that her test score is 94. The solution proposed in [8] is to further require the anonymized data to satisfy a condition called l-diversity, namely that in each group there be at least l distinct values of the sensitive attribute. This is shown in Table 2(c), which is 3-anonymous and 2-diverse: within each group, the attacker finds at least 2 (in general l) scores that could potentially belong to a particular individual, hence, arguably he cannot guess a private piece of data with probability more than 1/l. Thus, most of the prior research on data anonymization has focused on understanding and improving the data's privacy. The formal definitions of privacy in the literature rely on comparing the a priori and the a posteriori probability of a sensitive tuple t being in the database [8]. The a priori probability Pr[t] is the attacker's belief before seeing the published data: for example, the attacker may believe that Joe, who 21 years old and Indian, had a test score of 82 with probability 5%. The a posteriori probability is after seeing the published view, Pr[t | V ]: for example, after seeing the view in Table 2 (b) the a posteriori probability of Joe having a test score of 82 is 50%. When these two probabilities are close, or when the latter is low, then privacy is said to be preserved. In this paper we use a formal definition of privacy that follows the same principles.
Much less understood is the data's utility. Consider the following query: compute the number of individuals between 26-32 years that received a score > 90: it is unclear how to estimate the query's answer from any of these three tables, and what guarantees this estimate offers. A definition of utility based on entropy is given in [6], but this compares the a priori and the a posteriori distribution, and does not give any guarantees on estimating the answer to a counting query.

Our Contributions
In this paper we study the privacy/utility tradeoff. For that we give a definition of utility based on estimating counting queries, i.e. queries of the form count the number of records satisfying a certain predicate. Our definition requires that all counting queries whose answer is "large" be accurately estimated from the anonymized data, with a guarantee on the accuracy that does not depend on any additional assumptions on the original data. For example, if the query count the number of persons with age between 26 and 32 who received a score over 90 has a large answer (say, 1/50th of the size of the instance), then we require it to be possible to estimate it with high accuracy from the anonymized data. None of the variations of k-anonymity described earlier allows us to compute a good estimate to this query: for example in Table 2 (c) all six entries could have an age between 26 and 32, and the only way to estimate the query's answer is to make further assumptions about the distribution of the data: e.g. that ages are uniformly distributed in the interval 21-40, and that the distribution on ages is independent on the test score. But if we ask users to know such properties about the data then we are defeating their very purpose in analyzing the data: the users would like to discover whether age and the test score are independent or not, and not to be required to know this in order to discover other facts.
Note that our definition of utility applies only to queries with large answers. This is crucial: queries with small answers could leak privacy if we allow them to be estimated accurately. For example the query count the number of Indian persons, of age 21, who received a score of 82 has answer 1 on the original data, and if we allowed it to be estimated with high accuracy then privacy would be breached.
Our main result is an almost complete separation of the case when a private/useful anonymization algorithm is possible from that when it is impossible, based on the attacker's knowledge. If the attacker's prior tuple probability is as high as Ω(n/ √ m), where n is the size of the database and m the size of the domain D, then an utility preserving anonymization algorithm is impossible. This impossibility result holds even when the prior distribution is tuple independent. If the attackers attacker's prior is O(n/m), then privacy/utility is possible. We prove that by giving a new, and very simple anonymization algorithm: randomly remove each tuple in I with probability α, and randomly insert each tuple in the domain D with probability β. A particular run of this algorithm is shown in Table 2 (d): Two tuples have been removed from the original data, and eight new tuples have been inserted. (For presentation purposes we indicate which four tuples come from I and which were inserted randomly: in practice this separation is hidden.) Both privacy and utility can be achieved by tuning α and β, as long as the attacker's prior is O(n/m). Importantly, the accuracy of any counting query is guaranteed as a probability on the random choices made by the algorithm, without any assumptions on the original data. The proof of our algorithm's privacy assumes that the prior distribution is tuple independent, or that it satisfies some very limited form of correlations. This is clearly a weakness, but in some sense it is unavoidable: we show that if the attacker is allowed to know arbitrary tuple correlations, then no utility-preserving algorithm exists even when the prior is Ω(n/m).
Our impossibility result extends a similar result by Dwork and Nissim [4], which was derived for a different privacy setting. We give the formal definition of the privacy setting in Sec. 3.1. Using this notion of privacy, they showed that no such algorithm can be useful. We improve here, the impossibility result (by tightening the bounds, and relaxing the definition of counting queries), and show how to extend it to the more traditional notion of privacy.
Random deletions and insertions in the database are well known privacy preserving techniques, which have been used in a variety of settings, e.g. in private data mining [5]. Perhaps surprisingly, our algorithm is the first application of these techniques to data publishing.
Overview Privacy and utility are defined in Sec. 2; the negative (impossibility) result is in Sec. 3, and the positive result (the new algorithm) is in Sec. 4. Extensions to tuple correlations are discussed in Sec. 5.

Notations and Definitions
Let I = {t 1 , t 2 , .., t n } be a database instance where each tuple t i is drawn from a domain D of size m (i.e. I ⊆ D). We need to design a privacy preserving algorithm A which takes as input an instance I and publishes a view V , of the same schema as I (i.e. V ⊆ D). The view V becomes public knowledge while the original instance I remains hidden.
Modeling the Adversary We model the adversary's background knowledge using a probability distribution , and call Pr 1 tupleindependent when these are independent events. Clearly, we do not know Pr 1 , only the attacker knows it, and we should design our privacy algorithm assuming the worst about Pr 1 . As we shall see, however, it is impossible to achieve privacy and utility when the attacker is all powerful, hence we will make reasonable assumptions about Pr 1 below.
Modeling the Algorithm Given an instance I, a privacy-preserving algorithm A will make some random choices and compute a view V . We denote Pr I 2 [V ] the probability distribution on the algorithm's outputs, i.e.
Unlike Pr 1 , we have total control over Pr 2 , since we design the algorithm A.
As the algorithm A needs to be publicly known, an adversary can compute the induced probability Pr 12 [t i |V ] based on his prior distribution Pr 1 and the algorithm's distribution Pr 2 , namely Pr 12 [t i |V ] = I⊆D:t∈I Pr I 2 [V ]Pr 1 [I]. We call Pr 1 [t] as the prior probability of tuple t while Pr 12 [t|V ] is called the posterior probability of t conditioned on view V . Throughout this paper we assume that the adversary is computationally powerful and that Pr 12 [t|V ] can always be computed by the adversary irrespective of the computation effort required.

Classification of Adversaries
Dwork's impossibility result [3] suggest that it is impossible to anonymize data such that it is both useful and protects against arbitrary adversaries. If taken literally, it seems to say that anonymization is hopeless. However, there are lots of examples in practice when data is being anonymized and published under risks considered to be acceptable, and this indicates that the privacy definition used by Dwork is too general.
We propose here to study adversaries with restricted power, based on placing a bound on his prior knowledge, and will show that for certain values of this bound privacy is possible.
Specifically, we restrict the adversaries by assuming that for every tuple t his prior probability Pr 1 [t] is either small, or equal to 1. In the first case we will seek to hide the tuple from the adversary; in the second case there's nothing to do, since the adversary already knows t. Another way to look at this is that we require the algorithm to preserve the privacy for tuples for which Pr 1 [t] is small: if Pr 1 [t] is large, we may well assume that it is 1, in essence giving up any attempt to hide t from the adversary. We also consider a sub-class of d-bounded adversaries called the d-independent adversary, which further require Pr 1 to be tuple-independent:

Privacy definition and motivation
Our definition of privacy is based on comparing the prior probability Pr 1 [t] with the a posteriori probability Pr 12 [t | V ], as standard in the literature. We consider here two definitions, one relative and one absolute, and will prove that, in some sense, they are equivalent.
3. An algorithm is called (d, δ)-relative-private if the following holds for all d-independent adversaries P r 1 , views V , and tuples t: Denoting de δ = γ, the definition can be written as: If tuple t fails the left (or right) inequality then we say there has been a negative (or positive) leakage, respectively. Note that positive leakage resembles the notion of positive (ρ 1 , ρ 2 ) breach as described in [5]. We prove the following in the Appendix: Proposition 2.5. Every (d, δ)-relative-private algorithm is (d, γ)-private for γ = de δ . Conversely, every (d, γ)private algorithm is (d, δ)-relative-private for

Utility
As explained earlier, we are interested in supporting counting queries over some predicates. More generally, we define a query Q to be any subset of the domain D, i.e. Q ⊆ D. The result of the query over the instance I is simply |Q ∩ I|, which we denote as Q(I). For example, the query count the number of tuples with age between 26 and 31 and score > 91 is expressed as Q(I), where Q denotes all tuples in the domain having age in [26, 31] score > 91. For any algorithm A, using the knowledge of how the algorithm publishes its view one can obtain an estimate for Q(I). Let EST (Q, V ) be the estimate 2 of Q(I) as obtained from the published view V . Additionally, let |Q(I) − EST (Q, V )| be the absolute error for a query Q. We require the algorithm to be such that EST (Q, V ) provides a good approximation for Q(I).
Definition 2.6. A randomized algorithm A is called useful if there exists an estimator EST (Q, V ) s.t. for any ǫ > 0 there exists a constant ρ such that for all domain size m, database size n, and query Q:

Discussion
Our working definition of privacy is (d, γ)-privacy, where d intuitively corresponds to the prior, and γ to the posterior. An intuitive reference point for d is d = n/m, since the expected size of I is n for the independent distribution where Pr 1 [t] = n/m for all t. γ is larger, and should be measured in absolute values. For example, γ = 0.05 means that the view V leaks no tuple t with more than 5% probability. The motivation for our definition of utility is to give a guarantee on the absolute error of the estimator. It is stated as ∀ǫ.∃ρ rather than ∀ρ.∃ǫ because the latter is trivially satisfied by any estimator (simply choose ǫ = 1). The absolute error is expressed as ρ √ n for two reasons. On one hand we do not want small errors: if one could estimate Q(I) with an error < 1 then there would be privacy breaches, as we have seen. On the other we do not want big errors: any estimator is accurate with probability 1 if the absolute error is n. In between 1 and n we have chosen ρ √ n. k-anonymity and l-diversity satisfy neither (d, γ)-privacy nor usefulness.
Considering a d-independent adversary, privacy is compromised when the adversary knows that some tuples have very low probability. To see the intuition, consider the instance in Table 2(c). Suppose a d-independent adversary is trying to find out Joe's test score, and he knows that Joe is likely to have a low score: i.e. the prior is such that Pr 1 [t] is very low for a tuple saying that Joe's score is greater than 95, and larger (but still ≤ d) for tuples saying that his score less than 90. If the adversary knows that Joe's age is less than 30, then his record is among the first three: since the first two tuples have a very low probability (as their scores are 99, 97), the adversary concludes that Joe's scores is 82 with very high probability. There is no utility either. Suppose we want to estimate the number of students between 29 and 31 years old from Table 2(c): the answer can be anywhere between 0 and 6, and, if our estimate is the average, 3, then the only way we can guarantee any accuracy is by making assumptions on the distribution of the data, in essence by knowing Pr 1 .
By contrast, the algorithm described in Sec. 4 takes two constants k, γ and is both (k n m , γ)-private and also useful: for any ǫ, it gives ρ = 4 3 k γ ln( 2 ǫ ).

Impossibility Results
We prove here that no (d, γ)-private algorithm can provide even a weak notion of utility if d = Ω(n/ √ m). For that we first establish an impossibility result for a weaker notion of privacy, called ǫ-indistinguishability, and a very weak notion of utility, called meaningfulness: in this form, our result is an improvement of the impossibility result in [4]. Then we establish an impossibility result for our notions of privacy and utility.

The Strong Impossibility Result
Consider the following alternative definition of privacy [4]: 1. An algorithm is ǫ-indistinguishable if for all database instances I and I ′ which disagree exactly over a pair of tuples (i.e. |I| = |I ′ | and | I − I ′ |= 2) and for all views V , The weak notion of utility, which we call meaningfulness was first considered in [4] and is based on the notion of statistical difference:

Definition 3.2. The statistical difference between two distributions Pr A and Pr
Note that SD(Pr A , Pr B ) ∈ [0, 2]: it is 0 when Pr A = Pr B , and is 2 when ∀x.(Pr A (x) = 0 ∨ Pr B (x) = 0). We explain now informally the connection between statistical difference and utility (the formal connection is in Prop 3.6 below). Suppose an algorithm A gives reasonable estimates to counting queries Q. Let Q be a "large" query, i.e. if executed on the entire domain it returns sizeable fraction, say 1/5. When we estimate Q on the view published for a particular instance I we will get some errors, which depend on actual size n = |I|. If there is any utility to A then a user should be able distinguish between the two extreme cases, when Q(I) = n and when Q(I) = 0. To capture this intuition, define the uniform distribution P r 1 : ∀I s.t |I| = n, P r 1 .
Note that m n is the number of instances of size n. Thus P r 1 makes every instance of size n equally likely. Let E Q be the event (|I| = n ∧ Q(I) = n), and E ′ Q the event (|I| = n ∧ Q(I) = 0). Then we expect to be able to differentiate between the following two distributions: is smaller than 1/2 for a fraction 2/3 of queries Q.
Next we state the strong impossibility result using meaningfulness as the definition of utility. For the sake of concreteness we use the constant 1/2 for statistical difference and 2/3 for the fraction of queries in the definition of meaningfulness. However, the impossibility result works for arbitrary constants.
Theorem 3.4 (Strong Impossibility). There exists a constant c independent of m and n such that every algorithm which satisfies ǫ-indistinguishability with e ǫ ≤ c m n 2 is meaningless. Before giving the proof, we comment on how this result extends a similar result in [4]. First, we have generalized it to a larger class of queries: the previous result restricts the class of selection queries to certain xor operations, here we allow arbitrary selection queries. Secondly, we improve the bound on the statistical difference. This was possible because the original proof relies on a chaining argument which provides a bound on the statistical difference of a function at each step of the chain to eventually compute the statistical difference of Pr A and Pr B . At each step it considers tuples as points in a high dimensional space and bounds the statistical difference of a function which satisfies ǫ-indistinguishability over tuples. We observe that each database instance can be thought of as a point in a higher dimensional space and thus bound the statistical difference of a function which satisfies ǫ-indistinguishability over instances. Proof of Theorem 3.4: Consider all instances I such that |I| = n. The number of such instances with all distinct tuples is m n . Moreover, as A satisfies ǫ-indistinguishability, for any pair of instances I and I ′ where |I| = |I ′ | = n and |I − I ′ | = 2, We denote by P r 12 [V ] the probability that the view V is published. If P r 1 is the uniform distribution then Let us represent the set of instances for which Q(I) = n as S Q . Then |S Q | is mτ n . Let E Q be the event that input database instance I belongs to S Q . P r 12 [V |E Q ] is the probability that the view V is published if an instance I is picked uniformly at random from the set S Q . Fix α = 1 6 . As τ ≥ 1 2 (1 + f ) and f is a constant independent of n and m, with probability greater than

Impossibility for (d, γ)-Privacy
We show now how the strong impossibility result translates to our notions of privacy/utility. First, we show that (d, δ)-relative-privacy implies ǫ-indistinguishability. Note that the former is a privacy notion about an adversary, while the latter does not talk about any adversary. The proof of the following theorem is in the appendix.
Proof: Consider the distributions Pr Q A , Pr Q B defined above, for the events E Q = (Q(I) = n) ∧ (|I| = n) and Since the algorithm is useful, we will choose the value ǫ = 1 4 in Definition 2.6, and obtain a value for ρ. Let I 0 be the set of instances I such that Q(I) = 0 and |I| = n. Similarly, let I n be the set of instances I ′ such that Q(I ′ ) = n and |I ′ | = n.
As A is useful, a view V ∈ V 0 would be published on any I ∈ I 0 with probability greater than 3 4 . Thus, If n ≥ 2ρ √ n then V 0 and V n have to be disjoint. As ρ is independent of n, we can choose a large enough n such that √ n ≥ ρ. For those values of n, the statistical difference between Pr Q A and Pr Q B is at least 2( 3 4 − 1 4 ) = 1, for every Q. Thus any useful algorithm is also meaningful   • There is positive leakage: This completes the proof.

Algorithm
As we have seen, it is impossible to guarantee absence of privacy breaches against all d-independent adversaries if d = Ω( n √ m ). In this section, we present a simple algorithm which is (d, γ)-private. Here, d and γ are parameters given to the algorithm. The utility of the algorithm depends on the values of d and γ and a guarantee for the utility can be made only for d = k n m , for any fixed constant k (hence d = O( n m )). Assume that the input database instance is I ⊆ D. The insert-remove algorithm computes the view V as following: • For every tuple in I, insert it in the V independently with probability α • For every tuple in D which is not in I, insert it in the view V independently with probability β • Publish D, V , α, β.

Privacy Analysis
If d ≤ γ then β ≤ α. Now consider the following two cases: • t is present in the published view. Thus P r[V |t] = α and P r[V |t] = β. Using this we get, On the other hand, for negative leakage, note that P r • t is not present in the published view. Thus P r[V |t] = 1 − α and P r[V |t i ] = 1 − β. Using this we get, As αp αp+β(1−p) is an increasing function of α β for a fixed p. Thus even in this case we have P r[t|V ] ≤ γ.

Utility Analysis
The estimator EST (Q, V ) is the following. Recall that α and β are published.
• Let n V = Q(V ); that is n V =| Q ∩ V | is the query evaluated on the view V .
• Let n D = Q(D); that is n D =| Q | is the query evaluated on the entire domain (we explain below how to do this efficiently) • Define: Let r be a constant and α, β be such that α ≥ 1 2 and β ≤ r 4 n m . Then for any ǫ > 0, denoting ρ = 2 3rln( 2 ǫ ) we have: It follows that the algorithm is useful for α ≥ 1 2 and β ≤ r which reduces to Instead of using µ V , we use n V and obtain EST (Q, V ). Thus, the absolute error Σ = |Q(I) − EST (Q, V )| is Using Chernoff bound we can say that with an probability 1 − 2e − µ V δ 2

3
, the fractional error |µV −nV | µV ≤ δ. Thus , we know that Σ ≤ δµV α−β . Hence, for δ = 3ln 2 ǫ µV , with probability greater than 1 − ǫ the following holds: As α = 1 2 and β ≤ r 4 n m , we can guarantee that the error Σ would be less than 2 3rln( 2 ǫ )n with probability greater than 1 − ǫ. Since ǫ was arbitrary, the algorithm is useful. This completes the proof. Assuming that d ≤ γ 2 , for satisfying the trade off between privacy and utility we can choose α = 1 2 and a suitable β, if This is true when d γ ≤ r 4 n m . Thus for d = k n m , the algorithm satisfies (d, γ)-privacy and is also useful, as can be seen by setting ρ = 4 3 k γ ln( 2 ǫ ) for ǫ > 0.

Discussion
Choice of parameters Suppose we want to ensure (k n m , γ)-privacy, where k is a constant, i.e. d = k n m is the bound on the adversary's prior probability, and γ is the bound on the posteriori probability that is acceptable for us. We also want to ensure utility. Choosing α = 1 2 satisfies both Theorems 4.1 (assuming d/γ < 1/2) and 4.2. Next, we choose β = k γ n m = d γ . This satisfies Theorem 4.1 (since 1 > 1−γ 1−d α), and also satisfies Theorem 4.2 whenever k γ ≤ r 4 . In other words, with these choices of parameters we have (d, γ)-privacy, and a utility that is captured by ρ = 2 3rln( 2 ǫ ), where r = 4k γ (smaller r's are better for utility). The privacy/utility tradeoff is like this. We want to protect against a powerful adversary, i.e. large k: we want to protect well, i.e. small γ; and this limits the utility expressed by r.
The View Size A concern about this algorithm is the potential size increase of the view: since most of the privacy comes from the newly inserted tuples (i.e. β), clearly V will be larger than I. The expected size of V is simply nα + (m − n)β. . . m a is huge. The large size of the domain means that the estimator needs to compute Q(D) = |Q ∩ D| efficiently. This is easy, since Q is usually a conjunction of predicates over several attributes, hence can be computed on each D i independently. Secondly, in the insertion phase of the algorithm tuples from the domain are added by first computing the number of tuples to be added using a binomial distribution with parameters m − n and β. Then a sample of that size is drawn by randomly selecting tuples from the domain without replacement.
A Case Study To understand the tradeoff between privacy and utility, we experimented with US census data in the Adults database which has also been used for experiments in ( [8], [1]). The database I has 9 attributes and n = 30162 tuples. The product of the attributes active domains has m = 648023040 tuples, thus n/m ≈ 4.65 × 10 −3 . We chose the parameters α and β to ensure (10n/m, 0.2)-privacy: i.e. the adversary's prior is Next we tested the utility of this data, by running all possible selection queries with up to three attributes.

Tuple correlations
So far our analysis was restricted to tuple-independent adversaries. This restriction strengthens the impossibility result, and weakens that of the algorithm. Here we discuss several extensions to tuple correlations. First, we show that if the adversary knows arbitrary correlations, then no algorithm can achieve both privacy and utility. Then we examine a restricted class of correlations, which is sufficiently general to model join/link attacks: we show that our algorithm still guarantees privacy against positive leakages (utility, of course, is unchanged), but it cannot protect against negative leakage. The policy of protecting against positive leakage while permitting negative leakage is sometimes acceptable in practice, and it raises the question whether our algorithm could be strengthened in this case: after all the result in Corollary 3.7 relies on both negative and positive leakages. We answer this negatively, by giving a variant of the impossibility result for positive leakages only.

Arbitrary Correlations
Suppose we publish a view V of a database of diseases with schema (age, zip, disease) using our algorithm. An attacker knows the age and zipcode for both Joe and Jim. Now Joe and Jim are brothers: if one has diabetes, then the other is quite likely to have diabetes as well (at least that's what the attacker believes). Suppose the attacker finds two tuples in V matching both Joe and Jim having diabetes. The probability that none was in I and were inserted by the algorithm is very small: β 2 . In contrast, because of their strong correlation, the probability that they were in the instance I is now much larger: . Thus, upon seeing both tuples the attacker concludes that they are Joe and Jim's with high probability. This is the reason why our algorithm has difficulties hiding data when the prior has correlations.
We show here that even for d ≥ n m no private and useful algorithm exists if the adversary is allowed to know arbitrary correlations. The proof appears in the appendix.
Theorem 5.1. If A is a useful algorithm, then for any ǫ > 0 there exists n such that for every d ≥ n m there is a d-bounded adversary and tuple t such that P r 1 [t] ≤ d but P r 12 [t|V ] ≥ 1 − 2ǫ

Exclusions
We consider now some restricted forms of correlations: exactly one tuple from a set of tuples occurs in the database. • Tuples are pairwise independent if they do not belong to the same set.

• Exactly one tuple in each set occurs in the database instance
This type of correlations model naturally adversaries performing join/link attacks. Such attackers are able to determine some of the identifying attributes of a particular tuple, say the age and nationality of a person that they know must occur in the database. The adversary can thus identify a set of tuples S j of the domain such that exactly one tuple in the set belongs to the database.

Positive results for d-exclusive adversaries
We have already seen the privacy analysis for the insert-remove algorithm against d-independent adversaries. In this section, we show that the algorithm provides a slightly weaker form of guarantee for d-exclusive adversaries. We show that the algorithm ensures that there is no positive leakage for negatively correlated d-bounded adversaries: That is if Pr 1 [t] ≤ d then Pr 12 [t|V ] ≤ γ. The proof of the theorem appears in the appendix. The algorithm cannot guarantee absence of negative leakage for d-exclusive adversaries, as seen from the following example: Example 5.4 Suppose we publish a view V of a database of diseases with schema (age, zip, disease) using our algorithm. An attacker knows the age and zipcode of a person Joe and additionally knows that no other person in the database has the same combination of age and zipcode. The prior belief of the attacker is that Joe has exactly one disease but any one of the diseases is equally likely. Suppose the attacker finds a tuple t 1 in V matching Joe and Diabetes. Let us consider the tuple t 2 corresponding to Joe and Malaria. Theorem 5.3 shows that there won't be a positive leakage for t 1 . However, for t 2 there is a drastic drop in the a posteriori probability causing a negative leakage.

Impossibility results for d-exclusive adversaries
In this section we extend the impossibility result for d-exclusive adversaries to accommodate the case when negative leakage is legally allowed and only positive leakage is considered as a privacy breach. The impossibility result shows that if an algorithm satisfies some form of weak utility then there exists a d-exclusive adversary, for d = Ω( n √ m ), which can infer that a certain tuple exists in the database with high probability. The extension works only for a restricted class of randomized algorithms. However, the class is broad enough to encompass many of the privacy preserving algorithms in the literature. The class of algorithms which we consider satisfy the following bucketization assumptions: • The algorithm is such that if the prior distribution is tuple independent then the posterior distribution is also tuple independent. More formally, the tuples in the domain can be partitioned into buckets such that the distribution P r 12 [t i |V ] over the tuples obeys the following condition: If two tuples t i and t j lie in different buckets then they are independent conditioned on the view.
• Let the number of buckets be N B . We assume that the distribution of tuples both of the database instance and the domain among the buckets is not too skewed. More formally , for every k > 1 there exists a N k < N B such that if we remove any N k buckets, the remaining still contain a fraction 1/k of tuples of I as well as D.
For example consider the method of full domain generalization (in [7]) as applied to ensure k-anonymity or the anatomy method (in [11]) as applied to ensure l-diversity. For both the methods the tuples corresponding to the different anonymized groups form buckets which satisfy the assumptions above.
To show the impossibility result for d-independent adversaries, we used ǫ-indistinguishability as the privacy definition and meaningfulness as the utility definition. Impossibility result for d-exclusive adversaries requires a slight modification to both privacy and utility definitions.
Thus ǫ-indistinguishability over a set D ′ is a relaxation of the original ǫ-indistinguishability definition. Next we consider the notion of utility called k-meaninglessness. The notion of utility is a generalization of meaninglessness and is also defined for counting queries Q s.t 1 2 ( for a constant f < 1. Intuitively, the definition tries to capture the fact that an algorithm will have bad utility if many queries Q have an error of O(n) in their estimates.
Definition 5.6. An algorithm is called k-meaningless, if there is a set S with |S| ≤ n(1 − 1 k ) such that the distributions P r ′Q A and P r ′Q B have a statistical difference smaller than 1/2 for a fraction 2/3 of the queries Q. P r ′Q A : P r 12 [V |E Q ] where E Q is the event Q(I) = |Q ∩ S| and |I| = n P r ′Q B : P r 12 [V |E ′ Q ] where E ′ Q is the event Q(I) = |Q ∩ S| + n k and |I| = n Note that for k = 1, the definition reduces to notion of meaninglessness. k-meaninglessness follows the same intuition: If SD(P r ′Q A , P r ′Q B ) is small then it would be impossible to distinguish whether the original answer is |Q ∩ S| or |Q ∩ S| + n k thus resulting in an error of at least n k . Cor. 5.7 relates the notions of ǫ-indistinguishability over the set D ′ and k-meaninglessness; the proof appears in the appendix.
Corollary 5.7. Let D ′ be a set of tuples such that |D ′ | ≥ m k and |D ′ ∩ I| ≥ n k , for some constant k independent of m and n. Then there exists a constant c such that every algorithm which satisfies ǫ-indistinguishability over the set D ′ with e ǫ ≤ c m n 2 is k-meaningless. We call any algorithm which is not k-meaningless as k-meaningful. As any algorithm which is meaningless is also k-meaningless, it implies that every k-meaningful algorithm is meaningful. The proof of Theorem 5.8 appears in the appendix. We give a brief overview outlining the intuition: We argue that for a k-meaningful algorithm which satisfies the bucketization assumptions, there exists a d ′ -independent adversary for which either there is a positive leakage on one tuple or there is negative leakage on lot of tuples. The presence of multiple negative leakages is shown by using the fact that, for a k-meaningful algorithm, any large set containing a significant fraction of tuples of the database will have leakage on some tuple. Using the bucketization assumption we prove that if there is no positive leakage, then many buckets will contain tuples having negative leakage. In case of positive leakage we are done as the d ′ -independent adversary serves as d-exclusive adversaries. In the case of multiple negative leakages, we explicitly construct a d-exclusive adversary using the d ′ -independent adversary such that there is positive leakage for at least one tuple. Here, we use d ′ = d/3.

Conclusions
We have described a formal framework for studying both the privacy and the utility of an anonymization algorithm. We proved a tight bound between privacy and utility, based on the attacker's power. For the case where privacy/utility can be guaranteed, we have described a new, quite simple anonymization algorithm, based on random insertions and deletions of tuples in/from the database. We have done a limited empirical study, and saw a good privacy/utility tradeoff. Our algorithm increases the size of the data, but by tolerable amounts (a factor of 10, in our empirical study). It will be interesting to study in future work ways to reduce the size of the published view.

A Relationships among privacy definitions
A.1 (d, γ)-privacy and (d, δ)-relative-privacy Proposition (2.5). Every (d, δ)-relative-private algorithm is (d, γ)-private for γ = de δ . Conversely, every (d, γ)private algorithm is (d, δ)-relative-private for Proof: The proof of the first part trivially follows from the definitions. For the converse let A be a (d, γ)-private algorithm. Thus A ensures no positive/negative leakage for all d-independent adversaries. We shall use this fact to show that A should satisfy (d, δ)-relative-privacy. For this we consider P r 12 [t i |V ] purely as a function of P r 1 [t 1 ] while keeping the prior probability of all other tuples constant. Let us call the function as f . We compute the function explicitly as: Here, I t represent the set of instances which contain t i and It represent the set which does not. For each instance I j in the set I t we can decompose P r 1 [I j ] as P r 1 [t i ]P r 1 [T j ] where T j is the event that denotes that only the tuples in I j except for t i occur in the database. This decomposition is possible because of tuple independence in P r 1 . Using this decomposition we can rewrite P r 12 [t 1 |V ] as where c 1 and c 2 are constants as we vary P r 1 [t i ] and keep the prior probabilities of all other tuples constant. Let us represent P r 12 [t i |V ] as the function We notice that the function is increasing in x and has slope c1 c2 at the origin. Additionally, if c 1 ≥ c 2 then f (x) ≥ x for all x. On the other hand if c1 < c 2 then f (x) ≤ x for all x. We are interested in the maximum and minimum possible values of f (x) x . The maximum occurs when c 1 > c 2 at points near the origin and is equal to c1 c2 . The fact that A has be safe from privacy leakages imposes certain restrictions on f . One condition is that It follows that such an algorithm A is also (d, δ)-relative-private for e δ = max( γ(1−d)

A.2 (d, δ)-relative-privacy and ǫ-indistinguishability
For proving Proposition 3.5, we need to show the following lemma, Lemma A.1. Let A be a (d, δ)-relative-private algorithm. Then, for all tuples t i such that P r 1 [t i ] ≤ d, Proof: Assume P r 1 (t i ) ≤ d. Additionally, we know that It is easy to see that using the above two inequalities we can bound P r12[ti|V ] P r1 [ti] as required. This completes the proof.
Using sandwich theorem on (1), we note that Thus, for any given δ, we can choose d small enough such that 1 2 Proposition (3.5). Every (d, δ)-relative-private algorithm satisfies ǫ-indistinguishability with ǫ = 2δ + 2 ln (2) Proof: Consider a d ′ for which P r ′ 1 is such that We know that such a d ′ exists for every δ. If d ≤ d ′ then we let P r ′ 1 = P r 1 . On the other hand if d > d ′ , then we use the fact any (d, δ)-relative-private algorithm would also be (δ, d ′ )-private algorithm and hence from here on we consider the algorithm as (δ, d ′ )-private and assume that equation (2) holds true for P r 1 .
Consider any two database instances I and I ′′ which differ in exactly one tuple with I containing one extra tuple t 1 . Then we can represent I as t 1 ∩ T and I ′′ ast 1 ∩ T . Here T represents the event that all tuples in I ′′ belong to the database and all tuples inĪ do not belong to the database.
Consider a d-independent adversary for which P r 1 [T ] = 1 but P r 1 [t 1 ] ≤ d. As the algorithm satisfies (d, δ)-relative-privacy, it should be safe against such an adversary. Thus, Similarly consider the database instances I ′ and I ′′ such that I ′ has one extra tuple t 2 . Again, we observe that Thus, combining the two inequalities we can see that there exists an ǫ = 2(δ + ln (2)) such that  Here |x − y| is the symmetrical difference between the instances x and y. Thus |x − y| represents the number of tuples in which x and y disagree. We use the notation a i = |x−y|=2i Note that i b i = 0. Moreover we can rewrite b i as the product of m−n i n n−i and . We can see that the first factor is always positive while the second factor decreases as i increases.
For the sequence a i it is easy to see that If e ǫ ≤ mτ −2n Hence there are i 2 such instances. Note that ∀y ′ ∈ S y , p(y ′ ) ≤ e ǫ p(y). On the other hand each instance y ′ ∈ ∪ y∈S x i S y is obtained from exactly (n − i + 1)(m − n − i + 1) instances from S x i . Thus Similarly we can show that a i ≤ e ǫ a i−1 . This completes the proof Proof: The proof is exactly the same as in the proof of Lemma 2 shown in [4].
C Tuple correlations C.1 Arbitrary correlations Theorem. 5.1 If A is a useful algorithm, then for any ǫ > 0 there exists n such that for every d ≥ n m there is a d-bounded adversary and tuple t such that P r 1 [t] ≤ d but P r 12 [t|V ] ≥ 1 − 2ǫ Proof: Let I be the input instance and n = |I|. Consider a d-bounded adversary with the following tuple correlations: The adversary knows that either all tuples of the set S = I belong to the database or none of the tuples belong to the database. Consider the query Q = S. As the algorithm is useful, for every ǫ there exists a ρ such that the |EST (Q, V ) − Q(I)| ≤ ρ √ n with probability greater than ǫ. If n is large enough, then it follows that algorithm cannot output the same view on I and any instance I ′ in the set {I ′ |S ⊂ D − I ′ } with probability greater than 2ǫ. Hence, from the view there will be a breach with probability greater than 1 − 2ǫ. Proof: The probability P r[t i |V ] is only dependent on which tuples in S appear in V . It is clear that maximum privacy leakage happens when V contains t i but does not contain any other tuple from S. In that case, P r[V |t i ] = α(1−β) (|S|−1) and P r[V |t j ] = β(1−α)(1−β) (|S|−2) . Also, let P r[t i ] = p. For a d-exclusive adversaryt i = ∪ j =i t j . Thus we get, This completes the proof. Proof: As A is k-meaningful, it is also meaningful. By Corollary 3.7 we know that there exists a d ′ -independent adversary Ad 1 which either has a positive leakage or negative leakage. Here we use d ′ such that d ′ = d 3 . If it has positive leakage then that adversary serves as the required d-exclusive adversary. On the other hand, if it has negative leakage on tuple t 1 we choose the bucket B 1 which contains that tuple. The set D ′ = D − B 1 is thus the set of tuples which are conditionally independent of tuple t 1 .
Let us define, I ′ = I ∩ D ′ . We know from the bucketization assumptions that |D ′ | ≥ |D| k and I ′ ≥ |I| k . Let us define, e ǫ = max I,I ′ P r2[V |I] P r2[V |I ′ ] for all I and I ′ which disagree over a single pair of tuples with both of them in D ′ . As A is k-meaningful, from Corollary 5.7, we know that e ǫ = Ω( m n 2 ). By restricting over the set D ′ and using Corollary 3.7, it follows that there exists a d ′ -independent adversary Ad ′ 2 for which there is a leakage for some tuple t 2 in the set D ′ . If there is positive leakage for t 2 then Ad ′ 2 serves as the required d-exclusive adversary. If there is negative leakage on t 2 then let the bucket which contains it be B 2 . Consider the adversary Ad 2 which has prior of Ad ′ 2 for tuples in B 2 and prior of Ad 1 for tuples in B 1 . As the posterior probabilities of tuples in B 2 are independent of that of tuples in B 1 even conditioned on V , the leakages for Ad ′ 2 in B 2 and for Ad 1 in B 1 would be preserved for Ad 2 . Thus, Ad 2 has negative leakage for both tuples t 1 and t 2 .
We repeat this procedure 3 d times, with buckets being B i for i ∈ [1, 3 d ]. Define B = ∪ i B i and D B = D − B. As N k ≥ 3 d , by the bucketization assumptions on the algorithm, it follows |D B | ≥ m k and |D B ∩ I| ≥ n k . Hence, Corollary 5.7 holds for each step and we can show that there is either a d ′ -independent adversary for which there is positive leakage on some tuple or there exists a d ′ -independent adversary Ad for which there is negative leakage on at least 3 d tuples. In the former case, we have the required d-exclusive d-bounded adversary. For the latter case, let the set of tuples with negative leakage be S ′ . We know that each tuple in S ′ belongs to a different bucket. Thus, we can increase the prior probability of each tuple t i in S so that P r 1 [t i ] = d ′ . The negative leakage on each t i ∈ S is still preserved because as shown in the proof of Proposition 2.5, the ratio P r12[ti|V ] P r1 [ti] increases by at most 1 1−d ′ if we increase P r 1 [t i ] to d ′ while keeping the prior probability of all other tuples constant. For d ′ ≤ 1 2 , the increase in the ratio is by a factor of at most 2, thus preserving the negative leakage.
Additionally there exists at least one tuple for which the prior P r 1 of Ad is such that P r 12 [t p |V ] = cd ′ . This is because D B contains at least m k tuples and Ad can have any prior probabilities for each one of them as they will never effect the posterior probabilities of the leaking tuples. So, we can change the prior of any tuple in D ′ so as to get the required posterior probability for t p . This is shown in Lemma C.1 proved in the appendix. Let us define S as S ′ ∪ t p Using Ad we construct a d-exclusive adversary Ad ′ having positive leakage on tuple t p . Ad ′ corresponds to the adversary who knows exactly one tuple in S occurs in the database instance. We construct Ad ′ from Ad by making the prior probability of each illegal instance (instances which do not exactly one tuple from S) as 0. We do this by distributing the probability of each such illegal instance over the entire set of legal instances such that the probability of every legal instance increases by an amount proportional to its original probability. Let L denote the set of legal instances and IL denote set of illegal instances.
For Ad, Let us call τ = I ′ ∈IL P r Ad In Ad ′ this sum gets distributed to every legal instance and thus P r Ad ′ 1 [I] = P r Ad 1 [I]( 1 1−τ ) for every legal instance I. We know that Thus Ad ′ is d-bounded. Lemma C.2, proved in the appendix, shows that the constructed adversary Ad ′ is indeed d-exclusive. We next show that there is a positive leakage on tuple t p for Ad ′ . Let us compute for any t i in S ′ and t p the ratio P Note that (4) can be derived from (3) as both the summation are being done over a subset of legal instances. Also (6) is true as there is negative leakage for t i and P r Ad 12 [t p |V ] = cd. Note that (6)  . Hence there exists a d-exclusive adversary for which there is positive leakage for at least one tuple. This completes the proof.
Lemma C.1. Let A be a k-meaningful algorithm. Let D ′ ⊂ D be a set of tuples such that |D ′ | ≥ m k and |D ′ ∩ I| ≥ n k . Then there exists a tuple t in D ′ such that P r u 12 [t|V ] ≥ c ′ n m for the uniform tuple independent distribution P r u 1 and some constant c ′ independent of n and m. Let us define I ′ = D ′ ∩ I. For the algorithm to have some utility over domain D ′ , there exists a constant l with l > k for which some query Q has the following properties: |Q ∩ I ′ | ≥ n k and EST (Q, V ) D ′ ≥ n l . If not then it would be impossible to distinguish whether Q(I) ≥ n k or Q(I) ≤ n l from the view for every query Q. As EST (Q, V ) D ′ = ti∈D ′ P r u 12 [t i |V ] ≥ n l . This means, there exists a tuple t in D ′ such that P r u 12 [t|V ] ≥ n lm . Hence proved.
Note that P r u 12 [t|V ] P r u 1 [t] = 1 l . As shown in the proof of Proposition 2.5 increasing the prior probability to d will change the ratio of posterior to prior probability to d d+l ≤ d 2l . Thus, for the tuple t there exist Pr 1 such that P r 12 [t|V ] ≥ cd.
Lemma C.2. The constructed adversary Ad ′ is d-exclusive Proof: We show that Ad ′ is d-exclusive adversary by first showing that all tuples t 1 and t 2 which are not in S are still independent. Let us define E as the event that exactly one tuple in S occurs in the database. We know that