Ehab Elsalamouny

Konstantinos Chatzikokolakis

Catuscia Palamidessi

A differentially private mechanism of optimal utility for a region of priors

The notion of differential privacy has emerged in the area of statistical databases as a measure of protection of the participants' sensitive information, which can be compromised by selected queries. Differential privacy is usually achieved by using mechanisms that add random noise to the query answer. Thus, privacy is obtained at the cost of reducing the accuracy, and therefore the utility, of the answer. Since the utility depends on the user's side information, commonly modelled as a prior distribution, a natural goal is to design mechanisms that are optimal for every prior. However, it has been shown that such mechanisms do not exist for any query other than (essentially) counting queries ([1]). Given the above negative result, in this paper we consider the problem of identifying a restricted class of priors for which an optimal mechanism does exist. Given an arbitrary query and a privacy parameter, we geometrically characterise a special region of priors as a convex polytope in the priors space. We then derive upper bounds for utility as well as for min-entropy leakage for the priors in this region. Finally we define what we call the tight-constraints mechanism and we discuss the conditions for its existence. This mechanism reaches the bounds for all the priors of the region, and thus it is optimal on the whole region.

Introduction

Statistical databases are commonly used to provide aggregate information about the individuals of a certain population, to attain a social benefit. In general, certain data of the participants in the database may be confidential, and we should not allow queries that can reveal them. On the other hand we would like to allow global queries, like, for instance, the average salary of the inhabitants of a certain region, the percentage of individuals having a certain disease, or the cities with the highest rates of crime. This kind of information can be extremely useful for e.g. financial planning, medical research, and anti-crime measures.

Unfortunately, even though these kinds of queries do not refer directly to the individual data, they still represent a major threat to the privacy of the participants in the databases. To illustrate the problem, consider a database whose records contain personal data, among which the salary, regarded as confidential. Suppose we are allowed to query the number of participants and their average salary. Then, by querying the database before and after the insertion of a new record "Bob", we can easily infer, by an easy calculation, the exact salary of Bob.

A successful approach to solve the above problem is to report to the user an approximate answer instead of the exact one. The approximate answer is produced by adding controlled random noise to the exact answer. The overall procedure, representing the sanitized query, is a (probabilistic) mechanism K which takes as input the database v and reports to the user an output o in some domain O, according to some probabilistic distribution. Intuitively, the uncertainty introduced at the level of the global answer induces uncertainty about the value of the individual data in the database, thus making it difficult for an attacker to guess such value. However it is crucial to know exactly what kind of protection is achieved this way. Differential privacy, introduced by Dwork ( [START_REF] Dwork | Differential privacy[END_REF][START_REF] Dwork | Differential privacy and robust statistics[END_REF][START_REF] Dwork | Differential privacy in new settings[END_REF][START_REF] Dwork | A firm foundation for private data analysis[END_REF]), is a formalization of the privacy property that can be guaranteed by such mechanism. It is a quantitative notion, in the sense that it depends on a parameter representing the provided level of privacy. Following common lines (e.g. [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF][START_REF] Gupte | Universally optimal privacy mechanisms for minimax agents[END_REF][START_REF] Alvim | On the relation between Differential Privacy and Quantitative Information Flow[END_REF]), in this paper we assume that the mechanism K is oblivious with respect to the given query f . Namely, its output depends only on the exact query result and not on the underlying database. Furthermore, we consider only the case in which the domains of the answers (exact and reported) are finite. Under these assumptions, the mechanism K is determined by an underlying stochastic noise matrix X whose generic element x io is the conditional probability of reporting the answer o when the exact query answer is i.

Besides guaranteeing differential privacy, a mechanism should of course provide an answer which is still "useful" enough to the user asking the query. This second goal is measured in terms of utility, which represents the average gain that a rational user obtains from the reported answer. More precisely, on the basis of the reported answer o the user can make a guess k (remapping) about the exact hidden query result i. His gain g(i, k) is established by a given function g. The utility is then defined as the expected gain under the best possible remapping. While the gain function can take various forms, in this paper we restrict our analysis to the binary gain function, which evaluates to 1 when the user's guess is the same as the query result (k = i) and evaluates to 0 otherwise.

The utility of a mechanism depends on the side-information which the user may have about the database. This knowledge induces a probability distribution, called 'prior', over the possible query results. Suppose for example that a user "Alice" knows that all people in the database have a salary of at least 20K e. Thus Alice expects the average of the salaries to be at least 20K e. This is reflected on Alice's prior over the average-salary query results: the total probability mass is distributed on the range of values ≥ 20K, while it is 0 on lower values. Given this prior, a mechanism X producing only outputs ≥ 20K is intuitively more useful to Alice than another one generating also values < 20K, which are less informative for Alice.

The optimal mechanism for a given prior and level of privacy is defined as the mechanism which maximises the utility function, while satisfying -differential privacy. Naturally, we do not want to change the mechanism depending on the user, so we would like to devise mechanisms which are universally optimal, i.e. optimal for any prior. A famous result by Gosh et al. [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] states that this is possible for the so-called counting queries, which are queries concerned with questions of the kind "how many records in the database have the property P?" (for some P). In [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] it was proved that the truncated geometric mechanism is optimal, for this type of queries, for all priors. Of course the question immediately arises whether we can obtain a similar result for other queries as well. Unfortunately Brenner and Nissim answered this question negatively, by showing that for any query other than (essentially) counting queries a universally optimal mechanism does not exist [START_REF] Brenner | Impossibility of differentially private universally optimal mechanisms[END_REF]. However, one can still hope that, also for other queries, by restricting the class of users (i.e. the domain of priors), one could find mechanisms that are optimal for all the users of the class. This is exactly the objective of the present paper: given a query, we aim at identifying a mechanism, and a class of users, for whom that same mechanism provides -differential privacy and maximal utility at the same time.

Given an arbitrary query and a privacy level > 0, we call -regular the priors, for which, the probabilities of two adjacent answers (i.e. answers obtained from databases that differ for only one record) are not very different (their ratio is bounded by e ). At the same time, they may assign significantly different probabilities to "distant" answers. As an example of such prior, consider a researcher "Alice" in a medical school who is interested in the incidence of a certain disease in a statistical medical database containing 1000 records. (Each record represents a person and contains a field saying whether or not the person is infected.) Assume that Alice's side knowledge lets her to expect that the percentage of infected people is likely to be, say, between 1% and 2%, while it is highly unlikely to be higher than 5%. Also, assume that Alice does not have "sharp" enough information to assign significantly different probabilities to adjacent answers, e.g. 1.5% (15 people affected) and 1.6% (16 people affected). It is precisely this kind of users that we target in this paper: we will see that, under certain conditions, we can design a mechanism which maximises the utility for all of them.

A related issue that we consider in this paper is the amount of information leaked by a mechanism, from the point of view of the so-called quantitative information flow framework. There have been various proposal for quantifying the information flow; we consider here the information-theoretic approach, in which the system (in this case the mechanism) is regarded as a noisy channel, and the leakage is defined as the difference between the a priori entropy of the input (the secret -in this case the database entries), and the a posteriori one, after revealing the output (in this case the reported answer). Depending on the notion of entropy adopted one can model different kinds of adversaries [START_REF] Köpf | An information-theoretic model for adaptive side-channel attacks[END_REF]. In particular, Shannon entropy (used, for instance, in [START_REF] Clark | Quantitative information flow, relations and polymorphic types[END_REF][START_REF] Boreale | Quantifying information leakage in process calculi[END_REF][START_REF] Malacaria | Assessing security threats of looping constructs[END_REF][START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF]) is suitable for adversaries who can probe the secret repeatedly, while Rényi min-entropy (used, for instance, in [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]) is suitable for one-try attacks. In both cases, the main difference with differential privacy is that the information-theoretic approaches measure the expected threat to confidentiality (i.e. the average amount of leakage, where each leak is weighted by its probability to occur), while differential privacy considers catastrophic any disclosure of confidential information, no matter how unlikely it is.

