Mário S Alvim
email: msalvim@dcc.ufmg.br

Miguel E Andrés

Konstantinos Chatzikokolakis

Pierpaolo Degano

Catuscia Palamidessi

On the information leakage of differentially-private mechanisms

Keywords: Differential privacy, information flow, min-entropy leakage, gain functions, optimal mechanisms

Differential privacy aims at protecting the privacy of participants in statistical databases. Roughly, a mechanism satisfies differential privacy if the presence or value of a single individual in the database does not significantly change the likelihood of obtaining a certain answer to any statistical query posed by a data analyst. Differentially-private mechanisms are often oblivious: first the query is processed on the database to produce a true answer, and then this answer is adequately randomized before being reported to the data analyst. Ideally, a mechanism should minimize leakage-i.e., obfuscate as much as possible the link between reported answers and individuals' data-while maximizing utility-i.e., report answers as similar as possible to the true ones. These two goals, however, are in conflict with each other, thus imposing a trade-off between privacy and utility.

In this paper we use quantitative information flow principles to analyze leakage and utility in oblivious differentially-private mechanisms. We introduce a technique that exploits graph symmetries of the adjacency relation on databases to derive bounds on the min-entropy leakage of the mechanism. We consider a notion of utility based on identity gain functions, which is closely related to min-entropy leakage, and we derive bounds for it. Finally, given some graph symmetries, we provide a mechanism that maximizes utility while preserving the required level of differential privacy.

Introduction

Statistical databases store data of a large number of individuals, and data analysts are allowed to pose statistical queries about these data. Typical such queries include average values, total counting, or the percentage of the entries that satisfy a given property. Statistical databases are of crucial importance in many areas. For instance, medical databases can guide pharmacological research, and census databases can help authorities decide how to spend the budget of years to come. The field of statistical disclosure control concerns the problem of revealing accurate statistics about a set of individuals while preserving their privacy.

In principle we would like to consider aggregate information as public, and specific information about any individual as private. However, since the two kinds of information are intrinsically linked, it is not easy to make available the former without revealing the latter. Consider, for example, a database that stores the values of the salaries of a set of individuals, and consider the queries "what is the average salary of the people in the database?" and "how many people are in the database?". Both queries are about aggregate information, but by posing them immediately before and after the addition of a new individual to the database, the data analyst can infer exactly the salary of this individual.

Another important issue is the presence of side information, which is any information about individuals coming from sources external to the database itself (e.g., from prior beliefs, public sources, newspapers, or other databases). The combination of statistical queries and suitable side information can pose serious threats to the privacy of individuals [START_REF] Dwork | Differential privacy[END_REF]. 1To tackle the problem of statistical disclosure control, Dwork has proposed the notion of differential privacy [START_REF] Dwork | Differential privacy[END_REF][START_REF] Dwork | Differential privacy in new settings[END_REF][START_REF] Dwork | A firm foundation for private data analysis[END_REF][START_REF] Dwork | Differential privacy and robust statistics[END_REF], which has received great attention in the privacy community. Essentially, differential privacy ensures that the presence or absence of any individual in a database, or changing the data of any individual, does not significantly affect the probability of obtaining any specific answer for a certain query. Intuitively, this implies that it is "safe" for an individual to opt in (or out) a database, since their choice will not significantly affect the information the data analyst will obtain. An important feature of differential privacy is that it does not depend on side information.

There are several approaches in the literature to implement differentially-private mechanisms. For numeric queries, Dwork has proposed the simple method of adding Laplacian noise to the true answer to the query [START_REF] Dwork | Differential privacy[END_REF]. More sophisticated mechanisms correlate noise between queries, enabling more information to be extracted from the database while still preserving differential privacy [START_REF] Blum | A learning theory approach to non-interactive database privacy[END_REF][START_REF] Roth | Interactive privacy via the median mechanism[END_REF][START_REF] Hardt | A multiplicative weights mechanism for privacy-preserving data analysis[END_REF]. For cases in which perturbing the answer is not an adequate option (e.g. for non-numeric queries), McSherry and Talwar have proposed the exponential mechanism [START_REF] Mcsherry | Mechanism design via differential privacy[END_REF].

Differential privacy relies on the randomization of the query answer, and thus imposes a trade-off in fulfilling two opposing goals. On one hand, privacy demands the minimization of the amount of information about the database (and, in particular, about individuals) revealed through the randomized answers. On the other hand, the mechanism should provide good utility, i.e., some adequate closeness between true and randomized answers.

In this paper we investigate the quantification of privacy and utility in differentially-private mechanisms, approaching the problem from the perspective of the well-established field of quantitative information flow.

Quantitative information flow. Completely secure systems are often impossible to obtain in practice, either by design or by technological constraints, and thus it is important to quantitatively analyze the leakage of such systems. The field of quantitative information flow is concerned with the amount of secret information one can infer from the observable behavior of an execution of a system.

Information theory is widely regarded as a natural framework to provide firm foundations to quantitative information flow. A system can be seen as an information-theoretic channel from secret inputs to observable outputs. The input has some uncertainty representing how easily an adversary can discover the secret. Uncertainty is evaluated through entropy measures, which vary according to the model of adversary and to the way one estimates the success of an attack [START_REF] Köpf | An information-theoretic model for adaptive side-channel attacks[END_REF]. One of the main notions of entropy in quantitative information flow is min-entropy [START_REF] Smith | On the foundations of quantitative information flow[END_REF][START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF][START_REF] Smith | Quantifying information flow using min-entropy[END_REF], which is closely related to the risk of an adversary guessing the secret correctly in one try.

Independently of the adopted model of adversary and attack, a general principle of quantitative information flow is that leakage can be expressed as the difference between the initial uncertainty about the secret before the system is executed, and the remaining uncertainty after the execution is observed: information leakage = initial uncertaintyremaining uncertainty.

The observation of the execution is expected to increase the probabilistic knowledge about the secret, therefore decreasing the corresponding uncertainty and making the equation above non-negative.

Quantitative information flow vs. differential privacy. Both quantitative information flow and differential privacy measure the protection of sensitive information provided by a mechanism, and in both cases this measure is linked to the probabilistic knowledge that an adversary gains about the secret from the outcome of the mechanism. It is therefore natural to ask how they compare, and whether one is preferable to the other. In our opinion, there is no absolute criterion to prefer one to the other: it depends on the context in which we want to use a privacy mechanism. One main difference between the two notions is that quantitative information flow is an average measure, defined in terms of the expected value of the probability of a successful attack with respect to all possible outcomes, while differential privacy is concerned with the worst-case, no matter how improbable it may be. Thus differential privacy reflects the perspective of an individual, for whom the consequences of a privacy breach may be dramatic, while quantitative information flow could be more suitable for companies, as they can usually amortize the costs of single incidents, and are more interested in optimizing the trade-off between average costs rather than avoiding all risks.

Another important difference between quantitative information flow and privacy is that the latter has a nice compositionality property: the combination of an ǫ 1 -differentially private and an ǫ 2 -differentially private mechanism gives an (ǫ 1 + ǫ 2 )-differentially private mechanism. Hence the degradation of privacy under composition is controllable. In quantitative information flow there has been some work on the cascading of channels [START_REF] Espinoza | Min-entropy leakage of channels in cascade[END_REF], which however is a rather specific form of composition, and rather different from the one of differential privacy. More general kinds of composition have been analyzed in [START_REF] Kawamoto | Compositionality Results for Quantitative Information Flow[END_REF] (including the one of differential privacy, under the name of "parallel composition with repeated input"), and in the context of a process calculus [START_REF] Braun | Compositional methods for informationhiding[END_REF], but a neat compositionality result like the one of differential privacy has not been produced.

Contributions. This work investigates connections between differential privacy and quantitative information flow. We note that differentially-private mechanisms can be seen as information-theoretic channels from databases to reported answers, and we describe-and quantify-the level of privacy and utility of such mechanisms in terms of entropy min-entropy and leakage. We are motivated by the following fundamental questions.

To address those questions, we exploit the graph structure of the database domain to derive bounds on leakage, and, similarly, the graph structure that a query induces on the domain of true answers to derive bounds on utility. The main contributions of this paper are the following.

-We propose an information-theoretic framework to reason about information leakage and utility in differentially-private querying mechanisms. -We explore graph-theoretic properties of the adjacency relation on databases, using two types of symmetries (distance-regularity and vertex-transitivity) that enable us to prove that differential privacy induces a bound on min-entropy leakage. -Furthermore, we prove that this bound is tight, i.e., that there always exists a differentially-private mechanism that attains this bound. -We prove that if the graph structure of the answers satisfies our symmetry conditions, then differential privacy induces a bound on utility, measured in terms of identity gain functions. We also prove that this bound is tight. -As a side result, we prove that under the considered symmetry conditions the exponential mechanism is optimal, i.e., it provides maximum utility for a given degree of privacy.

Finally, we show that the opposite direction of the relation between quantitative information flow and differential privacy is not possible to establish in general. More precisely, a bound on the min-entropy leakage of a channel does not necessarily imply a bound on the level of differential privacy of the channel (i.e., on the parameter ǫ).

The remainder of this paper is organized as follows. In Section 2 we review basic concepts of information theory, quantitative information flow, differential privacy, and graph theory. In Section 3 we introduce a model for leakage and utility in oblivious differentially-private mechanisms. In Section 4 we exploit graph-symmetries (distance-regularity or vertex-transitivity) of the adjacency relation on the input to a channel to derive bounds on the a posterior min-entropy of that channel. We then apply this bound to differentially-private mechanisms to derive our results for leakage in Section 5 and for utility in Section 6. Finally, in Section 7 we discuss related work, and in Section 8 we conclude. Full proofs for all our results can be found in Appendix 8.

A preliminary version of some of the results of this paper appeared in [START_REF] Mário | Differential Privacy: on the Trade-Off between Utility and Information Leakage[END_REF] and [START_REF] Mário | On the relation between Differential Privacy and Quantitative Information Flow[END_REF].

Preliminaries

The information-theoretic framework for quantitative information flow

Let A, B denote two discrete random variables with carriers A = {a 0 , . . . , a n-1 }, B = {b 0 , . . . , b m-1 }, and let π denote a probability distribution on A, called a prior distribution.

An (information-theoretic) channel is a triple (A, B, M ), where A is the channel input, B is the channel output, and M is a channel matrix of conditional probabilities. Each element M a,b represents the probability that B takes value b given that A has value a. Together, π and M induce a joint probability distribution p for A, B, defined as p(a, b) = π a M a,b . Note that p satisfies p(a) = π a and, for values of π(a) > 0, p(b|a) = M a,b .

There are several measures of the information shared by A and B via the channel matrix. In this paper we will concentrate on the measures of vulnerability and min-entropy.

The vulnerability of A is defined as V (A) = max a∈A p(a), and it represents the probability that an adversary can correctly guess the value of A in a single try (a rational adversary chooses as a guess a value of a with maximum probability). Correspondingly, the conditional vulnerability of A given B is defined as V (A|B) = b∈B p(b)V (A|B = b) = b∈B max a∈A p(a)p(b|a), and it is the probability that the adversary can correctly guess the value of A in one try after having observed the value of B. It can be shown that V (A|B) /V (A) ≥ 1, and intuitively this ratio represents by how much the adversary's probability of success is increased by the observation of the channel output.

For mathematical convenience, the vulnerability is usually converted into bits by taking its negative logarithm (in base 2). The min-entropy of A is then defined as H ∞ (A) =log V (A), and the conditional min-entropy of A given B is defined as H ∞ (A|B) =log V (A|B).

