A Survey on Interdependent Privacy <s> Aggregate Data and Differential Privacy <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> BIB001 </s> A Survey on Interdependent Privacy <s> Aggregate Data and Differential Privacy <s> Differential privacy is a powerful tool for providing privacy-preserving noisy query answers over statistical databases. It guarantees that the distribution of noisy query answers changes very little with the addition or deletion of any tuple. It is frequently accompanied by popularized claims that it provides privacy without any assumptions about the data and that it protects against attackers who know all but one record. In this paper we critically analyze the privacy protections offered by differential privacy. First, we use a no-free-lunch theorem, which defines non-privacy as a game, to argue that it is not possible to provide privacy and utility without making assumptions about how the data are generated. Then we explain where assumptions are needed. We argue that privacy of an individual is preserved when it is possible to limit the inference of an attacker about the participation of the individual in the data generating process. This is different from limiting the inference about the presence of a tuple (for example, Bob's participation in a social network may cause edges to form between pairs of his friends, so that it affects more than just the tuple labeled as "Bob"). The definition of evidence of participation, in turn, depends on how the data are generated -- this is how assumptions enter the picture. We explain these ideas using examples from social network research as well as tabular data for which deterministic statistics have been previously released. In both cases the notion of participation varies, the use of differential privacy can lead to privacy breaches, and differential privacy does not always adequately limit inference about participation. <s> BIB002
The correlation between the data of different individuals raises issues not only for individual data (usually through inference attacks as described in the previous subsections) but also for aggregate data. In this setting, the now well-established approach for guaranteeing individual data contributors' privacy is to add some noise on the released aggregrate data to achieve differential privacy (DP) BIB001 ]. This definition guarantees that the distribution of any aggregate query result changes only slightly when a single record in the dataset is added/removed. However, for guaranteeing a certain privacy level, DP assumes that the different records in the considered dataset are statistically independent. Kifer and Machanavajjhala are the first to demonstrate, based on illustrative examples and synthetic data, that correlated records in a dataset can void the guarantees provided by DP BIB002 . Liu et al. further demonstrate, based on real data, such correlation can be exploited through inference attacks and therefore jeopardize the DP guarantees . Specifically, they rely on a dataset from Gowalla, composed of ∼100k check-ins from ∼7k users with ∼47.5k edges between them. The considered setting is that of a data provider that releases the centroids of clusters μ (computed with k-means from the users' check-in locations) in a differentially private manner by applying Laplace noise on the original centroids. The adversary is assumed (i) to have access to all but the target user's data (a generic assumption in differential privacy), and (ii) to know the joint distribution between the data records in the dataset. The second assumption makes the adversary more powerful than the traditional DP adversary but also more realistic when data records happen to be correlated (such as in OSNs). The authors first show that the adversary's posterior on the estimated value of the target recordD i is as follows: where exp(−|μ −μ|ϵ ) is the noise induced by the Laplace distribution applied on the centroids. Under the original DP adversary, P (D i =d i |D −i ) = P (D i =d i ), which limits the power of the adversary to infer the posterior ofD i . In this case, D −i can only be used to estimate the prior probability P (D i =d i ). These records can indeed be used to sample D i , typically by counting the number of check-ins falling into a given region. Now, if the adversary not only knows location records D −i but also some dependencies between D i and these (e.g., through social relationships of users), then P (D i =d i |D −i ) can be better estimated by assigning higher weights to the check-ins whose owners are friends with the target (due to the fact that mobility patterns between are often correlated). Finally, the authors show that inference attack achieve better performance when accounting for dependencies and that the theoretical maximum information leakage guaranteed by DP is violated under a more realistic adversary who exploit correlation between records.