A Survey on Interdependent Privacy <s> PRIVACY RISKS AND CONCERNS <s> Consider a data holder, such as a hospital or a bank, that has a privately held collection of person-specific, field structured data. Suppose the data holder wants to share a version of the data with researchers. How can a data holder release a version of its private data with scientific guarantees that the individuals who are the subjects of the data cannot be re-identified while the data remain practically useful? The solution provided in this paper includes a formal protection model named k-anonymity and a set of accompanying policies for deployment. A release provides k-anonymity protection if the information for each person contained in the release cannot be distinguished from at least k-1 individuals whose information also appears in the release. This paper also examines re-identification attacks that can be realized on releases that adhere to k- anonymity unless accompanying policies are respected. The k-anonymity protection model is important because it forms the basis on which the real-world systems known as Datafly, µ-Argus and k-Similar provide guarantees of privacy protection. <s> BIB001 </s> A Survey on Interdependent Privacy <s> PRIVACY RISKS AND CONCERNS <s> We continue a line of research initiated in [10, 11] on privacy-preserving statistical databases. Consider a trusted server that holds a database of sensitive information. Given a query function f mapping databases to reals, the so-called true answer is the result of applying f to the database. To protect privacy, the true answer is perturbed by the addition of random noise generated according to a carefully chosen distribution, and this response, the true answer plus noise, is returned to the user. Previous work focused on the case of noisy sums, in which f = Σ i g(x i ), where x i denotes the ith row of the database and g maps database rows to [0,1]. We extend the study to general functions f, proving that privacy can be preserved by calibrating the standard deviation of the noise according to the sensitivity of the function f. Roughly speaking, this is the amount that any single argument to f can change its output. The new analysis shows that for several particular applications substantially less noise is needed than was previously understood to be the case. The first step is a very clean characterization of privacy in terms of indistinguishability of transcripts. Additionally, we obtain separation results showing the increased value of interactive sanitization mechanisms over non-interactive. <s> BIB002 </s> A Survey on Interdependent Privacy <s> PRIVACY RISKS AND CONCERNS <s> Publishing data about individuals without revealing sensitive information about them is an important problem. In recent years, a new definition of privacy called k-anonymity has gained popularity. In a k-anonymized dataset, each record is indistinguishable from at least k − 1 other records with respect to certain identifying attributes. In this article, we show using two simple attacks that a k-anonymized dataset has some subtle but severe privacy problems. First, an attacker can discover the values of sensitive attributes when there is little diversity in those sensitive attributes. This is a known problem. Second, attackers often have background knowledge, and we show that k-anonymity does not guarantee privacy against attackers using background knowledge. We give a detailed analysis of these two attacks, and we propose a novel and powerful privacy criterion called e-diversity that can defend against such attacks. In addition to building a formal foundation for e-diversity, we show in an experimental evaluation that e-diversity is practical and can be implemented efficiently. <s> BIB003 </s> A Survey on Interdependent Privacy <s> PRIVACY RISKS AND CONCERNS <s> The goal of privacy metrics is to measure the degree of privacy enjoyed by users in a system and the amount of protection offered by privacy-enhancing technologies. In this way, privacy metrics contribute to improving user privacy in the digital world. The diversity and complexity of privacy metrics in the literature make an informed choice of metrics challenging. As a result, instead of using existing metrics, new metrics are proposed frequently, and privacy studies are often incomparable. In this survey, we alleviate these problems by structuring the landscape of privacy metrics. To this end, we explain and discuss a selection of over 80 privacy metrics and introduce categorizations based on the aspect of privacy they measure, their required inputs, and the type of data that needs protection. In addition, we present a method on how to choose privacy metrics based on nine questions that help identify the right privacy metrics for a given scenario, and highlight topics where additional work on privacy metrics is needed. Our survey spans multiple privacy domains and can be understood as a general framework for privacy measurement. <s> BIB004
In this section, we survey the concrete interdependent privacy risks (i.e., situations where the actions of some individuals affect the privacy of others) studied in the literature. In most of the considered risks, "actions" refer to information disclosure, typically on online platforms. The root cause of such risks is either that the data disclosed directly features multiple individuals or that the private attributes of different individuals, hence the data associated with them, are often times correlated, especially when these individuals are somehow related (e.g., friends, family members). 10 Two typical sources of correlation are (1) homophily for friends (the fact that individuals tend to befriend with individuals with whom they share similarities) and (2) genetic inheritance (the fact that individuals inherit their genetic material from both their parents). Correlation often indicates a predictive relationship between the private attributes of individuals; these relationships can be exploited, by an adversary, at the expense of these individuals' privacy. Indeed, by considering the statistical properties of the relationship between the data of different individuals, the unknown private attributes of an individual can be inferred, or, more generally, the knowledge about them can be refined, algorithmically from the data disclosed by other individuals. Beyond correlation, interdependent privacy risks can also arise when individuals disclose, intentionally or not, to third parties the information related to another individual, which they were trusted with in the first place. Privacy leakage is related to the increase in the knowledge acquired by the adversary from the disclosed data, possibly through inference. In interdependent privacy situations, the leakage comes also from other individuals. It is important to note that interdependent privacy refers to a class of situations, not to a specific privacy metric; in fact, standard metrics for quantifying/defining privacy are used to quantify interdependent privacy risks. These include k-anonymity BIB001 (and its refinements, e.g., l-diversity BIB003 ]) w.r.t. certain pseudo identifiers and private attributes of the target individuals, differential privacy BIB002 ] w.r.t. certain private attributes and queries, and uncertainty (usually captured by Shannon's entropy) and incorrectness (usually captured by the distance between the ground truth and the inferred value, i.e., the expected error) w.r.t. certain private attributes. In other words, because of the actions/data of other individuals, an individual's privacy might be decreased, which would result in a decrease of k (for k-anonymity), an increase of ϵ (for ϵ-differential privacy), 11 or a decrease in entropy/expected error. Such metrics, however, are not specific to interdependent privacy; Wagner and Eckhoff wrote a comprehensive survey on privacy metrics including for social network, genomic and location data BIB004 . They conclude from their survey that multiple metrics are often needed to cover multiple aspects of privacy, and they propose a series of nine questions to guide the selection of appropriate metrics for a given scenario. Furthermore, in the supplementary materials, they briefly cover interdependent privacy and mention that existing privacy metrics can be relied upon to quantify the privacy effect of interdependence. Most works presented in this section rely on uncertainty and incorrectness for quantifying privacy. We structure this section according to the types of data involved in the different risks surveyed. For each data type, we first describe the context and give the necessary background, before we present the different risks associated with the considered data type. A typical risk consists in inferring (or refining knowledge on) certain private attributes of an individual, based on the data disclosed by other individuals, assuming that the adversary has information about the relationship between individuals. 12 We present, for some data types, studies on the associated user privacy concerns. We summarize the results of this section in a synthetic table presented at the end of this section ( Table 2 , on page 23).