A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Privacy Model for Attacks <s> We initiate a theoretical study of the census problem. Informally, in a census individual respondents give private information to a trusted party (the census bureau), who publishes a sanitized version of the data. There are two fundamentally conflicting requirements: privacy for the respondents and utility of the sanitized data. Unlike in the study of secure function evaluation, in which privacy is preserved to the extent possible given a specific functionality goal, in the census problem privacy is paramount; intuitively, things that cannot be learned “safely” should not be learned at all. ::: ::: An important contribution of this work is a definition of privacy (and privacy compromise) for statistical databases, together with a method for describing and comparing the privacy offered by specific sanitization techniques. We obtain several privacy results using two different sanitization techniques, and then show how to combine them via cross training. We also obtain two utility results involving clustering. <s> BIB001 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Privacy Model for Attacks <s> An organization makes a new release as new information become available, releases a tailored view for each data request, releases sensitive information and identifying information separately. The availability of related releases sharpens the identification of individuals by a global quasi-identifier consisting of attributes from related releases. Since it is not an option to anonymize previously released data, the current release must be anonymized to ensure that a global quasi-identifier is not effective for identification. In this paper, we study the sequential anonymization problem under this assumption. A key question is how to anonymize the current release so that it cannot be linked to previous releases yet remains useful for its own release purpose. We introduce the lossy join, a negative property in relational database design, as a way to hide the join relationship among releases, and propose a scalable and practical solution. <s> BIB002 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Privacy Model for Attacks <s> Privacy preservation is an important issue in the release of data for mining purposes. The k-anonymity model has been introduced for protecting individual identification. Recent studies show that a more sophisticated model is necessary to protect the association of individuals to sensitive information. In this paper, we propose an (α, k)-anonymity model to protect both identifications and relationships to sensitive information in data. We discuss the properties of (α, k)-anonymity model. We prove that the optimal (α, k)-anonymity problem is NP-hard. We first presentan optimal global-recoding method for the (α, k)-anonymity problem. Next we propose a local-recoding algorithm which is more scalable and result in less data distortion. The effectiveness and efficiency are shown by experiments. We also describe how the model can be extended to more general case. <s> BIB003 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Privacy Model for Attacks <s> In 1977 Dalenius articulated a desideratum for statistical databases: nothing about an individual should be learnable from the database that cannot be learned without access to the database. We give a general impossibility result showing that a formalization of Dalenius' goal along the lines of semantic security cannot be achieved. Contrary to intuition, a variant of the result threatens the privacy even of someone not in the database. This state of affairs suggests a new measure, differential privacy, which, intuitively, captures the increased risk to one's privacy incurred by participating in a database. The techniques developed in a sequence of papers [8, 13, 3], culminating in those described in [12], can achieve any desired level of privacy under this measure. In many cases, extremely accurate information about the database can be provided while simultaneously ensuring very high levels of privacy <s> BIB004 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Privacy Model for Attacks <s> Privacy is a serious concern when microdata need to be released for ad hoc analyses. The privacy goals of existing privacy protection approaches (e.g., k-anonymity and l-diversity) are suitable only for categorical sensitive attributes. Since applying them directly to numerical sensitive attributes (e.g., salary) may result in undesirable information leakage, we propose privacy goals to better capture the need of privacy protection for numerical sensitive attributes. Complementing the desire for privacy is the need to support ad hoc aggregate analyses over microdata. Existing generalization-based anonymization approaches cannot answer aggregate queries with reasonable accuracy. We present a general framework of permutation-based anonymization to support accurate answering of aggregate queries and show that, for the same grouping, permutation-based techniques can always answer aggregate queries more accurately than generalization-based approaches. We further propose several criteria to optimize permutations for accurate answering of aggregate queries, and develop efficient algorithms for each criterion. <s> BIB005 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Privacy Model for Attacks <s> The k-anonymity privacy requirement for publishing microdata requires that each equivalence class (i.e., a set of records that are indistinguishable from each other with respect to certain "identifying" attributes) contains at least k records. Recently, several authors have recognized that k-anonymity cannot prevent attribute disclosure. The notion of l-diversity has been proposed to address this; l-diversity requires that each equivalence class has at least l well-represented values for each sensitive attribute. In this paper we show that l-diversity has a number of limitations. In particular, it is neither necessary nor sufficient to prevent attribute disclosure. We propose a novel privacy notion called t-closeness, which requires that the distribution of a sensitive attribute in any equivalence class is close to the distribution of the attribute in the overall table (i.e., the distance between the two distributions should be no more than a threshold t). We choose to use the earth mover distance measure for our t-closeness requirement. We discuss the rationale for t-closeness and illustrate its advantages through examples and experiments. <s> BIB006 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Privacy Model for Attacks <s> Advances in information technology, and its use in research, are increasing both the need for anonymized data and the risks of poor anonymization. We present a metric, δ-presence, that clearly links the quality of anonymization to the risk posed by inadequate anonymization. We show that existing anonymization techniques are inappropriate for situations where δ-presence is a good metric (specifically, where knowing an individual is in the database poses a privacy risk), and present algorithms for effectively anonymizing to meet δ-presence. The algorithms are evaluated in the context of a real-world scenario, demonstrating practical applicability of the approach. <s> BIB007 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Privacy Model for Attacks <s> We consider the privacy problem in data publishing: given a database instance containing sensitive information "anonymize" it to obtain a view such that, on one hand attackers cannot learn any sensitive information from the view, and on the other hand legitimate users can use it to compute useful statistics. These are conflicting goals. In this paper we prove an almost crisp separation of the case when a useful anonymization algorithm is possible from when it is not, based on the attacker's prior knowledge. Our definition of privacy is derived from existing literature and relates the attacker's prior belief for a given tuple t, with the posterior belief for the same tuple. Our definition of utility is based on the error bound on the estimates of counting queries. The main result has two parts. First we show that if the prior beliefs for some tuples are large then there exists no useful anonymization algorithm. Second, we show that when the prior is bounded for all tuples then there exists an anonymization algorithm that is both private and useful. The anonymization algorithm that forms our positive result is novel, and improves the privacy/utility tradeoff of previously known algorithms with privacy/utility guarantees such as FRAPP. <s> BIB008 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Privacy Model for Attacks <s> In this paper we demonstrate that, ignoring computational constraints, it is possible to privately release synthetic databases that are useful for large classes of queries -- much larger in size than the database itself. Specifically, we give a mechanism that privately releases synthetic data for a class of queries over a discrete domain with error that grows as a function of the size of the smallest net approximately representing the answers to that class of queries. We show that this in particular implies a mechanism for counting queries that gives error guarantees that grow only with the VC-dimension of the class of queries, which itself grows only logarithmically with the size of the query class. ::: We also show that it is not possible to privately release even simple classes of queries (such as intervals and their generalizations) over continuous domains. Despite this, we give a privacy-preserving polynomial time algorithm that releases information useful for all halfspace queries, given a slight relaxation of the utility guarantee. This algorithm does not release synthetic data, but instead another data structure capable of representing an answer for each query. We also give an efficient algorithm for releasing synthetic data for the class of interval queries and axis-aligned rectangles of constant dimension. ::: Finally, inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than the prevailing privacy notion, differential privacy. <s> BIB009 </s> A Survey of Privacy Preserving Data Publishing using Generalization and Suppression <s> Privacy Model for Attacks <s> Public opinion is the belief or thoughts of the public regarding a particular topic, especially one regarding politics, religion or social issues. Opinions may be sensitive since they may reflect a person's perspective, understanding, particular feelings, way of life, and desires. On one hand, public opinion is often collected through a central server which keeps a user profile for each participant and needs to publish this data for research purposes. On the other hand, such publishing of sensitive information without proper de-identification puts individuals' privacy at risk, thus opinions must be anonymized prior to publishing. While many anonymization approaches for tabular data with single sensitive attribute have been introduced, the proposed approaches do not readily apply to opinion polls. This is because opinions are generally collected on many issues, thus opinion databases have multiple sensitive attributes. Finding and enforcing anonymization models that work on datasets with multiple sensitive attributes while allowing risk analysis on the publisher side is not a well-studied problem. In this work, we identify the privacy problems regarding public opinions and propose a new probabilistic privacy model MSA-diversity, specifically defined on datasets with multiple sensitive attributes. We also present a heuristic anonymization technique to enforce MSA-diversity. Experimental results on real data show that our approach clearly outperforms the existing approaches in terms of anonymization accuracy. <s> BIB010
The linkage attack is that adversary steals sensitive information by the means of linking with released dataset. It has three types of linkage, record linkage, attribute linkage and table linkage. Quasi-identifiers are known by adversary beforehand is the common characteristic of linkage attack. Furthermore, adversary also grasps the basic information of individuals and wants to know their sensitive information under the scenarios of record linkage and attribute linkage. While, table linkage attack puts more emphasizes on the point that whether known individual's information presents in released dataset. The privacy model of record linkage will be elaborately described in the next section, which is the important part of this paper. For the attack of attribute linkage, the adversary could infer sensitive information from the released dataset based on the distribution of sensitive value in the group that the individual belongs to. A successful inference is possible working on the published dataset that satisfies the qualifications of k-anonymity. The common effective solution for the attribute linkage attack is to lessen the correlation of quasi-identifiers and sensitive attributes of original dataset. Certainly, others models also bloom recently for capturing this kind of attack, like ℓ-diversity BIB010 and recursive (c, ℓ)-diversity  , (X, Y)-Anonymity BIB002 , (a, k)-Anonymity BIB003 , (k, e)-Anonymity BIB005 , t-closeness by Li et al. BIB006 , personalized privacy by Xiao and Tao  and so on. BIB007 . The probabilistic attack can be depicted in the scenarios that adversary will not immediately scratch sensitive information from released dataset, while, the released dataset can do some favor for adversary through increasing his/her background knowledge to some extent. This kind of attack is called probabilistic attack that it turns up a visible deviation for gaining sensitive information after accessing the released dataset. Probabilistic attack is not like linkage attack which precisely knows individual information, then gain sensitive information combined with existed background knowledge, but it focuses on changing adversary's probabilistic confidence of getting privacy information after acquiring published dataset. The privacy model to this attack needs to ensure that the change of probabilistic confidence is relatively small after obtaining the published dataset. Some insightful notions for probabilistic attack are (c, t)-isolation BIB001 , ε-differential privacy BIB004 , (d, γ)-privacy BIB008 , distributional privacy BIB009 and so on. Different privacy preserving model has its unique features determined by details of the vicious attack, so related algorithms which belong to a specific privacy model are customized and targeted at settling particular attack situation.