Computing and bounding the information leakage has been pursued in several papers, we mention for instance [START_REF] Köpf | Vulnerability bounds and leakage resilience of blinded cryptography under timing attacks[END_REF][START_REF] Andrés | Computing the leakage of information-hiding systems[END_REF]. Recently, researchers have investigated the relation between differential privacy and information leakage [START_REF] Barthe | Information-theoretic bounds for differentially private mechanisms[END_REF][START_REF] Clarkson | Quantification of integrity[END_REF][START_REF] Alvim | Differential Privacy: on the trade-off between Utility and Information Leakage[END_REF][START_REF] Alvim | On the relation between Differential Privacy and Quantitative Information Flow[END_REF], and in particular it has been proved in [START_REF] Alvim | Differential Privacy: on the trade-off between Utility and Information Leakage[END_REF] that differential privacy induces a bound on the min-entropy leakage, which is met by a certain mechanism for the uniform prior (for which min-entropy leakage is always maximum). In this paper, we extend the above result so to provide a more accurate bound for any fixed -regular prior distribution. More precisely, we provide a bound to the leakage specific to the prior and that can be met, under a certain condition, by a suitable mechanism. It is worth noting that this mechanism is defined similarly to the one that is optimal for the -regular priors. In fact, min-entropy leakage and utility are strongly related: the main difference is what we regard as the input of the channel. For the former is the database, for the latter the exact answer to the query. Correspondingly, min-entropy leakage measures the correlation between the reported answer and the database entries, while utility measures the correlation between the reported answer and the exact answer.

Contribution

-We identify, for an arbitrary query and a privacy parameter , the class of theregular prior distributions on the exact answers. The interest of this class is that for each prior in it we are able to provide a specific upper bound to the utility of anydifferentially-private mechanism. We characterise this class as a geometric region, and we study its properties. -We describe an -differentially-private mechanism, called "tight-constraints mechanism", which meets those upper bounds for every -regular prior, and is therefore universally optimal in this region. We provide necessary and sufficient conditions for the existence of such mechanism, and an effective method to test the conditions and to construct the mechanism. -Switching view, and considering the correlation between the databases and the reported answers (instead than between the exact and reported answers) we recast the above definitions and results in terms of quantitative information flow. The outcome is that we are able to improve the upper bounds for the min-entropy leakage of an -differentially-private mechanism, for all the -regular prior distributions on the databases. A construction similar to the one in previous point yields the tightconstraints mechanism which reaches those upper bounds.

Plan of the paper In the next section we recall the basic definitions of differential privacy and utility. Section 3 introduces the notion of -regular prior, investigates the properties of these priors, and gives a geometric characterisation of their region. Section 4 shows that for all -regular priors on the exact answers (resp. databases), -differential privacy induces an upper bound on the utility (resp. on the min-entropy leakage). Section 5 identifies a mechanism which reaches the above bounds for every -regular prior, and that is therefore the universally optimal mechanism (resp. the maximally leaking mechanism) in the region. Section 6 illustrates our methodology and results using the example of the sum queries. Section 7 concludes and proposes some directions for future research.

For reason of space we have omitted several proofs from the body of the paper. The interested reader can find them in the appendix.

Preliminaries

Differential privacy

The notion of -differential privacy, introduced by Dwork in [START_REF] Dwork | Differential privacy[END_REF], imposes constraints on data reporting mechanisms so that the user is unable to distinguish, from an output, between two databases differing only for one record. This indistinguishability property represents a protection for the individual corresponding to that record. In the following, the mechanism is represented as a probabilistic function K from the set of possible databases V to the set of possible reported outputs O. The relation of 'differing only for one record' for two databases v and v is represented by the adjacency relation and written as v ∼ v .

Definition 1 (Differential privacy [START_REF] Dwork | Differential privacy[END_REF]). A probabilistic mechanism K from V to O satisfies -differential privacy if for all pairs v, v ∈ V, with v ∼ v , and all S ⊆ O, it holds that P(K(v) ∈ S ) ≤ e P(K(v ) ∈ S ).

Note that the indistinguishability property is independent from the a priori knowledge the user may have about the database. Consider a query f : V → R f , where R f is the set of the query results. Then a mechanism K is said to be oblivious if for every database v ∈ V, the output of the mechanism, K(v), depends only on f (v), the result of applying the query to the database v, regardless of v itself. More formally, Definition 2 ( [START_REF] Brenner | Impossibility of differentially private universally optimal mechanisms[END_REF]). Let f : V → R f be a query. A mechanism K : V → O is oblivious if there exists a randomised function M : R f → O such that, for all v ∈ V, and all S ⊆ O, it holds that P(K(v) ∈ S ) = P(M( f (v)) ∈ S ).

According to the above definition, any oblivious mechanism K can be seen as a cascade of two functions: the deterministic query f and a randomised function M. The role of M is to add random noise to the exact query result f (v) and produce a 'noisy' output o ∈ O to the user. The privacy guarantees are therefore provided by the function M which we implement by a stochastic matrix X = (x io ), called the noise matrix. The rows of X are indexed by the elements of R f and the columns are indexed by the elements of O. With this representation x io is the probability of giving the output o when the exact query result is i. In this paper, we consider only oblivious mechanisms and therefore our results concern the design of the noise matrix X. Similarly, the query function f and the mechanism can be represented as matrices and hence it holds by Def. 2 that K = f X.

Given a query f , The adjacency relation on databases V induces another adjacency relation on the set of query results R f as follows.

Definition 3 (Adjacent query results). Given a query function f with a range R f , two different results i, h ∈ R f are said to be 'adjacent', and written as i ∼ f h, if and only if there exists two databases v, v such that f (v) = i and f (v ) = h, and v ∼ v .

f 1 (v) = count(v, p) 0 1 2 3 4 n Query f 2 (v) = count(v, p) mod (n + 1) (0,n) (1,n) (2,n) (n,n) (0,2) (1,2) (2,2) (n,2) (0,1) (1,1) (2,1) (n,1) (0,0) (1,0) (2,0) (n,0)
A 2-count query

f 3 (v) = (count(v, p 1 ), count(v, p 2 ))
Fig. 1. Examples for the graph structures of different queries Informally, i, h ∈ R f are adjacent if they discriminate between two adjacent databases.

Using the introduced notion of adjacency between query results, a graph structure can be used to model these results along with their adjacency relationship. More precisely, the set of nodes in this graph represents the set of query results R f , while edges represent the adjacency relationship among them. It is worth noting that this graph structure of queries have been used also in [START_REF] Alvim | On the relation between Differential Privacy and Quantitative Information Flow[END_REF][START_REF] Brenner | Impossibility of differentially private universally optimal mechanisms[END_REF] to analyse the differentially private mechanisms.

Figure 1 shows examples of the graph structures of different queries. In these examples count(v, p) refers to a counting query which returns the number of records in the database v which satisfy a certain property p. Other queries in the figure are expressed using the count function.

Let K be an oblivious mechanism for which X is the underlying noise matrix. It is intuitive to see that satisfying the indistinguishability between adjacent databases (i.e. satisfying differential privacy) corresponds to the satisfying indistinguishability (by means of X) between adjacent query results. Formally, Lemma 1. Given a noise matrix X, An oblivious mechanism K satisfies -differential privacy if and only if for all query results i, h where i ∼ f h and all outputs o ∈ O, it holds that x io ≤ e x ho .

Note that Lemma 1 provides an equivalent characterisation for differential privacy in terms of adjacent query results rather than adjacent databases.

With the graph structure of a query, the 'distance' between two query results i, h, denoted by d(i, h) is defined as the shortest graph distance between i and h. Using this distance measure, differential privacy constraints can be further lifted from conditions on pairs of adjacent query results (Lemma 1) to a general condition on any pair of query results according to the following proposition.