The min-entropy leakage (or simply min-leakage) of A to B is defined as the difference between the a priori (i.e., before observing the value of B) and the a posteriori (i.e., after observing the value of B) min-entropies of A:

I ∞ (A; B) = H ∞ (A) -H ∞ (A|B) = log V (A|B) /V (A). It can be shown that 0 ≤ I ∞ (A; B) ≤ H ∞ (A)
, and that min-entropy leakage is not symmetric, i.e., that

I ∞ (A; B) = I ∞ (B; A) in general.
Min-capacity is the worst-case leakage over all input distributions: C ∞ = max π I ∞ (A; B). It has been proven in [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF] that C ∞ is realized at the uniform distribution, and that it equals the logarithm of the sum of the maxima of each column in the channel matrix, i.e., C ∞ = log b ∈ B max a ∈ A p(b|a).

Differential Privacy

Let X be the set of all possible databases. Two databases x, x ′ ∈ X are adjacent (or neighbors), written x ∼ x ′ , if they differ for the presence or the value of exactly one individual. We call ∼ the adjacency relation on databases. Note that the structure (X , ∼) forms an undirected graph, where vertices are databases and edges connect every two adjacent databases.

A (differentially-private) mechanism is a probabilistic function K from X to some set of possible answers Z, satisfying the property that the ratio between the probabilities of two adjacent databases to give a certain answer is bounded by e ǫ , for some ǫ ≥ 0.

Definition 1 ([14]

). A mechanism K from X to Z satisfies ǫ-differential privacy, for some ǫ ≥ 0, if for all pairs x, x ′ ∈ X , with x ∼ x ′ , and all S ⊆ Z:

Pr [K(x) ∈ S] ≤ e ǫ • Pr[K(x ′ ) ∈ S]. (1)
Since in this work we consider finite X , Z, all probability distributions are discrete, and in the above definition it is sufficient to consider probabilities of the form Pr[K(x) = z].

Intuitively, [START_REF] Mário | Differential Privacy: on the Trade-Off between Utility and Information Leakage[END_REF] means that an isolated individual has a negligible influence on a large database. It is usual to think of ǫ as a constant smaller than 1, so e ǫ ≈ (1 + ǫ), and differential privacy ensures a small multiplicative difference in the distributions generated by neighbor databases.

Graph theory

Let G = (V, ∼) be a (undirected) graph with vertices in V and edges ∼ ⊆ V × V. We use the infix notation to denote that two elements w and w ′ of V are connected by an edge, i.e., w ∼ w ′ stands for (w, w ′ ) ∈ ∼. We also say, in this case, that w and w ′ are adjacent or neighbors. The distance d(w, w ′ ) between two connected vertices w, w ′ ∈ V is the number of edges in a shortest path connecting them. We denote by V d (w) the subset of vertices in V that are at distance d from the vertex w. The diameter d max (G) of G is the maximum distance between any two connected vertices in V, i.e., d max (G) = max w,w ′ ∈V d(w, w ′ ). We denote by ∆ G the set {0, 1, . . . , d max }. When no confusion can arise, we use d max and ∆ instead of d max (G) and ∆ G , respectively. The degree of a vertex is the number of edges incident to it. G is called regular if every vertex has the same degree, and k-regular if all vertices have degree k. An automorphism of G is a permutation σ on the vertex set V such that for any pair of vertices w, w ′ , if w ∼ w ′ , then σ(w) ∼ σ(w ′ ). The automorphism group of G is the set of all of its automorphisms. We denote by σ k the composition of σ with itself k times, i.e., σ k (w) = σ(σ k-1 (w)) for k > 0, and σ 0 (w) = w.

For the purpose of this paper, we need to consider graphs with certain symmetry properties, namely the so-called distance-regular graphs, and the vertex-transitive graphs.

Definition 2 (Distance-regular graph [START_REF] Brouwer | Distance Regular Graphs[END_REF]). A graph G = (V, ∼) is distance-regular if there exist integers b d and c d (d ∈ {0, . . . , d max }) (called intersection numbers) such that, for all vertices w, w ′ at distance d(w, w ′ ) = d, there are exactly b d neighbors of w ′ in V d+1 (w), and c d neighbors of w ′ in V d-1 (w).

The following proposition gives an alternative characterization of distance-regular graphs: Proposition 3 ([10]). A graph is distance-regular if, and only if, it is regular and, for any two vertices w and w ′ , the cardinality of V j (w) ∩ V k (w ′ ) depends only on j, k, and d(w, w ′ ).

We now define vertex-transitive graphs.

Definition 4 (Vertex-transitive graph). A graph G = (V, ∼) is called vertex-transitive if for any pair w, w ′ ∈ V there exists an automorphism σ such that σ(w) = w ′ .

Many regular graphs are both distance-regular and vertex-transitive. This includes, in particular, the Hamming graphs, which play an important role in this paper since they are the natural structure of databases. A Hamming graph is characterized by two natural numbers, u and v, and it is defined as the graph whose set of nodes are tuples of u elements, where each element can take v different values, and with an adjacency relation defined by stipulating that two tuples are adjacent if they differ in the value of exactly one element. Some examples of graphs that are both distance-regular and vertex-transitive are given in Figure 1. It is possible to show that Figures 1(a) and 1(b) are (isomorphic to) Hamming graphs, with (u, v) equal to [START_REF] Mário | Differential Privacy: on the Trade-Off between Utility and Information Leakage[END_REF][START_REF] Mário | Measuring information leakage using generalized gain functions[END_REF] and (3, 2), respectively.

Distance-regularity and vertex-transitivity, however, are incomparable properties, in the sense that neither of them implies the other. Figure 2(a) shows one of the Chang graphs, which is distance-regular and not vertex-transitive, whereas Figure 2(b) shows the truncated tetrahedron, which is an example of a graph that is vertex-transitive and not distance-regular.

Next, we show that distance-regular and vertex-transitive graphs have the property that, for any given distance d, the cardinality of V d (w) is the same for all vertices w, i.e., it depends only on d and not on w. This property will be relevant for some of the proofs in the paper.

Proposition 5. If a graph G = (V, ∼) is distance-regular or vertex-transitive, then, for every distance d ∈ ∆, there exists a constant n d which is equal to the cardinality of V d (w) for every w ∈ V.

A model of utility and privacy for statistical databases

Let Ind = {0, 1, . . . , u -1} be a finite set of cardinality u representing the individuals participating in the database, and let Val = {val 0 , val 1 , . . . , val v-1 } represent the v different possible values for the A query on the database is a (deterministic) function f : X → Y, where Y is the domain of the true answers y = f (x) to the query. A (noisy) mechanism for f is a probabilistic mapping K : X → Z, where Z represents the domain of the answers reported by the mechanism, and does not necessarily coincide with Y (cf. Figure 3). We model such a mechanism as a channel (X , Z, M ), where X , Z are the channel's inputs and outputs, respectively, and M is the channel matrix. The definition of differential privacy is directly expressed as a property of the channel: M satisfies ǫ-differential privacy if, and only for all x, x ′ ∈ X s.t. x ∼ x ′ , and all z ∈ Z.

X dataset K ǫ-diff.
For the sake of clarity, sometimes we abuse notation slightly and identify a differentially-private mechanism K with its associated matrix M , thus writing K x,z for the conditional probability M x,z , assigned by the channel matrix, that the output is z given that the input is x.

Let Y be a random variable ranging over Y and modeling the true answer to f . The mechanism K is often oblivious, meaning that the reported answer Z only depends on the true answer Y and not on the database X. The channel corresponding to an oblivious mechanism K can thus be decomposed into a channel from X to Y modeling the query f and a noisy channel H from Y to Z modeling the randomization of the true answer. These two channels are said to be in cascade, since the output of the first one is the input for the second one, as depicted in Figure 4.

The leakage of the channel associated to the mechanism is a measure of the information about the database that the adversary can obtain by observing the reported answer, hence it represents a relation between X and Z. On the other hand, the utility of the mechanism is a measure of how much one can learn about the true answer from the reported one, hence it represents a relation between Y and Z. Note that in an oblivious mechanism the utility depends only of the noise channel H.

Following the standard approach in the differential privacy literature [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF][START_REF] Prasad | A note on differential privacy: Defining resistance to arbitrary side information[END_REF], we represent the adversary's side information as a prior distribution on X.

Relating differential privacy and quantitative information flow

In this section we propose a general technique to derive bounds on the min-entropy leakage of ǫdifferentially-private channels. The bounds are derived for any channel whose input respects certain graph regularities. Note that in previous section we have formulated the notion of differential privacy in terms of a generic graph structure on the input, hence we do not need to assume that the inputs are databases. In Section 5 we will instantiate this technique to the channel K associated to the whole mechanism thus obtaining results about leakage, while in Section 6 we will instantiate it to the channel H, thus obtaining results about utility.

More specifically, given a channel respecting ǫ-differential privacy, we show that if the graph structure of the channel input is distance-regular or vertex-transitive, it is possible to transform the channel matrix into a leakage-equivalent matrix with certain structural regularities that immediately allow to derive bounds on the a posteriori min-entropy of the channel.

We emphasize now an important assumption of our analysis, and its implications.

Remark 6. The bounds in this section are obtained under the assumption that the a priori distribution on the channel's input is uniform. This is not a restriction for when applying these bounds to leakage, since maximum min-entropy leakage is achieved on the uniform input distribution (as seen in Section 2) and, hence, any bound for the uniform distribution is also a bound for every other input distribution. In the case of utility the assumption of a uniform input distribution is more restrictive, but we will see that it still provides interesting results for several practical cases.

Assumptions and notation

We start by setting some assumptions and notation.

