Contractual Date of Delivery to the CEC: 1-Apr-2013 Actual Date of Delivery to the CEC: 20-Mar-2013 Organisation name of lead contractor for this deliverable: INR

The concept of differential privacy emerged as an approach to protect the privacy of the individuals participating in statistical databases. Roughly, a mechanism satisfies differential privacy if the presence or value of a single individual in a database does not change significantly the likelihood of obtaining a certain answer to any statistical query posed by the data analyst. Differentially-private mechanisms are often oblivious: first the query is processed on the database to produce the true answer, and then this answer is adequately randomized before being reported to the data analyst. Ideally the mechanism should minimize leakage, i.e., obfuscate as much as possible the link between the reported answer and the individuals ’ data. At the same time, it should maximize utility, i.e., the reported answer should be as close as possible to the true one. These two goals are, however, conflicting, and a trade-off between privacy and utility is imposed. In this paper we use quantitative information flow to analyze the leakage and the utility of oblivious differentially-private mechanisms. We introduce a technique that exploits some graph-symmetries presented by the adjacency relation on databases to derive bounds on the leakage of the mechanism, measured as min-entropy leakage. We use identity gain functions, which are closely related to min-entropy leakage, to evaluate utility, and therefore we are also able to derive bounds for it. Depending on the graph-symmetries we consider, we can additionally build a mechanism that maximizes utility while preserving the required level of differential privacy