Proposition 1. Given a noise matrix X, the oblivious mechanism K satisfies -differential privacy if and only if for all query results i, h and all outputs o ∈ O, it holds that x io ≤ e d(i,h) x ho .

That is, the ratio between the probability of reporting an answer o given that the query result is r and the probability of reporting the same output o given that the query result is h does not exceed e d(i,h) . We call the noise matrix that satisfies this conditiondifferentially private. Note that, while Lemma 1 describes differential privacy in terms of only adjacent query results, the equivalent characterisation given by Proposition 1 specifies the privacy constraints imposed on any pair of results (whether or not they are adjacent to each other). This feature abstracts our analysis to arbitrary pairs of graph nodes rather than reasoning about only adjacent ones.

Utility model

For an oblivious mechanism K, the objective of the underlying noise matrix X is to guarantee the differential privacy of the database, while providing the user with 'useful' information about the true query result. That is to satisfy a trade-off between the privacy and utility. For quantifying the utility of K we follow the model adopted in [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF]. Given a query f , let i ∈ R f be the result of executing f on some database. After processing i by the noise matrix X, let o be the reported output to the user. In practice, the user may use the output o, to 'guess' the value of the real query result. Therefore she may apply a remap ( or guess) function which maps the mechanism output o to a guess k ∈ R f for the exact query answer. The remap function (or simply 'remap') can be described as a stochastic matrix R, where its entry r ok is the probability of guessing k when the observed mechanism output is o. With this representation, it can be easily seen that the probabilities of the user's guesses given individual query results are described by the matrix product X R. We say here that X is remapped to X R by the remap R. Note that this remapping procedure models the post-processing done by the user for the mechanism output o. Now, with the user's guessed value k, a real-valued gain function g

: (R f × R f ) → R quantifies how informative k is compared to the real result i.
The utility of a given mechanism to the user is described as the expected value of the gain function g. The evaluation of this expected value depends on the a priori probability distribution π over the real query results, which models the side knowledge of the user about the database. The utility of the mechanism depends therefore on the definition of the gain function g, the mechanism's underlying noise matrix X, the user's remap R, and also the probability distribution π over the real query results.

One choice for the gain function is the binary gain defined as g b (i, j) = 1 iff i = j and 0 otherwise. The binary gain function formalises the requirement of a user to guess the exact query result using the mechanism output. In the current work we restrict our analysis to this gain function. An important feature of this function, is that it is applicable to the ranges of various queries including numerical and non-numerical one. Moreover, it will be shown that this gain function is strongly connected to the information theoretic notions of conditional entropy and information leakage. Hence, our results about the utility of private mechanism imply corresponding results regarding quantifying information leaked by these mechanisms. These results go inline with a recent trend of research aiming at quantifying information leaked by security protocols, and privacy mechanisms specifically (see e.g. [START_REF] Köpf | Vulnerability bounds and leakage resilience of blinded cryptography under timing attacks[END_REF][START_REF] Andrés | Computing the leakage of information-hiding systems[END_REF][START_REF] Alvim | On the relation between Differential Privacy and Quantitative Information Flow[END_REF][START_REF] Barthe | Information-theoretic bounds for differentially private mechanisms[END_REF]). We leave considering other gain functions to future work. Now, for formulating the utility we represent the a priori probability distribution (called the 'prior') over the real query results by a row vector π, indexed by R f , where π i is the probability that the query in hand yields the result i. The prior is therefore relative to the user and depends on her knowledge. With a generic gain function g, the utility of a mechanism for a prior π using the remap R is denoted by U(X, π, R), and defined as follows.

U(X, π, R) = E g(i, k) = i,k π i (X R) ik g(i, k), ( 1
)
where X is the noise matrix of the given mechanism. In our case, where the binary gain function g b is used, the utility reduces to a convex combination of the diagonal elements of X R as follows.

U(X, π, R) = i π i (X R) ii . (2)
Accordingly, for a given prior π, an oblivious -differentially private mechanism, with a noise matrix X, is said to be optimal if and only if there is a remap R such that the above function is maximised over all -differentially private mechanisms and all remaps 1 . As exemplified in the introduction, the optimality of a mechanism depends, in general, on the prior (user); that is a mechanism can be optimal for a prior while it is not for another one. It has been proved by [START_REF] Brenner | Impossibility of differentially private universally optimal mechanisms[END_REF] that for arbitrary queries (except the counting ones), there is no such a mechanism that is optimal for all priors simultaneously. Nevertheless, we identify in the following section a region of priors, where it is possible to find a single mechanism which is optimal to all of them.

-Regular priors

In this section we describe a region of priors, called ' -regular'. These priors are determined by the given query f and privacy parameter . In our way to specify these priors, we first represent the -differential privacy constraints in a matrix form. By Proposition 1, observe that each -differential privacy constraint imposed on a noise matrix X can be written as x io /x ho ≥ e -d(i,h) . Since the lower bound e -d(i,h) depends only on i, h, all constraints can be described altogether by a square matrix Φ formed by such lower bounds. We refer to this matrix as the privacy-constraints matrix. Note that the rows, and also columns of Φ are indexed by the elements of R f , the set of query results.

Definition 4 (privacy-constraints matrix). The privacy-constraints matrix Φ of a query f with a range R f , and a privacy parameter > 0 is a square matrix, indexed by

R f × R f , where φ ih = e -d(i,h) for all i, h ∈ R f .
Note that Φ is symmetric (φ ih = φ hi ) due to the symmetry of the distance function d(i, h).

Observe that when → ∞, i.e. exclude privacy at all, Φ converges to the identity matrix where each diagonal entry is 1 and other entries are zeros. In terms of the privacyconstraints matrix of a query and , we define now the -regular priors as follows (note that we use y ≥ 0 to denote ∀i : y i ≥ 0).

Definition 5 ( -regular prior). For a given query f and a privacy parameter > 0, a prior π is called -regular iff there exists a row vector y ≥ 0 such that π = y Φ.

In the following we describe the common properties of these priors and also give a geometric characterisation for their region comparing it to the whole prior space. As the first observation, note that, as privacy is excluded ( → ∞), this region converges to the entire prior space. This is because Φ approaches the identity matrix where the vector y exists for each prior.

An important property of any -regular prior is that the ratio between any two of its entries π i , π j is always bound as follows, depending on and the distance d(i, j). Because of this property, such a prior is called -regular.

Proposition 2. Consider a query f and > 0. Then for any -regular prior π, it holds for all i, j ∈ R f : π i π j ≤ e d(i, j) .

While the above property restricts the ratio between probabilities of adjacent query results, this restriction, in practice, holds for a large class of users who have no sharp information suggesting discrimination between adjacent results. This class is exemplified in the introduction. Note that the above property is not equivalent to Definition 5. Namely, it is not true that all priors having such a property are -regular.

A consequence of the above proposition is that for any -regular prior π, the probability π i associated with any query result i is restricted by upper and lower bounds as follows.

Proposition 3. Consider a query f and > 0. Then for any -regular prior π, it holds for all i ∈ R f that

1 j∈R f e d(i, j) ≤ π i ≤ 1 j∈R f e -d(i, j
) . One implication is that any -regular prior must have full support, that is π i > 0 for all i ∈ R f .

In the following we go further and describe the region of -regular priors as a region of points in the prior space, where each point represents a member in this region. For doing so, we identify by the following definition a set of priors which describe the 'corner points' or vertices of the region. Definition 6 (corner priors). Given a query f and a privacy parameter > 0, then for each query result i ∈ R f , a corresponding corner prior, denoted by c i , is defined as