Channels. We consider channels having input A and output B, with finite carriers A = {a 0 , . . . , a n-1 } and B = {b 0 , . . . , b m-1 }, respectively. The probability distribution of A is assumed to be uniform. Furthermore, we assume that |A| = n ≤ |B| = m. (where | • | represents the cardinality of a set). The latter assumption is without loss of generality, because if n > m we can add to the matrix enough allzero columns (i.e., columns containing only 0's), so as to match the number of rows. Note that adding all-zero columns does not change the min-entropy leakage of the channel.

We assume an adjacency relation ∼ on A, so that the structure (A, ∼) is a (undirected) graph.

For simplicity, we will often (and especially in the proofs) represent the elements of A and B by their indexes, i.e., we will use the natural numbers i, j to denote a i , b j , respectively. We will also write i ∼ h to mean a i ∼ a h , and d(i, h) to denote d(a i , a h ), i.e., the distance between a i and a h in the graph structure.

We use M , M ′ , M ′′ or N to range over channels. Since we represent the elements of A (resp. B) by their indexes, typically the rows and the columns of the channels will be indexed by natural numbers from 0 to n -1 (resp. m -1). We typically use i, h, l to range over rows, and j, k to range over columns. Given a matrix M , we denote by max M j the maximum value of column j over all rows i, i.e., max M j = max i M i,j , and by max M = max i,j M i,j the maximum element of the matrix.

Recall that a channel matrix M satisfies ǫ-differential privacy if, for each column j and for each pair of rows i and h such that i ∼ h, we have

1 e ǫ ≤ M i,j M h,j ≤ e ǫ .
When necessary to avoid confusion, we annotate the a posteriori min-entropy and the min-entropy leakage with the channel M they refer to. I.e., we use the notation H M ∞ (A|B) and I M ∞ (A; B), respectively.

Assumptions on the prior. An important feature of differential privacy is that its definition abstracts from prior information, allowing to show that a mechanism is differentially private without making assumptions on the prior. Nevertheless, prior information still plays an important role on the guarantees that are actually provided: for several natural privacy properties that one might want to enforce (eg. a bound on the adversary's probability of guessing an individual's data), we commonly find that differentially private mechanisms cannot guarantee them unless assumptions are made on the prior. For instance, Kifer and Machanavajjhala [START_REF] Kifer | No free lunch in data privacy[END_REF] argue that the privacy guarantees generally expected from a differentially private mechanism might be violated if the database presents correlations among individual records. Such guarantees depend on an assumption on the prior: the lack of correlations between individuals.

In this paper we study privacy guarantees imposed by differential privacy, expressed in terms of measures from quantitative information flow, in particular conditional min-entropy H ∞ and min-entropy leakage I ∞ . Although both measures depend on the prior, in our results there is a sharp difference between the two: results based on conditional min-entropy, such as Theorem 12, rely on the strong assumption of a uniform prior. This is in accordance to the discussion above: the adversary's probability of guessing the secret (expressed by min-entropy) cannot be bounded without assumptions on the prior. Results based on leakage, on the other hand, such as Theorem 15, make no such assumptions. This somewhat surprising behaviour is due to the way leakage is defined. Prior information might make the secret more vulnerable, but this happens both a priori and a posteriori. Leakage compares the two, measuring how much vulnerability is affected because of the mechanism. As a consequence, min-entropy leakage is maximized on a uniform prior, hence the bounds we provide hold for all priors.

The matrix transformation

Considering a channel matrix M having at least as many columns as rows, and assuming an uniform input distribution, the transformation on the channel matrix is divided into two steps. First, M is converted into a matrix M ′ in which each of the first n columns has a maximum in the diagonal, and the remaining columns are all 0's.

Then, we note that all-zero columns do not contribute to the a posteriori min-entropy leakage of the channel, nor to its min-entropy leakage, and, for simplicity, we erase them from M ′ . The result is a square matrix of dimension n × n.

Second, under the assumption that the input domain is distance-regular or vertex-transitive, M ′ is converted into a matrix M ′′ which has the same maximum leakage, is still ǫ-differentially private, and has all the elements of the diagonal equal to its maximum element max M ′′ .

A scheme of the transformation is shown in Figure 5, where Lemma 7 (Step 1) is the first step of our transformation, and the second is step either Lemma 8 (Step 2a) or Lemma 9 (Step 2b), depending on whether the graph structure is distance-regular or vertex-transitive, respectively. Lemma 7. (Step 1) Let M be a channel matrix of dimensions n × m s.t. n ≤ m, and assume that M satisfies ǫ-differential privacy. Then it is possible to transform M into a matrix M ′ of the same dimensions satisfying the following conditions:

(i) M ′ is a channel matrix: m-1 j=0 M ′ i,j = 1, for all 0 ≤ i ≤ n -1; (ii) each of the first n columns has a maximum in the diagonal: M ′ i,i = max M ′ i , for all 0 ≤ i ≤ n -1; M =      M 0,0 M 0,1 . . . M 0,m-1 M 1,0 M 1,1 . . . M 1,m-1 . . . . . . . . . . . . M n-1,0 M n-1,1 . . . M n-1,m-1     
Step 1: move column maxima to diagonal (any graph structure)

M ′ =      max M ′ 0 - . . . - 0 . . . 0 - max M ′ 1 . . . - 0 . . . 0 . . . . . . . . . . . . . . . . . . . . . - - . . . max M ′ n-1 0 . . . 0     
Erase all-zero columns

M ′ =      max M ′ 0 - . . . - - max M ′ 1 . . . - . . . . . . . . . . . . - - . . . max M ′ n-1     
Step 2a: average column maxima (distance-regular graph)

Step 2b: average column maxima (vertex-transitive graph) (iii) the mn last columns only contain 0's:

M ′′ =      max M ′′ - . . . - - max M ′′ . . . - . . . . . . . . . . . . - - . . . max M ′′     
M ′ i,j = 0, for all 0 ≤ i ≤ n -1 and all n ≤ j ≤ m -1; (iv) M ′ satisfies ǫ-differential privacy: M ′ i,j ≤ e ǫ M ′ h,j , for all 0 ≤ i, h ≤ n -1 s.t. i ∼ h and all 0 ≤ j ≤ m -1; and (v) H M ′ ∞ (A|B) = H M ∞ (A|B), if A has the uniform distribution.
Lemma 8. (Step 2a) Let M ′ be a square channel matrix of dimensions n × n that satisfies ǫ-differential privacy. Let ∼ be an adjacency relation on A such that the graph (A, ∼) is connected and distanceregular. Assume that the maximum value of each column is on the diagonal, i.e., M i,i = max M i for all 0 ≤ i ≤ n -1. Then it is possible to transform M ′ into a matrix M ′′ of the same dimension satisfying the following conditions:

(i) M ′′ is a channel matrix: n-1 j=0 M ′′ i,j = 1, for all 0 ≤ i ≤ n -1;
(ii) the elements of the diagonal are all the same, and are equal to the maximum of the matrix:

M ′′ i,i = max M ′′ , for all 0 ≤ i ≤ n -1; (iii) M ′′ satisfies ǫ-differential privacy: M ′ i,j ≤ e ǫ M ′ h,j , for all 0 ≤ i, h, j ≤ n -1 s.t. i ∼ h; and (iv) H M ′′ ∞ (A|B) = H M ′ ∞ (A|B), if A has the uniform distribution.
Lemma 9. (Step 2b) Consider a square channel matrix M ′ satisfying the assumptions of Lemma 8, except that we assume (A, ∼) to be vertex-transitive instead of distance-regular. Then it is possible to transform M ′ into a matrix M ′′ with the same properties as in Lemma 8.

The bound on the a posteriori entropy of the channel

Once the transformation has been applied, and the channel matrix respects the properties of M ′′ as in Figure 5, we use the graph structure of (A, ∼) to determine a bound on the a posteriori entropy H M ′′ ∞ (A|B). Since the matrix transformation preserves its a posteriori conditional min-entropy, the bound obtained is also valid for the original channel matrix M .

It is a known result in the literature (cfr. [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF]) that when the distribution of A is uniform, the a posteriori min-entropy of a channel M ′′ is given by

H M ′′ ∞ (A|B) = -log 1 n j∈B max M ′′ j . (2)
Given that the diagonal elements of the matrix M ′′ are all equal to the maximum max M ′′ , ( 2) becomes

H M ′′ ∞ (A|B) = -log max M ′′ , (3)
and finding a bound on the a posteriori entropy of the channel M ′′ reduces to finding a bound on max M ′′ . We proceed by noting that ǫ-differential privacy induces a relation between the ratio of elements at any distance (rather than only for neighbor elements at distance 1). Remark 10. Let M be a matrix satisfying ǫ-differential privacy. Then, for any column j, and any pair of rows i and h we have that:

1 e ǫ d(i,h) ≤ M i,j M h,j ≤ e ǫ d(i,h) . (4)
In particular, by taking h = j in (4), and since the elements on the diagonal of M ′′ are equal to the maximum, we obtain that, for each element M ′′ i,j ,

max M ′′ ≤ e ǫ d(i,j) M ′′ i,j . (5)
Intuitively, [START_REF] Barthe | Information-theoretic bounds for differentially private mechanisms[END_REF] means that the value of max M ′′ cannot be increased by arbitrarily grabbing probability mass from other elements in the same line in M ′′ , since ǫ-differential privacy imposes a maximum ratio between any two elements in the same column of the matrix. This observation motivates the next proposition. (Recall that A d (i) is the set of nodes j ∈ A at distance d from i ∈ A, and we use | • | to denote the cardinality of a set. Moreover, ∆ is the set of all possible distances between elements of A.)

Proposition 11. Let M be a channel matrix satisfying ǫ-differential privacy where for every 0 ≤ i ≤ n -1 we have M i,i = max M . Then, for every node i ∈ A,

max M ≤ 1 d∈∆ |A d (i)| e ǫd
, Proposition 11 can be made more precise when the graph structure of the channel input is vertextransitive or distance-regular. By Proposition 5, in such graphs, for every distance d ∈ ∆, the value of |A d (i)| is the same for every element i ∈ A, it and depends only on d. We recall that such value is denoted by n d .

Putting together the steps above, we obtain the main result in this section.

Theorem 12. Consider a channel matrix M satisfying ǫ-differential privacy for some ǫ ≥ 0, assume that the probability distribution on A is uniform, and that (A, ∼) is either distance-regular or vertextransitive. Then

H M ∞ (A|B) ≥ -log 1 d∈∆ n d e ǫ d . (6)
In case the matrix M can be transformed via Lemmata 7, 8, and 9 into a matrix M ′′ whose elements all satisfy (5) with equality, then the bound (6) holds with equality.

Application to leakage

We measure the leakage of a differentially-private mechanism as the the min-entropy leakage of the channel from X (databases) to Z (reported answers) of Figure 4. In this section we show that the graph structure (X , ∼) of the database domain presents the required symmetries (distance-regularity or vertextransitivity) for the matrix transformation from the previous section, so we can instantiate our bound for the posterior min-entropy to the particular channel from X to Z.

As emphasized in Remark 6, min-entropy leakage is maximum when the input distribution is uniform, so the bounds derived in this section (Theorem 15, Proposition 20, and Proposition 21) are valid for all distributions on inputs. Moreover, since we model side information as input distributions, it follows that these bounds are valid for any side information the adversary may have.

Graph symmetries of the database domain

We recall that the graph structure of the database domain (X , ∼) is a Hamming graph. Since Hamming graphs present the symmetries of distance-regularity and vertex-transitivity (cfr. [START_REF] Imrich | Product graphs, structure and recognition[END_REF][START_REF] Brouwer | Distance Regular Graphs[END_REF]), and so does (X , ∼). The relation between graph structures we consider in this paper is summarized in Figure 6.

The bound on leakage

Since the graph structure (X , ∼) of databases is both distance-regular and vertex-transitive, we can apply Theorem 12 to the channel from X to Z. Then, by [START_REF] Barthe | Information-theoretic bounds for differentially private mechanisms[END_REF], it follows that, for j ∈ X d (x) (i.e., every j in X at distance d from a given x), the transformed matrix M ′′ satisfies M ′′ x,j ≥ max M ′′ /e ǫd . Each element j at distance d from x can be obtained by changing the value of d individuals in the utuple representing i. These d individuals can be chosen in u d possible ways, and for each of those we can change the value (with respect to the one in x) in v -1 possible ways. Therefore |X d (x)| = u d (v -1) d , and the number of databases at distance d from any x must be a constant value n d given by

n d = u d (v -1) d . (7)
Using the value of n d from [START_REF] Blum | A learning theory approach to non-interactive database privacy[END_REF] in Theorem 12 we obtain a function Bnd of u, v and ǫ defined as

Bnd (u, v, ǫ) = u log v e ǫ v -1 + e ǫ ,
which is an upper bound for the leakage of the mechanism. Theorem 15. If K satisfies ǫ-differential privacy, then the information leakage is bounded from above as

I ∞ (X; Z) ≤ Bnd (u, v, ǫ).
The bound Bnd (u, v, ǫ) = u log v e ǫ /(v-1+e ǫ ) is a continuous function in ǫ. As expected, this bound has value 0 when ǫ = 0, since in this case all rows of the mechanism are identical, leading to no leakage. Also, the bound converges to u log v as ǫ approaches infinity. Intuitively, this is accordance with the observation that the ratio between two elements in a same column in the matrix could become unbounded, as ǫ approaches infinity. In this case, outputs could uniquely discriminate which input actually caused them, and the posterior entropy of the channel could, in this extreme case, be zero. This would make the leakage of the mechanism coincide with the priori entropy of the input. Since the entropy of the input is maximum when the distribution on all possible v u databases is uniform, the worst-case leakage is bounded by u log v. Figure 8 shows the growth of Bnd (u, v, ǫ) for different configurations of u, v, ǫ.

Choosing an appropriate value of the parameter ǫ in differential privacy is not trivial, and in general one must consider several factors. The information contained in Figure 8 provides some insight into the implications, in terms of vulnerability, of the choice of ǫ in differential privacy. For instance, with u = 100, v = 2, and ǫ = 5, the min-entropy capacity can be a high as 99.03 bits, giving a posterior vulnerability exceeding 1 /2, which intuitively means that this combination of parameters is not safe.

The next proposition shows that the bound obtained is tight.

0 1 1 1 1 2 2 2 2 ab 1 0 1 2 2 1 2 1 2 ac 1 1 0 2 2 2 1 2 1 ba 1 2 2 0 1 1 2 1 2 ca 1 2 2 1 0 2 2 1 1 bb 2 1 2 1 2 0 1 1 2 bc 2 2 1 1 2 1 0 2 1 cb 2 1 2 2 1 1 2 0 1 cc 2 2 1 2 1 2 1 1 0 (b)
The representation of the matrix, where each generic entry α stands for max M /e ǫ α Fig. 9. All possible databases and highest min-entropy leakage matrix giving ǫ-differential privacy for Example 17.

Proposition 16. For every u, v, and ǫ it is possible to define the mechanism K below, which provides ǫ-differential privacy and whose min-entropy leakage, for the uniform input distribution, is

I ∞ (X; Z) = Bnd (u, v, ǫ). K x,z = 2 Bnd(u,v,ǫ) v u (e ǫ ) d
, for every input x and output z.

We now give an example of the use of Bnd (u, v, ǫ) as a bound for min-entropy leakage. In the representation of the matrix, the generic entry α stands for max M /e ǫ α , where max M is the highest value in the matrix, i.e., max

M = 2 Bnd(u,v,ǫ) /v u = ( ve ǫ /v-1+e ǫ ) u • 1 /v u = e 2ǫ /(2+e ǫ ) 2 .

Bounds on leakage do not imply differential privacy

It is important to note that the converse of Theorem 15 does not hold, i.e., a bound on the min-entropy leakage of a channel does not necessarily imply a bound on level of differential privacy of that channel (i.e., on the parameter ǫ). One reason is that the min-entropy is defined as an expected value, i.e., it is the result of averaging the contribution of all the columns to the leakage, while differential privacy represents the worst-case. Hence, there could be a column which breaks differential privacy entirely, for instance in the case in which the column contains both zero and non-zero elements, and whose leakage, yet, does not contribute too much to the average (typically because the corresponding output has very low probability). In this case, the min-entropy leakage can be very small, and yet ǫ-differential privacy does not hold for any ǫ.

Another (related) reason is that min-entropy is sensitive to the values of the input distribution, whereas differential privacy is not. The following example illustrates this point. m-1 for 2 ≤ j ≤ m, and p(y j | x i ) = 1 m otherwise. This channel is represented in Figure 10. Simple calculations show that the min-entropy leakage of the channel approaches 0 as α approaches 0, independently of the value of β.

p X (•) α 1-α n-1 . . . 1-α n-1 y 1 y 2 . . . y m x 1 β 1-β m-1 . . . 1-β m-1
Differential privacy, however, depends only on the value of β, more precisely, the parameter of differential privacy is max{ln 1 mβ , ln mβ, ln m-1 m(1-β) , ln m(1-β) m-1 }, and such parameter is unbound and goes to infinity as β approaches 0.

Leakage of "skinny" matrices (m < n)

The construction of the matrix for Proposition 16 gives a square matrix of dimension Val u × Val u . Often, however, the range of K is fixed, as it is usually related to the possible answers to the query f . Hence it is natural to consider the scenario in which we are given a number r < Val u , and want to consider only those K's whose range has cardinality at most r. Proposition 20 shows that in this restricted setting we can find a better bound than that from Theorem 15. Lemma 19. Let K be a mechanism with input X, where X = Val u , providing ǫ-differential privacy. Assume that r = |Range(K)| = v ℓ , for some ℓ < u. Let M be the matrix associated with K. Then it is possible to build a square matrix M ′ of size v ℓ × v ℓ , with row and column indices in A ⊆ X , and a binary relation ∼ ′ ⊆ A × A such that (A, ∼ ′ ) is isomorphic to (Val ℓ , ∼ ℓ ), and such that:

(i) M ′ is a channel matrix: m-1 j=0 M ′ i,j = 1 for all 0 ≤ i ≤ n -1; (ii) M ′ i,j
≤ (e ǫ ) u-l+d M ′ h,j for all i, h ∈ X and j ∈ Z, where d is the ∼ ′ -distance between i and h; (iii) the elements of the diagonal are all equal to the maximum element of the matrix:

M ′ i,i = max M ′ for all i ∈ X ; and (iv) H M ′ ∞ (X|Z) = H M ∞ (X|Z), if X has the uniform distribution.
Now we are ready to prove the proposition.

Proposition 20. Let K be a mechanism with associated channel matrix M , and let r = |Range(K)|. If K provides ǫ-differential privacy then the min-entropy leakage associated with K is bounded from above as follows:

I M ∞ (X; Z) ≤ log r (e ǫ ) u (v -1 + e ǫ ) ℓ -(e ǫ ) ℓ + (e ǫ ) u ,
where ℓ = ⌊log v r⌋.

The bound above can be significantly smaller than that from Theorem 15. For instance, when r = v it becomes log v (e ǫ ) u v -1 + (e ǫ ) u , which for large values of u is much smaller than Bnd (u, v, ǫ). This does not contradict the fact that the bound Bnd (u, v, ǫ) is strict-it is strict when we are free to choose the range, which here is fixed.

Leakage about an individual

Protecting an entire database is not the primary goal of differential privacy: some information is expected to be revealed, otherwise the query would not be useful. Instead, differential privacy aims at protecting the value of any single individual. We will see that its definition induces a straightforward bound on the min-entropy leakage about a given individual.

Let i be an individual in the database, and let X i the random variable that ranges over the values Val and represents the value of our individual. Let X -= X \ X i be the random variable that represents the values of all the other individuals in the database (after removing the individual i) and let us fix its value to be the tuple x -. Let Z be the random variable that represents the answers of the mechanism over the databases consisting of x -and the value of X i , and consider the channel with input X i , output Z, and elements p(z|x i , x -).

The min-entropy leakage about individual i, given knowledge of all other values in the database, can be defined, as usual, in terms of the corresponding a priori and a posteriori min-entropies:

I ∞ (X i ; Z|X -= x -) = H ∞ (X i |X -= x -) -H ∞ (X i |Z, X -= x -) = log z p(z) max x i p(x i |x -, z) max x i p(x i |x -) ≤ log z p(z) • max x i p(x i |x -, z) p(x i |x -) (8)
Observe now that

p(x i |x -, z) p(x i |x -) = p(x i , x -, z) p(x -, z) • p(x -) p(x i , x -) = p(x i , x -, z) p(x i , x -) • p(x -) p(x -, z) = p(z|x i , x -) p(z|x -) (9)
Note now that x = x i , x -and x -are adjacent. Hence, if the mechanism respects ǫ-differential privacy, we have p(z|x i ,x -) /p(z|x -) ≤ e ǫ . From ( 9) and ( 8) we therefore obtain:

I ∞ (X i ; Z|X -= x -) ≤ log e ǫ (10)
The above bound is not very tight, because the inequality in (8) can be quite loose. With our model, however, we can find a better bound by using Theorem 12, and the fact that the databases obtained by fixing X -= x -, and varying X i , are all adjacent to each other, i.e., they form a clique of v nodes. We obtain: Proposition 21. Assume that K satisfies ǫ-differential privacy. Then the information leakage for an individual is bounded from above by

I ∞ (X i ; Z|X -= x -) ≤ log v e ǫ v -1 + e ǫ .
Note that this bound on leakage for an individual neither depends on the size u of Ind, nor on the database x -that we fix, which is in accordance with the fact that the guarantees provided by differentialprivacy are independent of any side information. Also note that the bound given by Proposition 21 differs from that of [START_REF] Brouwer | Distance Regular Graphs[END_REF] up to an additive correction of log v /(v-1+e ǫ ).

This correction is always non-positive, and it becomes non-negligible only when e ǫ -1 is comparable to v. Since ǫ is usually taken to be a small constant, our bound gives the best improvement, with respect to the straightforward one, when v is small. For instance, in a database that collects information about the incidence of a certain disease in a population, we could have v = 3 (any individual is either affected, not affected, or absent from the database). If we take ǫ = 1.35, the usual bound on leakage is log e ǫ ≈ 1.95, whereas our bound corrects it by an additive factor of log v /(v-1+e ǫ ) ≈ -0.97, meaning that our bound is approximately 50% tighter.

Application to utility

In this section we consider the relation between differential privacy and the utility of oblivious mechanisms. In such mechanisms, utility is a property of the noise channel H of Figure 4, which maps true answer y ∈ Y into reported answer z ∈ Z according to conditional probability given by H y,z .

Note that leakage is a comparative measure, as it tells how much the adversary's probability of success has improved with respect to an initial situation. Utility, instead, is an absolute measure, as it is only concerned about how much the output of the mechanism tells about the true answer to the query. Hence, leakage is related to the difference between the a priori and a posteriori min-entropy of the channel, whereas utility concerns only the a posteriori min-entropy. We use the results of Section 4 to derive bounds on the utility of H, and to construct the optimal mechanism.

We start by noting that the data analyst does not necessarily take the output z of the randomization mechanism H as a guess for the true answer y, since some Bayesian post-processing can be applied to maximize the probability of a correct guess. For each reported answer z the data analyst can remap their guess to a value y ′ ∈ Y according to some strategy.

The standard way to define utility is via gain functions (cfr. [START_REF] Bernardo | Bayesian Theory[END_REF]). These are functions of the form gain : Y × Y → R, where gain(y, y ′ ) represents the reward for an adversary who guesses the answer y ′ when the correct answer is y. It is natural to define the utility of the noise channel H as the expected gain. In the following definition, which formalizes this concept, p(y) is the prior probability of the true answer y, and p(y ′ |y) is the probability of guessing y ′ when the true answer is y. Note that the definition depends implicitly on the reported answer z, since the data analyst guesses a y ′ on the basis of the observed z.

Proposition 24. Assume that function gain is the identity and the function guess is optimal. Then:

U (Y, Z) = z max y (p(y) p(z|y)) = V (Y |Z) = 2 -H∞(Y |Z) .

The bound on utility and construction of the optimal mechanism

In this section we show that in some special cases, the fact that K provides ǫ-differential privacy determines a bound on the utility under the identity gain function. We start by observing that the adjacency relation on X induces, via the query f , an adjacency relation on Y: Definition 25. Given y, y ′ ∈ Y, with y = y ′ , we say that y and y ′ are adjacent (notation y ∼ y ′ ), if, and only if, there exist x, x ′ ∈ Val u with x ∼ x ′ such that y = f (x) and y ′ = f (x ′ ).

Since ∼ is symmetric on databases, it is also symmetric on Y, therefore also (Y, ∼) forms an undirected graph.

Using the above concept of neighborhood for the inputs of the noise channel H, we can show that in an oblivious mechanism of the form represented in Figure 4, K satisfies ǫ-differential privacy with respect to neighbor databases if, and only if, H satisfies ǫ-differential privacy with respect to neighbor answers. Proposition 26. In an oblivious setting (cf. Figure 4), if the query function f is deterministic, then the mechanism K satisfies ǫ-differential privacy with respect to X if, and only if, the noise channel H satisfies ǫ-differential privacy with respect to Y.

The link established by the above proposition will help us determine a bound on the utility of H. Note that, as was also the case in the previous Section, the bounds derived in this Section depend on the graph structure of the channel input satisfying either distance-regularity or vertex-transitivity. However, whereas the graph structure on databases is guaranteed to always satisfy both types of symmetries, the graph structure on true answers may present only one of them, or neither (cfr. Figure 2). Hence, the two alternative ways of performing the second step of the matrix transformation of Figure 5 will be particularly useful here.

In the following, we use n d to represent the number of nodes in Y at distance d from another node in y ∈ Y. We recall that in any distance-regular or vertex-transitive graph, such number depends only on d and not on y (cf. Proposition 5).

Theorem 27. Consider a noise channel H satisfying ǫ-differential privacy for some ǫ > 0. Assume that the distribution of Y is uniform and that (Y, ∼) is either distance-regular or vertex-transitive. Then we have:

U (Y, Z) ≤ 1 d∈∆ n d e ǫ d (16)
Provided (Y, ∼) is distance-regular or vertex-transitive, the above bound is tight, in the sense that there is a channel matrix whose utility coincides with the bound. Indeed, for 0 ≤ i, j ≤ n -1, define H as follows.

H i,j = γ e ǫ d(i,j) , (17)
where

γ = 1 d∈∆ n d e ǫ d . ( 18
)
The following proposition shows that this definition gives a channel with maximal utility.

Theorem 28. Assume (Y, ∼) is distance-regular or vertex-transitive and that the distribution of Y is uniform. Then the matrix H defined by ( 17) is a channel matrix that satisfies ǫ-differential privacy and has maximal utility:

U (Y, Z) = 1 d∈∆ n d e ǫ d
Note that the definition of H given by ( 17) needs the condition of distance-regularity or vertextransitivity in order for n d to be defined. Furthermore, if the distribution on Y is not uniform, then the utility of such H is not necessarily optimal. These are strong limitations for the results in this section, because the structure of (Y, ∼) and the distribution on Y depend on the query f , and in general the above conditions are not granted by f .

Examples

Although our method for the construction of the optimal noise channel requires strong conditions (distance-regularity or vertex-transitivity), there are some interesting scenarios in which they are satisfied. Furthermore:

Remark 29. Our method can be applied also when the conditions of Theorem 28 are not met-we can always add "artificial" adjacencies to the graph structure so as to meet those conditions. Instead of (Y, ∼), for computing the distance in [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] we use a structure (Y, ∼ ′ ) that satisfies the conditions of Theorem 28, and such that ∼ ⊆ ∼ ′ . The matrix constructed in this way provides ǫ-differential privacy, but may be non-optimal. In general, the smaller ∼ ′ , the higher the utility.

The following are two simple scenarios in which the conditions are satisfied:

-(Y, ∼) is a clique: every element has exactly |Y| -1 adjacent elements.

-(Y, ∼) is a ring: every element has exactly two adjacent elements. This is similar to the case of the counting queries considered in [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF], with the difference that our "counting" is in arithmetic modulo |Y|.

The next two examples illustrate queries that give rise to the clique structure and to a line structurewhich is then transformed into a ring by adding artificial adjacencies to the graph-, and show the corresponding matrices. Note that the matrices generated by our method can be rather different, depending on the structure of (Y, ∼).

Example 30. Consider a database with electoral information in which each entry corresponds to a ballot cast, which is described by three fields:

elector: a unique (anonymized) identifier assigned to an elector; candidate: the name of the candidate the elector voted for; and city: the name of the city where the ballot was cast.

Consider the query "What is the city with the greatest number of votes for a given candidate c?", and assume that the data analyst models the utility with the identity gain function. 4 Note that every two answers are neighbors, so the graph structure of the domain of answers is a clique.

Consider the scenario where the set of cities is City = {A, B, C, D, E, F } and assume for simplicity that there is a unique answer for the query, i.e., there are no two cities with exactly the same number of individuals voting for candidate c. Table 1 shows two alternative mechanisms providing ǫ-differential privacy (with ǫ = ln 2).

The first one, M 1 , is based on the truncated geometric mechanism method used in [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] for counting queries, here adapted to the case where every two distinct answers are neighbors. More precisely, the mechanism is defined by mapping A, . . . , F into the interval of natural numbers [0, 6], then constructing the truncated geometric mechanism as in [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF], where the parameter α (representing the minimum ratio between the elements of the matrix) is calculated imposing both the ǫ-differential privacy constraint (with ǫ = ln 2) and that all natural numbers in [0, 6] are adjacent to each other. We obtain that α 5 = 2, i.e. α ≈ 1.5.

The second mechanism, M 2 , is constructed according to [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF]. Theorem 28 ensures that, for the uniform input distribution, M 2 gives optimal utility. With the uniform input distribution, indeed, we have

U (M 1 ) = 0.2243 < 0.2857 = U (M 2 ).
Even for non-uniform distributions, our mechanism still provides better utility. For instance, for p(A) = p(F ) = 1/10 and p(B) = p(C) = p(D) = P (E) = 1/5, we have U (M 1 ) = 0.2415 < 0.2857 = U (M 2 ). This should not come as a surprise: the geometric mechanism, as well as the Laplacian mechanism, performs well when they are defined on the natural metrics of the answer domain. Here, the structure [0, 6] is sort of imposed artificially.

Example 31. Consider the same database of the previous example, and assume now the query of interest "What is the number of votes for candidate c?". Each answer has at most two neighbors, and hence the graph structure on the domain of answers is a line. Assume, for simplicity, that 5 individuals participated in the election.

(a) M1: truncated Table 2 shows again the two mechanisms providing ǫ-differential privacy (ǫ = ln 2) that we considered in previous example: the truncated geometric mechanism M 1 (in which, now, α = 2, because we only have the constraint of (ln 2)-differential privacy), and ours, M 2 . Note that in order to apply our method we have first to apply Remark 29 to transform the graph structure from a line into a ring.

Considering the uniform prior distribution, the utility of M 1 is now greater than that of M 2 : 4/9 versus 8/21, respectively. This does not contradict our theorem, because our matrix is guaranteed to be optimal only in the case of a ring structure, not of a line as we have in this example. (In fact, if the structure were a ring, i.e., if the last row were adjacent to the first one, then M 1 would not provide ǫ-differential privacy.) In case of a line, as here, the truncated geometric mechanism has been proved optimal [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF].

Related work

To the best of our knowledge, the first work to investigate the relation between differential privacy and information-theoretic leakage for an individual was [START_REF] Mário | Differential privacy versus quantitative information flow[END_REF]. Their definition of channel was for a given database, and the channel inputs were all possible databases adjacent to it. Two bounds on leakage were presented, one for the min-entropy, and one for Shannon entropy. Our bound in Proposition 21 improves the min-entropy bound of [START_REF] Mário | Differential privacy versus quantitative information flow[END_REF].

Barthe and Köpf [START_REF] Barthe | Information-theoretic bounds for differentially private mechanisms[END_REF] were the first to investigate the more challenging connection between differential privacy and the min-entropy leakage for the set of all possible databases. They considered "end-to-end" differentially-private mechanisms, which correspond to what in this paper we call the mechanism K, and proposed, like we do, to interpret these mechanisms as information-theoretic channels. Barthe and Köpf provided a bound for leakage, but pointed out that it was not tight in general. They also observed that for any number of individuals u and level of privacy ǫ one can construct a channel whose maximal leakage is u log (2e ǫ ) /(e ǫ +1), and concluded therefore that the bound must be at least as high as such expression. Another difference between their work and ours is that [START_REF] Barthe | Information-theoretic bounds for differentially private mechanisms[END_REF] captures the case in which the focus of differential privacy is on hiding participation of individuals in a database, whereas we consider both the participation and the values of the individuals.

Clarkson and Schneider also considered differential privacy as a case study of their proposal for quantification of integrity [START_REF] Michael | Quantification of integrity[END_REF]. They analyzed database privacy conditions from the literature (such as differential privacy, k-anonymity, and l-diversity) for utility quantification. In particular, they studied the relationship between differential privacy and a notion of leakage (being different from ours as their definition is based on Shannon entropy) and they provided a tight bound on leakage.

Heusser and Malacaria [START_REF] Heusser | Applied quantitative information flow and statistical databases[END_REF] were among the first to explore the application of information-theoretic concepts to databases queries. They proposed to model database queries as programs, which allows for statistical analysis of the information leaked by the query. However, [START_REF] Heusser | Applied quantitative information flow and statistical databases[END_REF] did not relate information leakage to differential privacy.

Ghosh et al. [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] aimed at obtaining optimal-utility mechanisms while preserving differential privacy. They proposed adding noise to the output of the query according to the geometric mechanism. Their framework provides a general definition of utility for a mechanism M that captures any possible side information and preferences the users of M may have. They proved that the geometric mechanism is optimal in the particular case of counting queries. Our results in Section 6 do not restrict to counting queries, yet we only consider the case of the identity gain (loss) function.

Finally, our definition of the channel matrix in [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] corresponds to the exponential mechanism of McSherry and Talwar [START_REF] Mcsherry | Mechanism design via differential privacy[END_REF] when the quality function relating two answers i and j is taken to be -d(i, j), that is, the negative of the distance between them. Therefore, under the hypothesis of Theorem 27, it follows that the exponential mechanism is an optimal way to maximize utility as measured by the identity gain-function, while preserving differential privacy.

Conclusion

We have investigated the relations of ǫ-differential privacy with leakage, and utility, extending our previous work [START_REF] Mário | Differential Privacy: on the Trade-Off between Utility and Information Leakage[END_REF][START_REF] Mário | On the relation between Differential Privacy and Quantitative Information Flow[END_REF]. Our main contribution has been the development of a general technique for determining these relations depending on the graph structure of the input domain, induced by the adjacency relation and by the query. We have considered two particular structures, the distance-regular graphs, and the vertex-transitive graphs, which allowed us to obtain tight bounds on leakage and on utility. We also constructed an optimal noise channel satisfying ǫ-differential privacy for some special cases.

As future work, we plan to extend our result to other kinds of utility functions, among which we feel promising the g-leakage framework [START_REF] Mário | Measuring information leakage using generalized gain functions[END_REF].

(iv) M ′ satisfies ǫ-differential privacy: M ′ i,j ≤ e ǫ M ′ h,j , for all 0 ≤ i, h ≤ n -1 s.t. i ∼ h and all 0 ≤ j ≤ m -1; and (v) H M ′ ∞ (A|B) = H M ∞ (A|B), if A has the uniform distribution. Proof. For 0 ≤ k ≤ m -1, define Col k as the set of columns indexes j of M which have maximum in row k, and in no other row with index smaller than k, i.e.,

Col k = {j | M k,j = max M j and ∀i < k. M i,j < max M j }
Note that, by construction, each j belongs to exactly one set Col k . Consequently we have

k Col k = {0, 1, . . . , m} (19)
and

Col h ∩ Col k = ∅ for h = k (20)
Note that some Col k may be empty. In particular, Col k = ∅ for all k > n. Now, define the matrix M ′ as:

M ′ ik = j∈Col k M ij for 0 ≤ i ≤ n -1 , 0 ≤ k ≤ m -1
We prove now that M ′ satisfies the required properties.

It is easy to see that M ′ is a valid channel matrix thanks to properties [START_REF] Heusser | Applied quantitative information flow and statistical databases[END_REF] and [START_REF] Imrich | Product graphs, structure and recognition[END_REF].

We prove now that the maximum of each column k ≤ n is in the diagonal (condition (ii)):

M ′ kk = j∈Col k M kj ≥ j∈Col k M ij = M ′ ik Condition (iii) is satisfied because Col k = ∅ for all k > n.
Furthermore, M ′ satisfies ǫ-differential privacy (condition (iv)):

M ′ ik = j∈Col k M ij ≤ j∈Col k e ǫ M hj = e ǫ j∈Col k M hj = e ǫ M ′ hk
Finally, observe that:

k max M ′ k = k M ′ kk = k j∈Col k M kj = k j∈Col k max M j = j max M j from which it immediately follows that H M ′ ∞ (A|B) = H M ∞ (
A|B) (recall that A has the uniform distribution and therefore the a posteriori entropy is a function of the sum of the maximum of each column), so condition (v) is satisfied. Lemma 8. (Step 2a) Let M ′ be a square channel matrix of dimensions n × n that satisfies ǫ-differential privacy. Let ∼ be an adjacency relation on A such that the graph (A, ∼) is connected and distanceregular. Assume that the maximum value of each column is on the diagonal, i.e., M i,i = max M i for all 0 ≤ i ≤ n -1. Then it is possible to transform M ′ into a matrix M ′′ of the same dimension satisfying the following conditions:

(i) M ′′ is a channel matrix: n-1 j=0 M ′′ i,j = 1, for all 0 ≤ i ≤ n -1; (ii) the elements of the diagonal are all the same, and are equal to the maximum of the matrix:

M ′′ i,i = max M ′′ , for all 0 ≤ i ≤ n -1; (iii) M ′′ satisfies ǫ-differential privacy: M ′ i,j ≤ e ǫ M ′ h,j , for all 0 ≤ i, h, j ≤ n -1 s.t. i ∼ h; and (iv) H M ′′ ∞ (A|B) = H M ′ ∞ (A|B)
, if A has the uniform distribution. Proof. We define each element M ′′ i,j of the new matrix M ′′ as an averaging, or "smoothing", of the elements of M ′ that are at same distance from i as j is:

M ′′ i,j = 1 n|A d(i,j) (i)| k∈B h∈A d(i,j) (k) M ′ h,k
We prove that this definitions satisfies Conditions (i) -(iv). We start with Condition (i).

j∈B

M ′′ i,j = j∈B 1 n|A d(i,j) (i)| k∈B h∈A d(i,j) (k) M ′ h,k = 1 n k∈B j∈B 1 |A d(i,j) (i)| h∈A d(i,j) (k) M ′ h,k
Note that for every i, B = d∈∆ B d (i), and for different values of d the sets B d (i) are disjoint. Therefore by splitting the summation over j ∈ B we obtain

= 1 n k∈B d∈∆ j∈B d (i) 1 |A d (i)| h∈A d (k) M ′ h,k = 1 n k∈B d∈∆ h∈A d (k) M ′ h,k j∈B d (i) 1 |A d (i)| since j∈B d (i) 1 |A d (i)| = j∈A d (i) 1 |A d (i)|
= 1 (recall that the definition of distance in B is given as that in A), we obtain

= 1 n k∈B d∈∆ h∈A d (k) M ′ h,k
and now the summations over h and d can be joined together

= 1 n k∈B h∈A M ′ h,k
now, reorganizing the summations, and considering that M ′ is a channel matrix, and that |B| = n we have

= 1 n h∈A k∈B M ′ h,k = 1 n h∈A 1 = 1
which implies that condition (i) is satisfied.

We now turn our attention to the elements of the diagonal, which are all identical because M ′′ i,i =

1 n k∈B M ′ k,k .
To fulfill condition (ii) we still need to show that M ′′ i,i = max M ′′ i for all i ∈ A.

M ′′ i,j = 1 n|A d(i,j) (i)| k∈B h∈A d(i,j) (k) M ′ h,k ≤ 1 n|A d(i,j) (i)| k∈B h∈A d(i,j) (k) M ′ k,k (since the biggest element is in the diagonal) = 1 n k∈B M ′ k,k 1 |A d(i,j) (i)| h∈A d(i,j) (k) 1 = 1 n k∈B M ′ k,k |A d(i,j) (k)| |A d(i,j) (i)|
and because the graph is distance-regular, the number of vertices at any arbitrary distance (and, in particular, at distance d(i, j)) from any vertice is always the same. Hence

|A d(i,j) (k)| = |A d(i,j) (i)| and we can conclude = 1 n k∈B M ′ k,k • 1 = M ′′ i,i
Since A has the uniform distribution, the conditional min-entropy H M ′′ ∞ (A|B) is given by the sum of the maximum elements of each column of M ′′ . Since this sum is preserved in the transformation, we have H M ′′ ∞ (A|B) = H M ′ ∞ (A|B), hence Condition (iv) is satisfied. It remains to show that M ′′ satisfies ǫ-differential privacy (condition (iii)). Since d(i, i ′ ) = 1, from the triangular inequality we have:

d(i ′ , j) -1 ≤ d(i, j) ≤ d(i ′ , j) + 1
Thus, there are 3 possible cases:

1. d(i, j) = d(i ′ , j)
The result is immediate since

M ′′ i,j = M ′′ i ′ ,j . 2. d(i, j) = d(i ′ , j) -1
We define the set of neighbors of h "one step further away" from k:

F h,k = {h ′ ∼ h | h ′ ∈ A d(h,k)+1 (k)}
Equivalently, we can see F h,k as the set of neighbors of h that are not at distance d(h, k) -1 or d(h, k) from k. Since the graph is distance-regular, the number of elements in this set is given by the intersection number b d(h,k) , i.e., |F h,k | = b d(h,k) . The following inequalities hold for any h, h ′ ∈ A:

M ′ h,k ≤ e ǫ M ′ h ′ ,k ∀h ′ ∈ F h,k (diff. privacy) ⇒ b d(h,k) M ′ h,k ≤ e ǫ h ′ ∈F h,k M ′ h ′ ,k
(sum of the above)

Fix now a distance d and sum the above inequalities for all vertices at distance d from k:

h∈A d (k) b d M ′ h,k ≤ e ǫ h∈A d (k) h ′ ∈F h,k M ′ h ′ ,k
Note that, being the graph distance-regular, and by the definition of the intersection number c d+1 , each h

′ ∈ A d+1 (k) is contained in F h,k for exactly c d+1 different h ∈ A d (k).
So the righthand side above sums all vertices of A d+1 (k) exactly c d+1 times each. Thus we get that for all k ∈ B, d ∈ ∆:

b d h∈A d (k) M ′ h,k ≤ e ǫ c d+1 h∈A d+1 (k) M ′ h,k (21)
Finally, note that c d+1 |A d+1 (i)| = b d |A d (i)| (both sides count the number of edges between a vertex at distance d and a vertex at distance d + 1) and therefore we have

c d+1 b d = |A d (i)| |A d+1 (i)|
Now we pick d = d(i, j) to conclude that

M ′′ i,j = 1 n|A d (i)| k∈B h∈A d (k) M ′ h,k ≤ e ǫ 1 n|A d (i)| c d+1 b d k∈B h∈A d+1 (k) M ′ h,k (from (21)) = e ǫ 1 n|A d+1 (i)| k∈B h∈A d+1 (k) M ′ h,k = e ǫ M ′′ i ′ ,j . 3. d(i, j) = d(i ′ , j) + 1
This case is analogous to the case where d(i, j) = d(i ′ , j) -1.

Lemma 9. (Step 2b) Consider a square channel matrix M ′ satisfying the assumptions of Lemma 8, except that we assume (A, ∼) to be vertex-transitive instead of distance-regular. Then it is possible to transform M ′ into a matrix M ′′ with the same properties as in Lemma 8.

Proof. Let Γ be the automorphism group of (A, ∼). Since (A, ∼) and (B, ∼) are isomorphic, it follows that Γ is also the automorphism group of (B, ∼). For all i, j ∈ A we define the elements of M ′′ as:

M ′′ i,j = 1 |Γ| σ∈Γ M ′ σ(i),σ (j)
We now show that M ′′ satisfies Conditions (i) -(iv). We start with Condition (i):

n-1 j=0 M ′′ i,j = n-1 j=0 1 |Γ| σ∈Γ M ′ σ(i),σ(j) = 1 |Γ| σ∈Γ n-1 j=0 M ′ σ(i),σ(j) = 1 |Γ| σ∈Γ 1 (since M σ(i),• is a prob. distribution) = 1
Then we show that M ′′ i,i = M ′′ j,j for all i, j ∈ A.

M ′′ i,i = 1 |Γ| σ∈Γ M ′ σ(i),σ(i) = 1 |Γ| n-1 k=0 σ∈Γ i →k M ′ σ(i),σ(i) (since Γ = k Γ i →k ) = 1 |Γ| n-1 k=0 σ∈Γ i →k M ′ k,k (σ(i) = k since σ ∈ Γ i →k ) = 1 |Γ| n-1 k=0 M ′ k,k |Γ i →k | = 1 |Γ| n-1 k=0 M ′ k,k |Γ| n (by Lemma 32) = 1 n n-1 k=0 M ′ k,k
And we can conclude that every element in the diagonal of M ′′ is the same, as they are the average of the diagonal elements of M ′ . To fulfil condition (ii) we still need to show that M ′′ j,j = max M ′′ j for all j ∈ A.

M ′′ j,j = 1 |Γ| σ∈Γ M ′ σ(j),σ(j) ≥ 1 |Γ| σ∈Γ M ′ σ(h),σ (j)
(for all h ∈ A, since all maxima are in the diagonal of M

′ ) = M ′′ h,j
Then we show that M ′′ provides ǫ-differential privacy (condition (iii)). Let i, h ∈ A such that i ∼ h. Note that σ(i) ∼ σ(h) for all σ ∈ Γ since σ is an automorphism. Thus for all j ∈ A we have:

M ′′ i,j = 1 |Γ| σ∈Γ M ′ σ(i),σ(j) ≤ 1 |Γ| σ∈Γ e ǫ M ′ σ(h),σ(j) (ǫ-diff. priv. of M, σ(i) ∼ σ(h)) = e ǫ M ′′ h,j Finally, we show that H M ′′ ∞ (A|B) = H M ′ ∞ (A|B) (condition (iv)). H M ′′ ∞ (A|B) = -log 1 n n-1 i=0 M ′′ i,i
(the maxima of M ′′ are in the diagonal and are all equal)

= -log 1 n n-1 i=0 1 |Γ| σ∈Γ M ′ σ(i),σ(i) = -log 1 n 1 |Γ| σ∈Γ n-1 i=0 M ′ σ(i),σ(i) = -log 1 n 1 |Γ| σ∈Γ n-1 i=0 M ′ i,i (because σ is an automorphism) = -log 1 n n-1 i=0 M ′ i,i = H M ′ ∞ (A|B)
(the maxima of M are also in the diagonal) Proposition 11. Let M be a channel matrix satisfying ǫ-differential privacy where for every 0 ≤ i ≤ n -1 we have M i,i = max M . Then, for every node i ∈ A,

max M ≤ 1 d∈∆ |A d (i)| e ǫd ,
Proof. The elements of any given row i of M represent a probability distribution, so they sum up to 1: j M i,j = 1. Then we can derive the following inequalities. j max M e ǫd(i,j) ≤ 1 (by ( 5))

d∈∆ |A d (i)| max M e ǫd ≤ 1
(grouping elements by distance)

And from the above we can conclude.

max M ≤ 1 d∈∆ |A d (i)| e ǫd
Theorem 12. Consider a channel matrix M satisfying ǫ-differential privacy for some ǫ ≥ 0, assume that the probability distribution on A is uniform, and that (A, ∼) is either distance-regular or vertextransitive. Then

H M ∞ (A|B) ≥ -log 1 d∈∆ n d e ǫ d . (6)
In case the matrix M can be transformed via Lemmata 7, 8, and 9 into a matrix M ′′ whose elements all satisfy (5) with equality, then the bound (6) holds with equality.

Proof. The inequality follows directly from (3) and Proposition 11.

To prove the second part of the result, note that if a (transformed) matrix M ′′ is such that all of its elements satisfy (5) with equality, then trivially condition bound (6) also holds with equality. Recalling that the transformations given by Lemmata 7, 8, and 9 do not change the a posterior min-entropy of the channel, if M ′′ satisfies (6) with equality, so does M . Proof. The vertices of (Val u , ∼) are u-tuples (val 1 , . . . , val u ), val i ∈ Val and two vertices are adjacent if, and only if, they differ in exactly one element val i . Then the distance between two vertices is the number of elements in which they differ. Let x 1 , x 2 ∈ Val u with d(x 1 , x 2 ) = d, so they differ in exactly d elements. To go at distance d + 1 from x 1 we can select any of the remaining ud elements and change it in v -1 possible ways, so the total number is (ud)(v -1), which only depends on d, not on x 1 , x 2 . Similarly, by changing one of the differing elements of x 2 to match the value of x 1 we get a vertex at distance d -1, and there are d such elements. Proposition 14. The graph (Val u , ∼) is a vertex-transitive graph.

Proof. The Hamming graph is the Cartesian product of u complete graphs of size v. Complete graphs are trivially vertex-transitive and it is known [START_REF] Imrich | Product graphs, structure and recognition[END_REF] that a Cartesian product is vertex-transitive if, and only if, each of its factors is so. Theorem 15. If K satisfies ǫ-differential privacy, then the information leakage is bounded from above as I ∞ (X; Z) ≤ Bnd (u, v, ǫ).

Proof. We start by deriving the following.

Lemma 19. Let K be a mechanism with input X, where X = Val u , providing ǫ-differential privacy. Assume that r = |Range(K)| = v ℓ , for some ℓ < u. Let M be the matrix associated with K. Then it is possible to build a square matrix M ′ of size v ℓ × v ℓ , with row and column indices in A ⊆ X , and a binary relation ∼ ′ ⊆ A × A such that (A, ∼ ′ ) is isomorphic to (Val ℓ , ∼ ℓ ), and such that:

(i) M ′ is a channel matrix: m-1 j=0 M ′ i,j = 1 for all 0 ≤ i ≤ n -1; (ii) M ′ i,j ≤ (e ǫ ) u-l+d M ′ h,j for all i, h ∈ X and j ∈ Z, where d is the ∼ ′ -distance between i and h; (iii) the elements of the diagonal are all equal to the maximum element of the matrix: M ′ i,i = max M ′ for all i ∈ X ; and (iv) H M ′ ∞ (X|Z) = H M ∞ (X|Z), if X has the uniform distribution.

Proof. (Sketch) We first apply a procedure similar to that of Lemma 7 to construct a square matrix of size v ℓ × v ℓ which has the maximum values of each column in the diagonal. (In this case we construct an injection from the columns to rows containing their maximum value, and we eliminate the rows that at the end are not associated with any column.) Then define ∼ ′ as the projection of ∼ u on Val ℓ , which satisfies condition (ii). Finally, apply the procedure in Lemma 8, or equivalently the procedure in Lemma 9, on the structure (X , ∼ ′ ) to make all elements in the diagonal equal to the maximum element of the matrix (condition (iii)). Note that this procedure preserves the property of condition (ii), and conditional minentropy (condition (iv)). Also the matrix obtained is a valid channel matrix (condition (i)).

Proposition 20. Let K be a mechanism with associated channel matrix M , and let r = |Range(K)|. If K provides ǫ-differential privacy then the min-entropy leakage associated with K is bounded from above as follows:

I M ∞ (X; Z) ≤ log
r (e ǫ ) u (v -1 + e ǫ ) ℓ -(e ǫ ) ℓ + (e ǫ ) u , where ℓ = ⌊log v r⌋.

Proof. We first consider the case where r = v ℓ for some ℓ. We transform the matrix M associated with K by applying Lemma 19, and let M ′ be the resulting matrix. Let max M ′ be the value of every element in the diagonal of M ′ , i.e., max M ′ = M ′ i,i for every row i, and let A ′ d (i) be the set of elements whose ∼ ′ -distance from i is d. Note that for every j ∈ A ′ d (i) we have that M ′ j,j ≤ M ′ i,j (e ǫ ) u-ℓ+d , hence

M ′ i,j ≥ max M ′ (e ǫ ) u-ℓ+d
Furthermore each element j at ∼ ′ -distance d from i can be obtained by changing the value of d individuals in the ℓ-tuple representing i (remember that (A, ∼ ′ ) is isomorphic to (Val ℓ , ∼ ℓ )). We can choose those d individuals in ℓ d possible ways, and for each of these individuals we can change the value (with respect to the one in i) in v -1 possible ways. Therefore

|A ′ d (i)| = ℓ d (v -1) d
Proposition 21. Assume that K satisfies ǫ-differential privacy. Then the information leakage for an individual is bounded from above by

I ∞ (X i ; Z|X -= x -) ≤ log v e ǫ v -1 + e ǫ .
Proof. Fix a database x, and a particular individual i in Ind. The possible ways in which we can change the value of i in x are v -1. All the new databases obtained in this way are adjacent to each other, i.e., the graph structure associated with the input is a clique of v nodes. Recall that n d is the number of elements of the input at distance d from a given element x. In this case we have

n d =      1 for d = 0, v -1 for d = 1, 0 otherwise.
By substituting this value of n d in Theorem 12, we get

H ∞ (X i |Z, X -= x -) ≥ -log 1 1 + v -1 e ǫ = -log e ǫ v -1 + e ǫ (30)
The particular individual can present v different values, and thus in the case the input distribution is uniform its min-entropy is H ∞ (X i |X -= x -) = log v.

I ∞ (X i ; Z|X -= x -) = H ∞ (X i |X -= x -) -H ∞ (X i |Z, X -= x -)
(by definition)

≤ log v + log e ǫ v -1 + e ǫ (by (30))

= log v e ǫ v -1 + e ǫ Since the min-entropy leakage is maximum in the case of the uniform input distribution, the result follows. Proof. First we prove that the matrix as defined in ( 17) is a channel matrix, i.e., that each row is a probability distribution. (by ( 18))

= γ 1 γ = 1
Now we show that the mechanism respects ǫ-differential privacy. For every i, i ′ such that i ∼ i ′ and every j:

H i,j H i ′ ,j
= γ e ǫd(i,j) • e ǫd(i ′ ,j) γ (by definition of H) = e ǫd(i ′ ,j) e ǫd(i,j)

= e ǫ(d(i ′ ,j)-d(i,j))

≤ e ǫd(i ′ ,i) (by the triangular inequality)

= e ǫ (since i ∼ i ′ , d(i, i ′ ) = 1)
Finally, we show that the utility is maximum.

U (Y, Z) =

Fig. 1 .Fig. 2 .

 12 Fig. 1. Some distance-regular and vertex-transitive graphs

Fig. 5 .

 5 Fig. 5. Matrix transformation for distance-regular and vertex-transitive graphs

Proposition 13 .

 13 If v ≥ 2, the graph (Val u , ∼) is a connected distance-regular graph with diameter d max = u, and intersection numbers b d = (ud)(v -1) and c d = d, for all 0 ≤ d ≤ d max . Proposition 14. The graph (Val u , ∼) is a vertex-transitive graph.

Fig. 6 .Fig. 7 .

 67 Fig. 6. Venn diagram for the classes of graphs considered in Section 5.1.

Fig. 8 .

 8 Fig. 8. Graphs of Bnd (u, v, ǫ) for different configurations of u, v, ǫ

  The datasets and their adjacency relation aa ab ac ba ca bb bc cb cc aa

Example 17 .

 17 Assume we are interested in the eye color of a certain population Ind = {Alice, Bob}. Let Val = {a, b, c}, where a stands for absent (i.e., the null value), b stands for blue, and c stands for coal black. Each dataset is a tuple x 0 x 1 ∈ Val 2 , where x 0 represents the eye color of Alice (cases x 0 = b and x 0 = c), or that Alice is not in the dataset (case x 0 = a), whereas x 1 provides the same kind of information for Bob. Note that v = 3. Fig 9(a) represents the graph structure (X , ∼) of the database domain, i.e., the set X of all possible datasets and its adjacency relation. Fig 9(b) represents the matrix with input X which provides ǫ-differential privacy and has the highest min-entropy leakage.

1 mFig. 10 . 18 Example 18 .

 1101818 Fig. 10. Input distribution and channel matrix for Example 18 Example 18. Let (X , Y, M ) be a channel such that |X | = n and |Y| = m. Assume that the channel matrix is such that p(x 1 ) = α and p(x i ) = 1-α n-1 for 2 ≤ i ≤ n, and let p(y 1 | x 1 ) = β, p(y j | x 1 ) = 1-β m-1 for 2 ≤ j ≤ m, and p(y j | x i ) = 1 m otherwise.This channel is represented in Figure10. Simple calculations show that the min-entropy leakage of the channel approaches 0 as α approaches 0, independently of the value of β.Differential privacy, however, depends only on the value of β, more precisely, the parameter of differential privacy is max{ln 1 mβ , ln mβ, ln m-1 m(1-β) , ln m(1-β) m-1 }, and such parameter is unbound and goes to infinity as β approaches 0.

. 4 .

 4 Application to leakage (Section 5) Proposition 13. If v ≥ 2, the graph (Val u , ∼) is a connected distance-regular graph with diameter d max = u, and intersection numbers b d = (ud)(v -1) and c d = d, for all 0 ≤ d ≤ d max .

1 )

 1 d e ǫ(u-d) (multiplying each term by e ǫu /e ǫu ) = (v -1 + e ǫ ) u e ǫu (by binomial expansion)

