This paper investigates the relation between three different notions of privacy: identifiability, differential privacy and mutual-information privacy. Under a unified privacy-distortion framework, where the distortion is defined to be the Hamming distance of the input and output databases, we establish some fundamental connections between these three privacy notions. Given a distortion level @math , define @math to be the smallest (best) identifiability level, and @math to be the smallest differential privacy level. We characterize @math and @math , and prove that @math for @math in some range, where @math is a constant depending on the distribution of the original database @math , and diminishes to zero when the distribution of @math is uniform. Furthermore, we show that identifiability and mutual-information privacy are consistent in the sense that given distortion level @math , the mechanism that optimizes the mutual-information privacy also minimizes the identifiability level.
 There is growing interest in quantitative theories of information flow in a variety of contexts, such as secure information flow, anonymity protocols, and side-channel analysis. Such theories offer an attractive way to relax the standard noninterference properties, letting us tolerate "small" leaks that are necessary in practice. The emerging consensus is that quantitative information flow should be founded on the concepts of Shannon entropy and mutual information . But a useful theory of quantitative information flow must provide appropriate security guarantees: if the theory says that an attack leaks x bits of secret information, then x should be useful in calculating bounds on the resulting threat. In this paper, we focus on the threat that an attack will allow the secret to be guessed correctly in one try. With respect to this threat model, we argue that the consensus definitions actually fail to give good security guarantees--the problem is that a random variable can have arbitrarily large Shannon entropy even if it is highly vulnerable to being guessed. We then explore an alternative foundation based on a concept of vulnerability (closely related to Bayes risk ) and which measures uncertainty using Renyi's min-entropy , rather than Shannon entropy. We propose a framework in which anonymity protocols are interpreted as particular kinds of channels, and the degree of anonymity provided by the protocol as the converse of the channel's capacity. We also investigate how the adversary can test the system to try to infer the user's identity, and we study how his probability of success depends on the characteristics of the channel. We then illustrate how various notions of anonymity can be expressed in this framework, and show the relation with some definitions of probabilistic anonymity in literature.  We propose a general statistical inference framework to capture the privacy threat incurred by a user that releases data to a passive but curious adversary, given utility constraints. We show that applying this general framework to the setting where the adversary uses the self-information cost function naturally leads to a non-asymptotic information-theoretic approach for characterizing the best achievable privacy subject to utility constraints. Based on these results we introduce two privacy metrics, namely average information leakage and maximum information leakage. We prove that under both metrics the resulting design problem of finding the optimal mapping from the user's data to a privacy-preserving output can be cast as a modified rate-distortion problem which, in turn, can be formulated as a convex program. Finally, we compare our framework with differential privacy. We focus on the privacy-accuracy tradeoff encountered by a user who wishes to release some data to an analyst, that is correlated with his private data, in the hope of receiving some utility. We rely on a general statistical inference framework, under which data is distorted before its release, according to a probabilistic privacy mechanism designed under utility constraints. Using recent results on maximal correlation and hyper-contractivity of Markov processes, we first propose novel techniques to design utility-aware privacy mechanisms against inference attacks, when only partial statistical knowledge of the prior distribution linking private data and data to be released is available. We then propose optimal privacy mechanisms in the class of additive noise mechanisms, for both continuous and discrete released data, whose design requires only knowledge of second-order moments of the data to be released. We then turn our attention to multi-agent systems, where multiple data releases occur, and use tensorization results of maximal correlation to analyze how privacy guarantees compose after collusion or composition. Finally, we show the relationship between different existing privacy metrics, in particular divergence privacy, and differential privacy. Information theory provides a range of useful methods to analyse probability distributions and these techniques have been successfully applied to measure information flow and the loss of anonymity in secure systems. However, previous work has tended to assume that the exact probabilities of every action are known, or that the system is non-deterministic. In this paper, we show that measures of information leakage based on mutual information and capacity can be calculated, automatically, from trial runs of a system alone. We find a confidence interval for this estimate based on the number of possible inputs, observations and samples. We have developed a tool to automatically perform this analysis and we demonstrate our method by analysing a Mixminon anonymous remailer node.   Measures for anonymity in systems must be on one hand simple and concise, and on the other hand reflect the realities of real systems. Such systems are heterogeneous, as are the ways they are used, the deployed anonymity measures, and finally the possible attack methods. Implementation quality and topologies of the anonymity measures must be considered as well. We therefore propose a new measure for the anonymity degree, which takes into account possible heterogeneity. We model the effectiveness of single mixes or of mix networks in terms of information leakage and measure it in terms of covert channel capacity. The relationship between the anonymity degree and information leakage is described, and an example is shown