c i j = φ i j k∈R f φ ik ∀ j ∈ R f .
Note that the above definition is sound, i.e. c i is a probability distribution. By the above definition, for a given query with the domain R f of results, the region of -regular priors has |R f | corner priors. Each one corresponds to a query result i ∈ R f . Note that each corner prior c i is maximally biased (relative to the region) to the query result i; that is the entry c i i meets its maximum value given in Proposition 3. It can be seen that each corner prior is -regular. Namely for any corner c i , define the vector y as y i = 1/ k∈R f φ ik and y j = 0 for all j i; thus it holds that c i = y Φ.

The region of the -regular priors can be characterised in terms of the corner priors. More precisely, this region consists of all priors that can be composed as a convex combination of the corner priors.

(1,0,0) (0,1,0) (0,0,1) Proposition 4 (convexity). For a given a query f and privacy parameter > 0, a prior π is -regular iff there exist real numbers

c 1 c 2 c 3 e -= 0.5 e -= 0.2 e -= 0 f 1 (1,0,0) (0,1,0) (0,0,1)
γ i ≥ 0, i ∈ R f such that π = i∈R f γ i c i .
It is easy to see that it must hold that i∈R f γ i = 1 for any -regular prior. This is obtained by summing the components of the π as follows.

j∈R f π j = i γ i j c i j and j π j = 1, ∀π.

From Proposition 4 and the above observation, the region of -regular priors is a convex set, where each point (prior) in this region is a convex combination of the corner priors. This region is therefore geometrically regarded as a convex polytope in the prior space.

Since the corner points always exists, this region is never empty. For a prior π in this region, the coefficients γ i model the 'proximity' of π to each corner prior c i . Observe that 0 ≤ γ i ≤ 1, and γ i = 1 iff π = c i . We demonstrate this geometric interpretation using the following examples.

Example 1. Priors having 3 entries can be represented as points in the 3-dimensional euclidean space. These priors correspond to queries whose graph structures contain 3 nodes. These nodes can be arranged in either a sequence or a cycle, corresponding to queries f 1 and f 2 respectively shown in Figure 1, with n = 2 in both cases. Figure 2 shows -for each of these queries -the region of -regular priors. The corner priors of each region are represented by points c 1 , c 2 , c 3 . For each query in Fig. 2, we depict the regions for e -= 0.5 and e -= 0.2. Note that the level of privacy set by imposes a restriction on the region of -regular priors. With e -= 0.2 (less privacy), this region is larger than the one with e -= 0.5. In fact, as e -→ 0 (i.e. no privacy), the region of -regular priors converges to the entire region of priors defined by the corner points {(0, 0, 1), (0, 1, 0), (0, 0, 1)}. Example 2. Let v be database containing at most one record. Consider a bundle of two counting queries f 3 = (count(v, p 1 ), count(v, p 2 )) which counts the records satisfying properties p 1 and p 2 respectively in the database v. The graph structure of this query is depicted in Figure 1 (with n = 1). Note that in this case the adjacency graph (and also the set R f of query results) consists of 4 nodes: {(0, 0), (1, 0), (0, 1), (1, 1)}. Any prior π corresponds therefore to a point in a 4-dimensional space. However, since the 4th component of the prior is redundant ( i π i = 1), each prior is defined by its 'projection' onto the 3-dimensional subspace. Given this observation, Figure 3 shows the projection of the -regular prior region for different values of e -. It is again seen that the region is getting larger as the level of privacy e -decreases, and coincides with the full space of priors when e -→ 0 (i.e. when no privacy is provided).

Upper bounds for utility and min-mutual information

In this section, we further describe the -regular priors in terms of the utility that can be achieved for these priors by -differentially private mechanisms. We also describe the amount of information that can be conveyed by these mechanisms to users with such priors. More precisely, we identify for any -regular prior π upper bounds for the utility and min-mutual information, considering all -differentially private mechanisms and all possible remaps. These bounds are indeed induced by the privacy constraints parameterised by and the query f as stated by Proposition 1. They also depend on the given prior π.

Utility

Given a query f and a privacy parameter > 0, let π be a prior on the set R f of the query results. For any noise matrix X satisfying -differential privacy (as in Proposition 1), and a remap R, we derive in the following a linear algebraic expression for U(X, π, R), the utility of X for π using the remap R. Such an expression will play the main role in the subsequent results. We start by observing that the matrix product of the noise matrix X and the remap R describes an -differentially private noise matrix X R : R f → R f . Hence the entries of X R satisfy (by Proposition 1) the following subset of constraints.

e -d(i,k) (X R) kk ≤ (X R) ik
for all i, k ∈ R f . Using Definition 4 of the privacy-constraints matrix Φ, and taking into account that k∈R f (X R) ik = 1 for all i (as both X and R are stochastic), we imply the following inequalities.

k∈R f φ ik (X R) kk ≤ 1, ∀i ∈ R f .
The inequality operators can be replaced by equalities while introducing slack variables 0 ≤ s i ≤ 1 for all i ∈ R f . The above inequalities can therefore be written as follows.

k∈R f φ ik (X R) kk + s i = 1, ∀i ∈ R f .
Let the slack variables s i form a column vector s indexed by R f . Let also 1 denote another column vector of the same size having all entries equal to 1. Using these vectors and the privacy-constraints matrix Φ (for the given query and ), the above equations can be rewritten in the following matrix form.

Φ diag(X R) + s = 1, (3)
where diag(X R) is the column vector consisting of the diagonal entries of X R. Now, for any noise matrix X : R f → O and a remap R : O → R f satisfying Eq. ( 3), and for a prior π, we want to refine the generic expression (2) of the utility by taking Eq. (3) into account. We start by rewriting Eq. ( 2) in the following matrix form.

U(X, π, R) = π diag(X R). (4)
Now, let y be a row vector such that π = y Φ.

Note that, the above matrix equation is in fact a system of |R f | linear equations. The kth equation in this system is formed by the kth column of Φ, and the kth entry of π as follows.

y Φ k = π k ∀k ∈ R f .
Solving this system of equations for the row vector y has the following possible outcomes: If the matrix Φ is invertible, then, for any prior π, Eq. ( 5) has exactly one solution. If Φ is not invertible (i.e. it contains linearly dependent columns), then there are either 0 or an infinite number of solutions, depending on the prior π: If the entries of π respect the linear dependence relation then are infinitely many solutions. Otherwise, the equations are 'inconsistent', in which case there are no solutions.

Since the matrices Φ have a precise format, one may wonder whether it could be that they are all invertible or all non invertible. In fact, this is not the case: In Appendix B we show an example of a matrix Φ that, for certain values of is invertible, while for others is non invertible.

Whether Φ is invertible or not, we consider here only the priors where the matrix equation ( 5) has at least one solution y. Note that, by definition, all the -regular priors have this property, but there can be others for which the solution y has some negative components. In some of the results below (in particular in Lemma 2) we consider this larger class of priors, for the sake of generality.

Multiplying Equation ( 3) by y yields

y Φ diag(X R) + y s = y 1. (6)
Substituting Equations ( 5) and (4) in the above equation consecutively provides the required expression for the utility and therefore proves the following lemma.

Lemma 2. For a given query f and a privacy parameter > 0, let π be any prior. Then for every row vector y satisfying π = y Φ, the utility of any -differentially private mechanism with a noise matrix X for the prior π using a remap R is given by

U(X, π, R) = y 1 -y s, (7)
for a vector s satisfying 0 ≤ s i ≤ 1 for all i ∈ R f .

Lemma 2 expresses the utility function for any -private noise matrix X for a prior π with a remap R as a function of the vector y and the slack vector s. Although the matrix X and the remap R do not explicitly appear on the right hand side of Equation ( 7), the utility still depends on them indirectly through the vector s. Namely, according to Equation (3), the choice of X and R determines the slack vector s. The utility function depends also on the prior π, because the choice of π determines the set of vectors satisfying Eq. ( 5). Substituting any of these vectors y in Eq. ( 7) yields the same value for U(X, π, R). By Definition 5, of -regular priors, the above lemma specifies the utility for any of them. Therefore, we use Lemma 2, and obtain an upper bound for the utility ofdifferentially private mechanisms for -regular priors.