. 5 .Proposition 23 . 12 ) 27 ..

 5231227 Application to utility (Section 6) Assuming that the data analyst uses a remapping function guess : Z → Y, we have U (Y, Z) = y,z p(y, z)gain(y, guess(z)). (Theorem Consider a noise channel H satisfying ǫ-differential privacy for some ǫ > 0. Assume that the distribution of Y is uniform and that (Y, ∼) is either distance-regular or vertex-transitive. Then we have: Proof. Since (Y, ∼) is distance-regular or vertex-transitive, and the distribution on Y is uniform, we can apply Theorem 12 to derive that H M ∞ (Z|Y ) ≥log Then we just substitute this result in Proposition 24. Theorem 28. Assume (Y, ∼) is distance-regular or vertex-transitive and that the distribution of Y is uniform. Then the matrix H defined by (17) is a channel matrix that satisfies ǫ-differential privacy and has maximal utility:

  since |Y| = |Z| = n)

Table 1

 1 Mechanisms for the city with higher number of votes for candidate c

			(b) M2: our mechanism
			In/Out A B C D E F
		060 0.053 0.046 0.040 0.267	A 2/7 1/7 1/7 1/7 1/7 1/7
	B 0.465 0.069 0.060 0.053 0.046 0.307	B 1/7 2/7 1/7 1/7 1/7 1/7
	C 0.405 0.060 0.069 0.060 0.053 0.353	C 1/7 1/7 2/7 1/7 1/7 1/7
	D 0.353 0.053 0.060 0.069 0.060 0.405	D 1/7 1/7 1/7 2/7 1/7 1/7
	E 0.307 0.046 0.053 0.060 0.069 0.465	E 1/7 1/7 1/7 1/7 2/7 1/7
	F	0.267 0.040 0.046 0.053 0.060 0.534	F 1/7 1/7 1/7 1/7 1/7 2/7