Theorem 1 (utility upper bound). For a given query f and a privacy parameter > 0, let π be an -regular prior and X be an -differentially private noise matrix. Then for all row vectors y ≥ 0 satisfying y Φ = π, it holds for any remap R that

U(X, π, R) ≤ i∈R f y i , (8)
where the equality holds iff Φ diag(X R) = 1.

The above result can be also seen from the geometric perspective. As shown by Proposition 4, each member in the region of -regular priors is described as a convex combination of the corner priors. That is there are coefficients γ i ≥ 0 for i ∈ R which form this combination. It can be shown (as in the proof of Proposition 4) that γ i = y i k∈R f φ ik . Hence, the upper bound given by Theorem 1 can be written as follows using the coeffi-

cients γ i . U(X, π, R) ≤ i∈R f γ i k∈R f φ ik .
Inspecting the above result for corner priors, recall that for a corner c i , γ j is 1 for j = i and is 0 otherwise; thus, the utility upper bound for c i is therefore 1/ k φ ik . Moreover, the upper bound for each -regular prior π can be regarded (according to the above equation) as a convex combination of the upper bounds for the corner priors. That is, from the geometric perspective, the utility upper bound for π linearly depends on its proximity to the corner priors.

Min-mutual information

In this section, we employ an information-theoretic notion, namely mutual information, to quantify the amount of information conveyed by a noise matrix X as an information theoretic channel. We use this notion in two distinct ways: first, mutual information is used to measure the information conveyed about the result of a specific query, similarly to the use of "utility" in the previous section. Mutual information and utility (under the binary gain function) are closely related, which allows us to transfer the bound obtained in the previous section to the information-theoretic setting.

Second, we use mutual information to quantify the information about the database that is revealed by a mechanism, a concept known in the area of quantitative information flow as "information leakage". This allows us to obtain bounds on the information leaked by any mechanism, even non-oblivious ones, independently from the actual query. For arbitrary priors, we obtain in a more natural way the bound conjectured in [START_REF] Barthe | Information-theoretic bounds for differentially private mechanisms[END_REF] and proven in [START_REF] Alvim | On the relation between Differential Privacy and Quantitative Information Flow[END_REF]. Moreover, if we restrict to specific ( -regular) priors, then we are able to provide more accurate bounds.

Following recent works in the are of quantitative information flow ([14-17, 8, 18]), we adopt Rényi's min-entropy ( [START_REF] Rényi | On Measures of Entropy and Information[END_REF]) as our measure of uncertainly. The min-entropy H ∞ (π) of a prior π, defined as H ∞ (π) =log 2 max i π i , measures the user's uncertainty about the query result. Then, the corresponding notion of conditional min-entropy, defined as H ∞ (X, π) =log 2 o max i π i x io , measures the uncertainty about the query result after observing the output of the noise matrix X. Finally, subtracting the latter from the former brings us to the notion of min-mutual information:

L(X, π) = H ∞ (π) -H ∞ (X, π)
which measures the amount of information about the query result conveyed by the noise matrix. In the area of quantitative information flow this quantity is known as min-entropy leakage; the reader is referred to [START_REF] Smith | On the foundations of quantitative information flow[END_REF] for more details about this notion.

Min-mutual information is closely related to the notion of utility under the binary gain function and using an optimal remap. A remap R is optimal for X, π if it gives the best utility among all possible remaps for this noise matrix and prior. The following result from [START_REF] Alvim | On the relation between Differential Privacy and Quantitative Information Flow[END_REF] connects min-mutual information and utility: Proposition 5. Given a noise matrix X and a prior π, let R be an optimal remap for π, X. Then, it holds

L(X, π) = log 2 U(X, π, R) max i π i
This connection allows us to transfer the upper-bound given by Theorem 1 to minmutual information.

Proposition 6 (min-mutual information upper bound). Let f be a query, let > 0, let π be an -regular prior and let X be the noise matrix of any -differentially private mechanism. Then for all row vectors y ≥ 0 satisfying y Φ = π, it holds that:

L(X, π) ≤ log 2 i∈R f y i max i π i (9)
The above bound holds only for -regular priors. However, it is well-known ( [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF]) that min-mutual information is maximised by the uniform prior u, i.e. L(X, π) ≤ L(X, u) for all X, π. Thus, in cases when u is -regular, we can extend the above bound to any prior.

Corollary 1. Let f be a query, let > 0 such that the uniform prior u is -regular, and let X be the noise matrix of any -differentially private mechanism. Then for all row vectors y ≥ 0 satisfying y Φ = u, and for all priors π, it holds that:

L(X, π) ≤ log 2 (|R f | i∈R f y i )

Quantifying the leakage about the database

In the previous section we considered the information about the query result conveyed by an oblivious mechanism. This information was measured by the min-mutual information L ( X, π), where X is noise matrix, mapping query results R f to outputs.

We now turn our attention to quantifying the information about the database that is conveyed by the complete mechanism K (even in the case of non-oblivious mechanisms). Intuitively, we wish to minimise this information to protect the privacy of the users, contrary to the utility which we aim at maximising. Quantifying this information can be done in a way very similar to the previous section. The only difference is that we use a stochastic matrix Y that models the mechanism K, mapping databases V = V u to outputs (recall that u is the number of individuals in the database and V the set of possible values for each individual). Moreover, the underlying graph ∼ is the Hamming graph, induced by the adjacency relation on databases, and -regularity concerns priors π on databases.

In this case, L(Y, π) measures the information about the database conveyed by the mechanism, which we refer to as "min-entropy leakage", and the bounds from the previous section can be directly applied. However, since we now work on a specific graph (V, ∼), we can obtain a closed expression for the bound of Corollary 1. We start by observing that due to the symmetry of the graph, the uniform prior u is -regular for all > 0. More precisely, we can show that the vector y, defined as

y i = e |V|(|V| -1 + e ) u i ∈ V
satisfies yΦ = u and y ≥ 0. Thus, applying Corollary 1 we get the following result.

Theorem 2 (min-entropy leakage upper bound). Let V = V u be a set of databases, let > 0, and let Y be an -differentially private mechanism. Then for all priors π, it holds that: This bound determines the maximum amount of information that any differentially privacy mechanism can leak about the database (independently from the underlying query). The bound was first conjectured in [START_REF] Barthe | Information-theoretic bounds for differentially private mechanisms[END_REF] and independently proven in [START_REF] Alvim | On the relation between Differential Privacy and Quantitative Information Flow[END_REF]; our technique gives an alternative an arguably more intuitive proof of this result.

L(Y, π) ≤ u log 2 |V| e |V| -1 + e 1 1.
Note that the above bound holds for all priors. If we restrict to a specific -regular prior π, then we can get better results by using the bound of Proposition 6 which depends on the actual prior. This is demonstrated in the following example.

Example 3. Consider a database of 5 individuals, each having one of 4 possible values, i.e. V = V u with V = {1, 2, 3, 4} and u = 5. Assume that each individual selects a value independently from the others, but not all values are equally probable; in particular the probabilities of values 1, 2, 3, 4 are 0.3, 0.27, 0.23, 0.2 respectively. Let π be the corresponding prior on V that models this information. We have numerically verified that for all 0.48 ≤ ≤ 1 (with step 0.01) π is -regular. Thus we can apply Proposition 6 to get an upper bound of L(Y, π) for this prior.