Table 2

 2 Mechanisms for the counting query(5 voters)

The combination of answers to statistical queries with side information can affect even the privacy of individuals not present in the database. For example, if one knows that a certain person's salary is exactly the same as the average salary of the people in the database, then the average-salary query will reveal the salary of this person, independently from whether they are in the database or not.

Instead of gain functions,[START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] uses the dual notion of loss functions, but the final result is equivalent.

In more general cases, not studied here, the answer domain could be endowed with a notion of distance, and the gain function could take into account the "proximity" of the reported answer to the true one. Intuitively, in this case a "close" answer, even if wrong, should be considered better than a "distant" one.

Clearly there are more interesting gain function, for instance with a suitable gain function we could distinguish the case in which the answer is totally wrong from an answer that is "almost correct" in the sense that the guessed town was the second best for the candidate. However, this is out of the scope of this paper as here we consider only binary gain functions.

Acknowledgements We are very grateful to the anonymous referees: Their comments and suggestions helped us to improve the paper in a substantial way.

Mário S. Alvim was a postdoctoral research associate at the Mathematics Department of the University of Pennsylvania when part of this research was performed, and he was partially supported by the AFOSR MURI "Science of Cyber Security: Modeling, Composition, and Measurement" as AFOSR grant FA9550-11-1-0137. Alvim was also partially supported by CNPq grant 459819/2014-3. The work of Konstatinos Chatzikokolakis and Catuscia Palamidessi was partially supported by the European 7th FP grant MEALS, the project ANR-12-IS02-001 PACE, the INRIA Large Scale Initiative CAPPRIS, and the INRIA Associated team PRINCESS. Part of this work was carried on during a visit of Pierpaolo Degano at LIX, partially supported by a Digiteo/INRIA grant, and part within the MIUR-PRIN project Security Horizons.

We focus here on the so-called identity gain function, which is defined as

The use of identity gain functions in the context of differential privacy was also investigated by Ghosh et al. [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF]. 2 Let δ x represent the "point" probability distribution which has value 1 on x and 0 elsewhere. Hence gain id (y, guess(z)) = δ y (guess(z)).

Intuitively, the function gain id fits situations in which there is little reason to prefer one answer over another, except if it is the correct answer. 3 By substituting gain with gain id in [START_REF] Dwork | Differential privacy[END_REF] we obtain

which tells us that the utility is highest when guess(z) = y is chosen to maximize p(y, z). Hence this is the data analyst's best strategy. Under such a maximizing remapping, we have

The formula thus obtained trepresents the Bayes risk, which is the converse of the min-vulnerability. Thus there is a correspondence between U and the a posteriori min-entropy, expressed by the following proposition.

Appendix

Proofs are given in the order the corresponding results appear in the main text. Before proceeding, we providing additional notation, definitions, and auxiliary results needed for the proofs in the reminding of this section.

.1. Auxiliary notation, definitions, and results Adjacency relation on channel outputs. At the end of the transformation operated by Lemma 7, and after removing the all-zero columns, we have a square matrix in which the maximum of each column is in the diagonal, as in Figure 11. On the columns B of this matrix we define a a graph structure derived from that of A. This will be useful to prove the Step 2a and Step 2b of the matrix transformation in Section 4. The definition is simply the following: given two elements j 1 , j 2 ∈ B, we stipulate that j 1 ∼ j 2 if, and only if, j 1 , j 2 are also in A 5 , and j 1 ∼ j 2 in A.