The resulting bound, together with the general bound for all priors from Theorem 2, are shown in Figure 4. We see that restricting to a specific prior provides a significantly better bound for all values of . For instance, for = 0.5 we get that L(Y, π) ≤ 1.2 for this π, while L(Y, π) ≤ 2.5 for all priors π. Note that, in general, the above bounds for the utility and the min-mutual information are not tight. For a given query and a privacy parameter , there may be no noise matrix X that meets these bounds. Nevertheless, they provide ultimate limits, induced by the privacy constraints, for all -differential private mechanisms and -regular priors. Note also that these bounds are simultaneously tight if the common condition Φ diag(X R) = 1 is satisfied (note that this condition is independent of the underlying prior). From this point we investigate the mechanisms that, whenever exist, they satisfy such a condition and are therefore optimal for the entire class of -regular priors.

Tight-constraints mechanisms

In this section, we introduce the notion of tight-constraints mechanism. We start by giving the definition of these mechanisms for a given query f and privacy parameter > 0. Then we describe their properties in terms of privacy guarantees and optimality for -regular priors.

Definition 7 (A tight-constraints mechanism). For a given query f with range R f , and a given privacy parameter > 0, an oblivious mechanism with a noise matrix X : R f → R f is called a tight-constraints mechanism iff it satisfies the following conditions for all i, k ∈ R f . e -d(i,k) x kk = x ik .

It is important to note that, in general, there may exist zero, one or more tight-constraints mechanisms for a given query f and a privacy parameter > 0. The above definition enforces |R f | (|R f | -1) linearly independent equations, referred to as the 'tight constraints'. Additionally it must also hold that k∈R f x ik = 1 for all i ∈ R f . Thus we have, in total, |R f | |R f | equations. If these equations are linearly independent, then they solve to unique values. If these values are non-negative, then they determine a unique tight-constraints mechanism. On the other hand, if these equations are not linearly independent, then there may be multiple solutions with non-negative entries, in which case we have multiple tight-constraints mechanisms for the given query and privacy parameter .

Properties

It has been seen from Definition 7, that the choice of a query f and a value > 0 correspond to a set of tight-constraints mechanisms. The first important feature of these mechanisms is that they satisfy -differential privacy as confirmed by the following proposition.

Proposition 7 (differential privacy). For a given query f and a privacy parameter > 0, every tight-constraints mechanism is -differentially private.

Thanks to the above fact, we can give a further useful characterisation of the tightconstraints mechanisms in comparison to other -differentially private mechanisms. More precisely, the following proposition identifies a linear algebraic condition that is satisfied only by the tight-constraints mechanisms for given f, :

Lemma 3 (diagonal characterisation). Let f be a query and let > 0. Then for any oblivious -differentially private mechanism K with a noise matrix X : R f → R f , the following equation holds iff K is a tight-constraints mechanism.

Φ diag(X) = 1. (11)
Observe that the above proposition provides a way to check the existence of, and also compute, the tight-constraints mechanisms for given f, . Since Condition ( 11) is satisfied only by these mechanisms, then there is at least one tight-constraints mechanism if there is a vector z, with non-negative entries, that satisfies the equation Φ z = 1. In this case the noise matrix X of a tight-constraints mechanism is obtained by setting its diagonal to z, and evaluating the non-diagonal entries from the diagonal using Equations [START_REF] Clark | Quantitative information flow, relations and polymorphic types[END_REF].

Now we turn our attention to the region of -regular priors and we identify the oblivious mechanisms which are optimal wrt both utility and min-mutual information in this region. It turns out that the set of these optimal mechanisms consists exactly of all the mechanisms that can be mapped to a tight-constraints mechanism using a remap R.

Theorem 3 (Optimality). Let f be a query and let > 0 such that at least one tightconstraints mechanism exists. Then any oblivious mechanism K : V → O is optimal (wrt both utility and min-mutual information) for every -regular prior π iff there is a remap R : O → R f such that K R is a tight-constraints mechanism for f, .

Proof. If there exists a tight-constraints mechanism for given f, , then its noise matrix X must satisfy Eq [START_REF] Boreale | Quantifying information leakage in process calculi[END_REF]. This implies that the upper-bound in Theorem 1 is reachable by X and the identity remap. Thus that upper-bound, in this case, is tight. By Theorem 1, a mechanism K with a noise matrix X meets such an upper bound for the utility (and therefore is optimal) iff it satisfies the condition Φ diag(X R) = 1, with some remap R. Since any mechanism with noise matrix X R is -differentially private, then by Lemma 3, this condition is satisfied iff X R is the noise matrix of a tight-constraints mechanism (for f, ). That is iff f X R = K R is a tight-constraints mechanism. Using the relation, given by Proposition 5, between utility and min-mutual information, the same argument holds for the latter.

Note that tight-constrains mechanisms are themselves optimal as they are mapped to themselves by the identity remap.

As a consequence of the above general result, we consider the special case of the uniform prior, denoted by u, where all exact query results in R f are equally likely. Note that this prior corresponds to users having unbiased knowledge about the query results, i.e. they assume that all the exact results R f are yielded, by executing the query, with the same probability. Firstly, the following lemma proves an equivalence between the existence of at least one tight-constraints mechanism on one hand and the uniform prior u being -regular on the other hand.

Lemma 4. For a given query f and privacy parameter > 0, there exists at least one tight-constraints mechanism iff the uniform prior u is -regular.

It is worth noticing that in general the region of -regular priors may or may not include the uniform prior. However, as shown earlier in Section 3, this region is enlarged and converges to the entire prior space as less privacy is imposed (that is as increases). This means that for the values of above certain threshold * , depending on the query, the region of -regular priors accommodates the uniform prior u, and therefore (by Lemma 4), there is at least one tight-constraints mechanism. This provides a design criteria to select a setting for such that we have an optimal mechanism for the whole region.

Using Lemma 4, we can describe the optimal mechanisms for the uniform prior as a corollary of Theorem 3. Corollary 2. Let f be a query and let > 0 such that there exists at least one tightconstrains mechanism. Then a mechanism K : V → O is optimal for the uniform prior iff K R is a tight-constraints mechanism for some remap R : O → R f .

(0,u) (1,u) (2,u) (u,u) (0,2) (1,2) (2,2) (u,2) (0,1) (1,1) (2,1) (u,1) (0,0) (1,0) (2,0) (u,0) (b) 2-count query
In fact when we consider arbitrary queries, we find that our specification for the tight-constraints mechanisms covers other well known differentially-private mechanisms. In particular, when we consider a counting query, we find that a tight-constraints mechanism for this query is exactly the truncated-geometric mechanism, which is shown by [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] to be optimal for every prior. Furthermore, we are able to show that this mechanism, as a tight-constraints one, exists for the selected query with any > 0.

Another class of queries, studied in [START_REF] Alvim | On the relation between Differential Privacy and Quantitative Information Flow[END_REF] are the ones whose graph structures are either vertex-transitive or distance-regular. The authors in [START_REF] Alvim | On the relation between Differential Privacy and Quantitative Information Flow[END_REF] were able to construct a mechanism which is optimal for the uniform prior for any > 0. In the context of our results, when we consider a query f in this class, it is easy to show that such an optimal mechanism is in fact a tight-constraints mechanism for f . We can also show that this tight-constraints mechanism exists for all > 0.

6 Case-study: sum and 2-count queries

In this section we show the usefulness of the tight-constraints mechanism by applying it to two particular families of queries, namely sum and 2-count queries. For each family, we evaluate the tight-constraint mechanism on databases consisting of u individuals each having an integer value between 0 and v, and we compare its utility to the geometric mechanism.

It is well-known that no universally optimal mechanism exists for these families; in particular, the geometric mechanism, known to be optimal for a single counting query, is not guaranteed to be optimal for sum or multiple counting queries. On the other hand, as discussed in the previous section, tight-constraints mechanisms, whenever they exist, are guaranteed to be optimal within the region of -regular priors.

The comparison is made as follows: for each query, we numerically compute the smallest (using a step of 0.01) for which a tight-constraints mechanism exists (i.e. for which the uniform prior u is -regular, see Lemma 4). Then we compute the utility (using an optimal remap) of both the tight constraints and the geometric mechanisms, for a range of starting from the minimum one (note that the tight constraint mechanism exists for any greater than the minumum one).