In this way (B, ∼) is also a graph structure, and the notions of distance, diameter, set of vertices at distance d from a given vertex, etc., are defined as usual. Also (A, ∼) and (B, ∼) are isomorphic hence all the properties that hold for A hold also for B.

Automorphisms. Let (V, ∼) be a graph, w, w ′ ∈ V be two of its vertices, and let Γ be an automorphism group for (V, ∼). We define the set of automorphisms that map w to w ′ as

Note that Γ w →w ′ ∩ Γ w →w ′′ = ∅ for all w ′ = w ′′ , and that Γ = w ′ Γ w →w ′ for any w ∈ V. 5 Recall that for simplicity we represent the elements of A and B by their indexes.

Fig. 11. The relation between elements of a row i and the elements in the diagonal

Lemma 32 states that in a vertex-transitive graph, starting from any vertex w, there exist as many automorphisms mapping w to w ′ as to any other vertex w ′′ . This auxiliary result is used in the proof of Lemma 9.

Lemma 32. Let (V, ∼) be a finite vertex-transitive graph, n = |V| and Γ its full automorphism group. Then, for all w, w ′ , w ′′ ∈ V:

Proof. Given two automorphisms σ and ρ, let ρ • σ denote the composition of ρ with σ, i.e., the automorphism one would obtain by first applying σ to every vertex of the graph, and then applying ρ to the resulting mapping. By extension, given an automorphism group Γ and an automorphism ρ, we write ρ•Γ for the automorphism group obtained by composing ρ with every σ ∈ Γ.