Sum query Let f be the query returning the sum of the value for all individuals, thus it has range R f = {0, . . . , vu}. By modifying the value of a single individual, the outcome of the query can be altered by at most v (when changing the value from 0 to v), thus two elements i, j ∈ R f are adjacent iff |i -j| ≤ v. The induced graph structure on R f is shown in Figure 5(a) (for the case v = 3).

For our case-study we numerically evaluate this query for u = 150, v = 5 and for the uniform prior. We found that the minumum for which a tight-constraints mechanism exists (and is in fact unique since Φ is invertible) is 0.8. Figure 6(a) shows the utility of the tight-constraint mechanism, as well as that of the geometric mechanism, for values of between 0.8 and 1.3, the uniform prior and using and optimal remap. We see that the tight-constraint mechanism provides significantly higher utility than the geometric mechanism in this case.

2-count query

Consider now the query f consisting of 2 counting queries (i.e. reporting the number of users satisfying properties p 1 and p 2 ), thus it has range R f = {0, . . . , u} × {0, . . . , u}. By modifying the value of a single individual, the outcome of each counting query can be altered by at most 1, thus two anwers (i 1 , i 2 ), (

j 1 , j 2 ) ∈ R f are adjacent iff |i 1 -j 1 | ≤ 1 and |i 2 -j 2 | ≤ 1. The induced graph structure on R f is shown in Figure 5(b).
We evaluate this query for u = 30 and for the uniform prior. We found that the minumum for which a tight-constraints mechanism exists is 0.9. Figure 6(b) shows the utility of the tight-constraint mechanism, as well as that of the geometric mechanism (applied independently to each counting query), for values of between 0.9 and 1.3 and the uniform prior. Similarly to the sum query, we see that the tight-constraint mechanism provides significantly higher utility than the geometric mechanism in this case.

Conclusion and future work

In this paper we have continued the line of research initiated by [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF][START_REF] Brenner | Impossibility of differentially private universally optimal mechanisms[END_REF] about the existence of universally-optimal differentially-private mechanisms. While the positive result of [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] (for counting queries) and the negative one of [START_REF] Brenner | Impossibility of differentially private universally optimal mechanisms[END_REF] (for essentially all other queries) answer the question completely, the latter sets a rather dissatisfactory scenario for differential privacy and the typical mechanisms used in the community, since counting queries are just one of the (infinitely many) kinds of queries one can be interested in. In practice the result of [START_REF] Brenner | Impossibility of differentially private universally optimal mechanisms[END_REF] says that for any query other than counting queries one cannot devise a mechanism that gives the best trade-off between privacy and utility for all users. Hence one has to choose: either design a different mechanism for every user, or be content with a mechanism that, depending on the user, can be far from providing the best utility. We have then considered the question whether, for a generic query, the optimality is punctual or can actually be achieved with the same mechanism for a class of users. Fortunately the answer is positive: we have identified a class of priors, called -regular, and a mechanism which is optimal for all the priors in this class. We have also provided a complete and effectively checkable characterisation of the conditions under which such mechanism exists, and an effective method to construct it. As a side result, we have improved on the existing bounds for the min-entropy leakage induced by differential privacy. More precisely, we have been able to give specific and tight bounds for each -regular prior, in general smaller than the bound existing in literature for the worst-case leakage (achieved by the uniform prior [START_REF] Alvim | Differential Privacy: on the trade-off between Utility and Information Leakage[END_REF]).

So far we have been studying only the case of utility for binary gain functions. In the future we aim at lifting this limitation, i.e. we would like to consider also other kinds of gain. Furthermore, we intend to study how the utility decreases when we use a tight-constraints mechanism outside the class of -regular priors. In particular, we aim at identifying a class of priors, larger than the -regular ones, for which the tightconstraints mechanism is close to be optimal.

The definition of tight-constrains mechanism is related to the connectivity condition of the column graphs introduced by Kifer and Lin [START_REF] Kifer | Towards an axiomatization of statistical privacy and utility[END_REF][START_REF] Kifer | An axiomatic view of statistical privacy and utility[END_REF]. They show that this property implies maximality w.r.t. the postprocessing preorder. As pointed out by an anonymous reviewer, we can probably exploit this result to strengthen our results in Section 5, in particular Theorem 3.

The negative result of [START_REF] Brenner | Impossibility of differentially private universally optimal mechanisms[END_REF] is stated in terms of the graph induced by ∼ f : a universally optimal mechanism can exist only if such graph is a line. This is the case of counting queries, but not only: any composition of a counting query with a function that preserves the graph structure would induce the same kind of graph, and it's for this reason that the authors of [START_REF] Brenner | Impossibility of differentially private universally optimal mechanisms[END_REF] write "essentially counting queries". As pointed out by an anonymous reviewer, we can use the techniques of our paper to prove that a universally optimal mechanism exists if and only if the query is derivable from a counting query by a bijection, thus making the result of [START_REF] Brenner | Impossibility of differentially private universally optimal mechanisms[END_REF] more precise, and extending the result of [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF].

The direction '⇐' is proved by restricting the right statement to pairs i, h having distance d(i, h) = 1. The other implication '⇒' is proved by induction on the distance between graph nodes: For all i, h where d(i, h) = 1, it holds that x io ≤ e d(i,h) • x ho ∀o.

(

) 16
Now we set our hypothesis that Inequality ( 16) holds for all i, h where d(i, h) = d, and then prove that the hypothesis holds for distance d + 1. For any node u at distance d + 1 from i, there is an adjacent node h (to u) such that d(i, h) = d. Then we have

x io ≤ e d • x ho and x ho ≤ e x uo .

Thus, we obtain x io ≤ e (d+1) • x uo That is, the hypothesis ( 16) holds for all pairs i, u having distance d(i, u) = d + 1.

Proof of Proposition 2:

Proof. By Definition 5, the ratio π i /π j is given by

π i π j = k y k φ ki k y k φ k j (17)
where φ k j = e -d(k, j) ≥ e -d(k,i)+d(i, j) = e -d(i, j) • φ ki

The above inequality is implied by the triangle inequality, d(k, j) ≤ d(k, i) + d(i, j) and the fact that e -< 1. Since y k ≥ 0 for all k, it holds that k y k φ k j ≥ e -d(i, j) • k y k φ ki Substituting the above inequality in Eq. ( 17) completes the proof.

Proof of Proposition 3:

Proof. By Proposition 2, it holds for any pair of entries π i , π j that π j ≤ e d(i, j) • π i and e -d(i, j) • π i ≤ π j .

Summing the above inequalities over j, we get j π j ≤ π i • j e d(i, j) and π i j e -d(i, j) ≤ j π j .

Since j π j = 1, the above inequalities imply the upper and lower bounds for π i .

Proof of Proposition 4:

Proof. By Definition 5, a prior π is -differentially informative if and only if there exists vector y such that π = y Φ and y i ≥ 0 for all i ∈ R f ; that is if and only if there are reals y i ≥ 0 for all i ∈ R f , such that π can be written as a linear combination Φ's rows as follows.

π = i∈R f y i Φ i ,
where Φ i is the row of Φ corresponding to the query result i. By Definition 6, observe that each row Φ i is equal to k∈R f φ ik c i . Now substitute this expression in the above equation for π, and let γ i = y i k∈R f φ ik . Note that γ i ≥ 0 if and only if y i ≥ 0 for all i ∈ R f . Thus we conclude that the condition given by the proposition is equivalent to the condition given by Def. 5.

Proof of Theorem 1:

Proof. Since π is -regular, then it holds π = y Φ for a vector y where y i ≥ 0 for all i ∈ R f . Applying Lemma 2 and noting that s i ≥ 0 for all i ∈ R f , we observe that y s ≥ 0 and hence the utility is upper-bounded by y 1 = i∈R f y i . Note also that this bound is met if and only if all entries of the slack vector s in Eq. ( 7) are 0, because y i ≥ 0 for all entries i. By Eq. ( 3), the condition s = 0 is equivalent to Φ • diag(X • R) = 1.

Proof of Proposition 6:

Proof. By Proposition 5, the leakage L(X, π) is monotonically increasing with the utility U(X, π, R). By Theorem 1, this utility is upper-bounded by i∈R f y i substituting this upper bound in Proposition 5 yields the inequality [START_REF] Köpf | An information-theoretic model for adaptive side-channel attacks[END_REF] where the equality holds if and only if it also holds in Theorem 1 for X and R. That is if and only if Φ diag(X R) = 1. This condition is equivalent to the condition of equality in Proposition 6, because if a remap R satisfies this latter condition then it must be optimal as the utility with R (by Theorem 1) is globally maximum, that is no other remap can achieve higher utility.

Proof of Proposition 7:

Proof. For the noise matrix X of a tight-constraints mechanism, we want to show (according to Proposition 1) that for every pair of query results i, h and every output o, it holds that xio ≤ e d(i,h) • xho . Consider the matrix Φ defined by φ ih = α d(v i ,v h ) , where α = e -. It is easy to see that if α = 1 /3, then the matrix is not invertible. In fact, if we denote by c i the row corresponding to the node v i , we have

c 0 + c 2 + c 4 + c 6 = c 1 + c 3 + c 5 + c 7
This can be easily proved by observing that for each position of the vectorial sum one side of the equation is 1 + 3 α 2 while the other is 4 α.

On the other hand, there are values of α for which Φ is invertible. For instance for α ≤ 1 /7 it is possible to show that the columns are linearly independent. Intuitively, this is because the elements which are not in the diagonal are too small to sum up to the diagonal. Note also that as α approaches 0 the matrix Φ approaches the identity matrix.

2 Fig. 2 .

 22 Fig. 2. Regions of -regular priors for queries described in Example 1

Fig. 3 .

 3 Fig. 3. Regions of -regular priors for the query described in Example 2

5

 5

Fig. 4 .

 4 Fig. 4. Leakage bounds for various values of

Fig. 5 .

 5 Fig. 5. Adjacency graphs

( 18 )

 18 By Definition 7 it holds for every pair of nodes i, h and every output o, thatxho = e -d(h,o) • xoo and xio = e -d(i,o) • xoo . (19)If xoo = 0 then xho = xio = 0. In this case, Condition (18) is satisfied. On the other hand, if xoo 0, then both xho and xio are non-zero, and it follows from Equations (19) that, for every inputs i and h, and every output o,xho xio = e -(d(h,o)-d(i,o)) .By the triangle inequality, it holds that d(h, o)d(i, o) ≤ d(i, h). Knowing also that e -< 1, it follows from the above inequality that xho xio ≥ e -d(i,h) .The above inequality implies Condition (18) of differential privacy.

2 Fig. 7 .

 27 Fig. 7. The set of query results R f and its adjacency relation

This work is partially funded by the Inria large scale initiative CAPPRIS, the EU FP7 grant no. 295261 (MEALS), and the project ANR-09-BLAN-0169-01 (PANDA).

Note that there may exist many optimal mechanism for a given prior.

Ehab ElSalamouny, Konstantinos Chatzikokolakis, and Catuscia Palamidessi

Acknowledgement We would like to thank the anonymous reviewers for their invaluable recommendations for improving the paper, and their suggestion for future work.

Appendix A Proofs

Proof of Lemma 1:

Proof. Assuming K is oblivious, then by Definition 1, the -differential privacy of K is written as follows.

Since the query f is deterministic, P(r | v) = 1 if r = f (v), and is 0 otherwise. Therefore, Condition ( 12) is written as follows.

Now we express the above condition in terms of adjacent query results instead of adjacent databases. For any pair of query results i, h such that i ∼ f h, there exists (by Def.

3) a pair of databases v, v such that

Repeating the same argument for all pairs of adjacent query results we get

We also imply Condition ( 13) from [START_REF] Smith | On the foundations of quantitative information flow[END_REF] as follows. For any pair of adjacent databases

, and hence applying Condition [START_REF] Smith | On the foundations of quantitative information flow[END_REF]

) then this ratio is 1 which is strictly less than e . Repeating the same argument for all pairs of adjacent databases we get Condition [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF]. It holds therefore that ( 13) is equivalent to [START_REF] Smith | On the foundations of quantitative information flow[END_REF]. It remains to show that ( 14) is equivalent to

For all o ∈ O, applying ( 14) to the subsets S = {o} , we easily get [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF]. Now we consider the other direction of implication. Note that it holds for any subset S ⊆ O and query result i that P(S | i) 15) holds. Then it holds for any subset S and any adjacent query results i, h that P(S | i) ≤ e o∈S P(o | h) = e P(S | h), and hence ( 14) is implied by quantifying over all possible subsets and adjacent query results.

Proof of Proposition 1:

Proof. Using the characterisation of -differential privacy given by Lemma 1, it is enough to prove the following equivalence for all outputs o ∈ O.

Proof of Lemma 3:

Proof. If a mechanism K is a tight-constraints mechanism, then it holds for its noise matrix X, by Def. 7 that x ik = e -d(i,k) x kk for all i, k ∈ R f . It also holds that k∈R f x ik = 1 for all i ∈ R f . Combining these equations yields

Using the privacy-constraints matrix Φ, the above equations can be written in the matrix form [START_REF] Boreale | Quantifying information leakage in process calculi[END_REF]. Now let X be the noise matrix of any -differentially private mechanism K. We prove that if X satisfies Equation ( 11) then K must be a tight-constraints mechanism. Note that if X satisfies Equation [START_REF] Boreale | Quantifying information leakage in process calculi[END_REF], then there must be a tight-constraints mechanism X having the same diagonal as X. Suppose for a contradiction that X deviates from X in the values of non-diagonal entries. Deviating the mechanism X, which satisfies Eqs. [START_REF] Clark | Quantitative information flow, relations and polymorphic types[END_REF], to another mechanism X while keeping the same diagonal requires increasing at least one non-diagonal entry x ik to preserve the differential privacy condition x ik ≥ e -d(i,k) x kk . This increment of x ik has to be deducted from one or more entries in the same row i. Let x i j be any of these decremented entries. To preserve the privacy condition x i j ≥ e -d(i, j) x j j we have to decrease the diagonal entry x j j . The change of x j j contradicts that the diagonals of X and X are the same.

Proof of Lemma 4:

Proof. By Lemma 3, if there is at least a tight-constraints mechanism, then Eq. ( 11) must hold for this mechanism's noise matrix X. Taking the transpose of both sides in this equation, and noting that Φ t = Φ (because Φ is symmetric), then we imply that

Scaling the above equation by 1/|R f | yields the row vector u, the uniform prior, on the right hand side. Thus if a tight-constraints mechanism, with noise matrix X, exists then

which means (By Def. 5) that u is -regular, because the row vector (diag( X)) t has only non-negative entries. For the opposite implication, assume that u is -regular. Then by definition there is a row vector y with non-negative entries such that y Φ = u. Taking the transpose of both sides, and multiplying by |R f |, yields that Eq. ( 11) is satisfied for the noise matrix X, whose diagonal is given by diag(X) = |R f | • y t (non-negative). Thus there exists a tight-constraints mechanism whose noise matrix is X.

B On the invertibility of the privacy-constraints matrix

In this section we show that the matrix Φ introduced in Definition 4 can be both invertible or not invertible. Assume that the set of query results R f , and its adjacency relation, are given by the graph represented in Fig. 7, which is obtained by the Hamming graph 2 3 by adding an