Assume that |Γ w →w ′ | < |Γ w →w ′′ | for some w, w ′ , w ′′ ∈ V. Since the graph is vertex-transitive, there exists an automorphism ρ such that ρ(w ′′ ) = w ′ .

Consider the set of automorphisms ρ • Γ w →w ′′ . This set contains

. Moreover these automorphisms map w to w ′ , and therefore we have ρ • Γ w →w ′′ ⊆ Γ w →w ′ , which is a contradiction since by hypothesis we have

.2. Preliminaries (Section 2)

Proposition 5. If a graph G = (V, ∼) is distance-regular or vertex-transitive, then, for every distance d ∈ ∆, there exists a constant n d which is equal to the cardinality of V d (w) for every w ∈ V.

Proof. Let us first examine the case in which G is distance-regular. Consider the alternative definition of distance-regularity given by proposition 3, and assume w ′ = w and j = k = d. We have V d (w) = V j (w) ∩ V k (w ′ ) whose cardinality, by Proposition 3, depends only on j, k (both equal d), and on d(w, w ′ ). Finally, note that d(w, w ′ ) = d(w, w) = 0. Consider now the case in which G is vertex-transitive. Given two vertices w and w ′ , we have that there exists an automorphism σ such that σ(w) = w ′ . By simple induction it can be shown that for every d ∈ ∆, if V d (w) = {w 1 , w 2 , . . . , w n }, then V d (w) = {σ(w 1 ), σ(w 2 ), . . . σ(w n )}, which means that the cardinality of V d (w) depends only on d. (i) M ′ is a channel matrix: m-1 j=0 M ′ i,j = 1, for all 0 ≤ i ≤ n -1; (ii) each of the first n columns has a maximum in the diagonal: M ′ i,i = max M ′ i , for all 0 ≤ i ≤ n -1; (iii) the mn last columns only contain 0's: M ′ i,j = 0, for all 0 ≤ i ≤ n -1 and all n ≤ j ≤ m -1;

And we can use the above in Theorem 12 as follows.

(by Theorem 12)

=log 1

/e ǫu (by ( 22))

Since by hypothesis the input distribution is uniform, the min-entropy of X is maximum, i.e., H ∞ (X) = log |Val u |. We then use this fact to derive that

Proposition 16. For every u, v, and ǫ it is possible to define the mechanism K below, which provides ǫ-differential privacy and whose min-entropy leakage, for the uniform input distribution, is

, for every input x and output z.

Proof. The adjacency relation in X determines a graph structure (X , ∼). Let Z = X and define the matrix of K as follows, where d = d(x, z):

We need to show that p(•|x) is a probability distribution for every x:

(max occurs when d = 0 in ( 24))

= 1

We now show that K provides ǫ-differential privacy. For every x, x ′ ∈ X such that x ∼ x ′ , and for every z ∈ Z we have:

(by ( 24))

≤ e ǫd(x,x ′ ) (by the triangle inequality)

Since input distribution is uniform, we have:

Moreover, we know from (3) that H ∞ (X|Z) =log max M ′′ , and to obtain the maximum value we take d = 0 in [START_REF] Köpf | An information-theoretic model for adaptive side-channel attacks[END_REF]:

Now, by subtracting the value of H ∞ (X|Z) from the value of H ∞ (X) we obtain I ∞ (X; Z) = Bnd (u, v, ǫ).

Taking into account that for M ′ i,i we need not to divide by (e ǫ ) u-ℓ+d , we obtain:

Since each row represents a probability distribution, the elements of row i must sum up to 1. Hence:

Simple calculations, similar to those of the proof of Theorem 15, give:

Therefore:

= log v u + log

(by ( 25) )

Consider now the case in which r is not of the form v ℓ . Let ℓ be the maximum integer such that v ℓ < r, and let m = rv ℓ . Transform the matrix M associated with K by collapsing the m columns with the smallest maxima into the m columns with highest maxima. I.e., let j 1 , j 2 , . . . , j m the indices of the columns which have smallest maxima values, i.e., max M jt ≤ max M j for every column j = j 1 , j 2 , . . . , j m . Similarly, let k 1 , k 2 , . . . , k m be the indices of the columns with maximum values. Recalling the definition of the "collapsing" operator introduced in Section 4.1, we define

Finally, eliminate the m all-zero columns to obtain a matrix with exactly v ℓ columns. It is easy to show that

After transforming N into a matrix M ′ with the same min-entropy leakage as described in the first part of this proof, from [START_REF] Roth | Interactive privacy via the median mechanism[END_REF] we conclude Proof. Just substitute [START_REF] Dwork | Differential privacy and robust statistics[END_REF] in the definition of conditional min-entropy: H ∞ (Z | Y ) =log z max y ((p(y) p(z|y)).

Proposition 26. In an oblivious setting (cf. Figure 4), if the query function f is deterministic, then the mechanism K satisfies ǫ-differential privacy with respect to X if, and only if, the noise channel H satisfies ǫ-differential privacy with respect to Y.

Proof. The probability of K producing an arbitrary reported answer z given an arbitrary database x can be calculated as

(since the mechanism is oblivious)

Hence, it follows immediately that Kx,z K x ′ ,z ≤ e ǫ if, and only if,