Estimating g-Leakage via Machine Learning

• •

  We propose a novel approach to the black-box estimation of $g$-vulnerability based on ML. To the best of our knowledge, this is the first time that a method to estimate $g$-vulnerability in a black-box fashion is introduced.

• •

  We provide statistical guarantees showing the learnability of the $g$-vulnerability for all distributions and we derive distribution-free bounds on the accuracy of its estimation.

• •

  We validate the performance of our method via several experiments using k-NN and ANN models. The code is available at the URL https://github.com/LEAVESrepo/leaves.

One important aspect to keep in mind when measuring leakage is the kind of attack that we want to model. In (Köpf and Basin, 2007), Köpf and Basin identified various kinds of adversaries and showed that they can be captured by known entropy measures. In particular it focussed on the adversaries corresponding to Shannon and Guessing entropy. In (Smith, 2009) Smith proposed another notion, the Rényi min-entropy, to measure the system’s leakage when the attacker has only one try at its disposal and attempts to make its best guess. The Rényi min-entropy is the logarithm of the Bayes vulnerability, which is the expected probability of the adversary to guess the secret correctly. The Bayes vulnerability is the converse of the Bayes error, which was already proposed as a measure of leakage in (Chatzikokolakis et al., 2008b).

Alvim et al. (Alvim et al., 2012) generalized the notion of Bayes vulnerability to that of $g$-vulnerability, by introducing a parameter (the gain function $g$) that describes the adversary’s payoff. The $g$-vulnerability  is the expected gain of the adversary in a one-try attack.

The idea of estimating the $g$-vulnerability in the using ML techniques is inspired by the seminal work (Cherubin et al., 2019), which used k-NN algorithms to estimate the Bayes vulnerability, a paradigm shift with respect to the previous frequentist approaches (Chatzikokolakis et al., 2010; Chothia and Guha, 2011; Chothia et al., 2014). Notably, (Cherubin et al., 2019) showed that universally consistent learning rules allow to achieve much more precise estimations than the frequentist approach when considering large or even continuous output domains which would be intractable otherwise. However, (Cherubin et al., 2019) was limited to the Bayes adversary. In contrast, our approach handles any adversary that can be modeled by a gain function $g$. Another novelty w.r.t. (Cherubin et al., 2019) is that we consider also ANN algorithms, which in various experiments appear to perform better than the k-NN ones.

Bordenabe and Smith (Bordenabe and Smith, 2016) investigated the indirect leakage induced by a channel (i.e., leakage on sensitive information not in the domain of the channel), and proved a fundamental equivalence between Dalenius min-entropy leakage under arbitrary correlations and g-leakage under arbitrary gain functions. This result is similar to our Theorem 4.2, and it opens the way to the possible extension of our approach to this more general leakage scenario.

Let $\mathcal{X}$ be a set of secrets and $\mathcal{Y}$ a set of observations. The adversary’s initial knowledge about the secrets is modeled by a prior distribution $\mathcal{P}(\mathcal{X})$ (namely $P_{X}$). A system is modeled as a probabilistic channel from $\mathcal{X}$ to $\mathcal{Y}$, described by a stochastic matrix $C$, whose elements $C_{xy}$ give the probability to observe $y\in\mathcal{Y}$ when the input is $x\in\mathcal{X}$ (namely $P_{Y|X}$). Running $C$ with input $\pi$ induces a joint distribution on $\mathcal{X}\times\mathcal{Y}$ denoted by $\pi{\kern-0.6pt\smalltriangleright\kern 0.3pt}C$.

In the $g$-leakage framework (Alvim et al., 2012) an adversary is described by a set $\mathcal{W}$ of guesses (or actions) that it can make about the secret, and by a gain function $g(w,x)$ expressing the gain of selecting the guess $w$ when the real secret is $x$. The prior $g$-vulnerability is the expected gain of an optimal guess, given a prior distribution on secrets:

In the posterior case, the adversary observes the output of the system which allows to improve its guess. Its expected gain is given by the posterior $g$-vulnerability, according to

Finally, the multiplicative¹¹1Originally the multiplicative version of $g$-leakage was defined as the $\log$ of the definition given here. In recent literature the $\log$ is not used anymore. Anyway, the two definitions are equivalent for system comparison, since $\log$ is monotonic. and additive $g$-leakage quantify how much a specific channel $C$ increases the vulnerability of the system:

The choice of the gain function $g$ allows to model a variety of different adversarial scenarios. The simplest case is the identity gain function, given by $\mathcal{W}=\mathcal{X}$, ${g_{\mathrm{id}}}(w,x)=1$ iff $x=w$ and $0$ otherwise. This gain function models an adversary that tries to guess the secret exactly in one try; $V_{{g_{\mathrm{id}}}}$ is the Bayes-vulnerability, which corresponds to the complement of the Bayes error (cfr. (Alvim et al., 2012)).

However, the interest in $g$-vulnerability lies in the fact that many more adversarial scenarios can be captured by a proper choice of $g$. For instance, taking $\mathcal{W}=\mathcal{X}^{k}$ with $g(w,x)=1$ iff $x\in w$ and $0$ otherwise, models an adversary that tries to guess the secret correctly in $k$ tries. Moreover, guessing the secret approximately can be easily expressed by constructing $g$ from a metric $d$ on $\mathcal{X}$; this is a standard approach in the area of location privacy (Shokri et al., 2011, 2012) where $g(w,x)$ is taken to be inversely proportional to the Euclidean distance between $w$ and $x$. Several other gain functions are discussed in (Alvim et al., 2012), while (Alvim et al., 2016) shows that any vulnerability function satisfying basic axioms can be expressed as $V_{g}$ for a properly constructed $g$.

The main focus of this paper is estimating the posterior $g$-vulnerability of the system from such samples. Note that, given $V_{g}(\pi,C)$, estimating $\mathit{\mathcal{L}^{\rm M}_{g}(\pi,C)}$ and $\mathit{\mathcal{L}^{\rm A}_{g}(\pi,C)}$ is straightforward, since $V_{g}(\pi)$ only depends on the prior (not on the system) and it can be either computed analytically or estimated from the samples.

We provide a short review of the aspects of ANN that are relevant for this work. For further details, we refer to (Bishop, 2007; Goodfellow et al., 2016; Hastie et al., 2001). Neural networks are usually modeled as directed graphs with weights on the connections and nodes that forward information through “activation functions”, often introducing non-linearity (such as sigmoids or soft-max). In particular, we consider an instance of learning known as supervised learning, where input samples are provided to the network model together with target labels (supervision). From the provided data and by means of iterative updates of the connection weights, the network learns how the data and respective labels are distributed. The training procedure, known as back-propagation, is an optimization process aimed at minimizing a loss function that quantifies the quality of the network’s prediction w.r.t. the data.

Classification problems are a typical example of tasks for which supervised learning works well. Samples are provided together with target labels which represent the classes they belong to. A model can be trained using these samples and, later on, it can be used to predict the class of new samples.

According to the No Free Lunch theorem (NFL) (Wolpert, 1996), in general, it cannot be said that ANN are better than other ML methods. However, it is well known that the NFL can be broken by additional information on the data or the particular problem we want to tackle, and, nowadays, for most applications and available data, especially in multidimensional domains, ANN models outperform other methods therefore representing the state-of-the-art.

The k-NN algorithm is one of the simplest algorithms used to classify a new sample given a training set of samples labelled as belonging to specific classes. This algorithm assumes that the space of the features is equipped with a notion of distance. The basic idea is the following: every time we need to classify a new sample, we find the $k$ samples whose features are closest to those of the new one (nearest neighbors). Once the $k$ nearest neighbors are selected, a majority vote over their class labels is performed to decide which class should be assigned to the new sample. For further details, as well as for an extensive analysis of the topic, we refer to the chapters about k-NN in (Shalev-Shwartz and Ben-David, 2014; Hastie et al., 2001).

We consider the problem of estimating the $g$-vulnerability from samples via ML models, and we show that the analysis of this estimation can be conducted in the general statistical framework of maximizing an expected functional using observed samples. The idea can be described using three components:

• •

  A generator of random secrets $x\in\mathcal{X}$ with $|\mathcal{X}|<\infty$, drawn independently from a fixed but unknown distribution $P_{X}(x)$;

• •

  a channel that returns an observable $y\in\mathcal{Y}$ with $|\mathcal{Y}|<\infty$ for every input $x$, according to a conditional distribution $P_{Y|X}(y|x)$, also fixed and unknown;

• •

  a learning machine capable of implementing a set of rules $f\in\mathcal{H}$, where $\mathcal{H}$ denotes the class of functions ${f:\mathcal{Y}\rightarrow\mathcal{W}}$ and $\mathcal{W}$ is the finite set of guesses.

Moreover let us note that

where $a$ and $b$ are finite real values, and $\mathcal{X}$ and $\mathcal{W}$ are finite sets. The problem of learning the $g$-vulnerability is that of choosing the function ${f:\mathcal{Y}\rightarrow\mathcal{W}}$ which maximizes the functional $V(f)$, representing the expected gain, defined as:

Note that $f(y)$ corresponds to the “guess” $w$, for the given $y$, in (2). The maximum of $V(f)$ is the $g$-vulnerability, namely:

Since we are in the black box scenario, the joint probability distribution $P_{XY}\equiv\pi{\kern-0.6pt\smalltriangleright\kern 0.3pt}C$ is unknown. We assume, however, the availability of $m$ independent and identically distributed (i.i.d.) samples drawn according to $P_{XY}$ that can be used as a training set $\mathcal{D}_{m}$  to solve the maximization of $f$ over $\mathcal{H}$ and additionally $n$ i.i.d. samples are available to be used as a validation²²2We call $\mathcal{T}_{n}$ validation set rather than test set, since we use it to estimate the $g$-vulnerability with the learned $f^{\star}_{m}$, rather than to measure the quality of $f^{\star}_{m}$. set $\mathcal{T}_{n}$ to estimate the average in (5). Let us denote these sets as: $\mathcal{D}_{m}$ $\stackrel{{\scriptstyle\text{def}}}{{=}}\big{\{}(x_{1},y_{1}),\dots,(x_{m},y_{m})\big{\}}$ and $\mathcal{T}_{n}$ $\stackrel{{\scriptstyle\text{def}}}{{=}}\big{\{}(x_{m+1},y_{m+1}),\dots,(x_{m+n},y_{m+n})\big{\}}$, respectively.

In order to maximize the $g$-vulnerability functional (5) for an unknown probability measure $P_{XY}$, the following principle is usually applied. The expected $g$-vulnerability functional $V(f)$ is replaced by the empirical $g$-vulnerability functional:

which is evaluated on $\mathcal{T}_{n}$ rather than $P_{XY}$. This estimator is clearly unbiased in the sense that $\mathbb{E}\big{[}\widehat{V}_{n}(f)\big{]}=V(f).$

Let $f^{\star}_{m}$ denote the empirical optimal rule given by

which is evaluated on $\mathcal{D}_{m}$ rather than $P_{XY}$. The function $f^{\star}_{m}$ is the optimizer according to $\mathcal{D}_{m}$, namely the best way among the functions $f:\mathcal{Y}\rightarrow\mathcal{W}$ to approximate $V_{g}$ by maximizing $\widehat{V}_{m}(f)$ over the class of functions $\mathcal{H}$. This principle is known in statistics as the Empirical Risk Maximization (ERM).

Intuitively, we would like $f^{\star}_{m}$ to give a good approximation of the $g$-vulnerability, in the sense that its expected gain

should be close to $V_{g}$. Note that the difference

is always non negative and represents the gap by selecting a possible suboptimal function $f^{\star}_{m}$. Unfortunately, we are not able to compute $V(f^{\star}_{m})$ either, since $P_{XY}$ is unknown. In its place, we have to use its estimation $\widehat{V}_{n}(f^{\star}_{m})$ Hence, the real estimation error is $|V_{g}-\widehat{V}_{n}(f^{\star}_{m})|$. Note that:

where the first term in the right end side represents the error induced by using the trained model $f_{m}^{\star}$ and the second represents the error induced by estimating the $g$-vulnerability over the $n$ samples in the validation set.

By using basics principles from statistical learning theory, we study two main questions:

• •

  When does the estimator $\widehat{V}_{n}(f^{\star}_{m})$ work? What are the conditions for its statistical consistency?

• •

  How well does $\widehat{V}_{n}(f^{\star}_{m})$ approximate $V_{g}$? In other words, how fast does the sequence of largest empirical g-leakage values converge to the largest g-leakage function? This is related to the so called rate of generalization of a learning machine that implements the ERM principle.

In the following we use the notation $\sigma^{2}_{f}=\mathit{Var}(g(f(Y),X))$, where $\mathit{Var}(Z)$ stands for the variance of the random variable $Z$. Namely, $\sigma^{2}_{f}$ is the variance of the gain for a given function $f$. We also use $\mathbb{P}$ to represent the probability induced by sampling the training and validation sets over the distribution $P_{XY}$.

Next proposition, proved in Appendix B.1, states that we can probabilistically delimit the two parts of the bound in (11) in terms of the sizes $m$ and $n$ of the training and validation sets.

Inequality (12) shows that the estimation error due to the use of a validation set in $\widehat{V}_{n}(f^{\star}_{m})$ instead of the true expected gain ${V}(f^{\star}_{m})$ vanishes with the number of validation samples. On the other hand, expression (13) implies ‘learnability’ of an optimal $f$, i.e., the suboptimality of $f^{\star}_{m}$ learned using the training set $\widehat{V}_{m}(f^{\star}_{m})$ vanishes with the number of training samples.

On the other hand the bound in eq. 13 depends on the underlying distribution and the structural properties of the class $\mathcal{H}$ through the variance. However, it does not explicitly depend on the optimization algorithm (e.g., stochastic gradient descent) used to learn the function $f_{m}^{\star}$ from the training set, which just comes from assuming the worst-case upper bound over all optimization procedures. The selection of a “good” subset of candidate functions, having a high probability of containing an almost optimal classifier, is a very active area of research in ML (Chizat and Bach, 2020), and hopefully there will be some result available soon, which together with our results will provide a practical method to estimate the bound on the errors. In appendix F we discuss heuristics to choose a “good” model, together with a new set of experiments showing the impact of different architectures.

Interestingly, the term $V_{g}-\mathbb{E}\big{[}{V}(f^{\star}_{m})\big{]}$ is the average error induced when estimating the function $f^{\star}_{m}$ using $m$ samples from the training set while $\mathbb{E}\big{|}{V}(f^{\star}_{m})-\widehat{V}_{n}(f^{\star}_{m})\big{|}$ indicates the average error incurred when estimating the $g$-vulnerability using $n$ samples from the validation set. Clearly, in eq. 15, the scaling of these bounds with the number of samples are very different which can be made evident by using the order notation:

These bounds indicate that the error in (17) vanishes much faster than the error in (18) and thus, the size of the training set, in general, should be kept larger than the size of the validation set, i.e., $n\ll m$.

We now study how large the validation set should be in order to get a good estimation. For ${\varepsilon,\delta>0}$, we define the sample complexity as the set of smallest integers $M(\varepsilon,\delta)$ and $N(\varepsilon,\delta)$ sufficient to guarantee that the gap between the true $g$-vulnerability and the estimated $\widehat{V}_{n}(f^{\star}_{m})$ is at most $\varepsilon$ with at least $1-\delta$ probability:

Next result says that we can bound the sample complexity in terms of $\varepsilon,\delta,\sigma$, and $|b-a|$ (see Appendix B.3 for the proof).

The theoretical results of this section are very general and cannot take full advantage of the specific properties of a particular model or data distribution. In particular, it is important to emphasize that the upper bound in (11) is independent of the learned function $f^{\star}_{m}$ because ${|\widehat{V}_{n}(f^{\star}_{m})-V(f^{\star}_{m})|\leq\max_{f\in\mathcal{H}}|\widehat{V}_{n}(f)-V(f)|}$ and because of (39), and thus these bounds are independent of the specific algorithm and training sets in used to solve the optimization in (8). Furthermore, the $f$ maximizing $|{V}(f)-\widehat{V}_{n}(f)|$ in those in-equations is not necessarily what the algorithm would choose. Hence the bounds given in Theorem 3.2 and 3.4 in general are not tight. However, these theoretical bounds provide a worst-case measure from which learnability holds for all data sets.

In the next section, we will propose an approach for selecting $f^{\star}_{m}$ and estimating $V_{g}$. The experiments in Section 5 suggest that our method usually estimates $V_{g}$ much more accurately than what is indicated by Theorem 3.2.

The data pre-processing technique is completely black-box in the sense that it does not need access to the channel. We only assume the availability of a set of pairs of type $(x,y)$, sampled according to $\pi{\kern-0.6pt\smalltriangleright\kern 0.3pt}C$, the input-output distribution of the channel. This set could be provided by a third party, for example. We divide the set in $\mathcal{D}_{m}$ (training) and $\mathcal{T}_{n}$ (validation), containing $m$ and $n$ pairs, respectively.

For the sake of simplicity, to describe this technique we assume that $g$ takes only integer values, in addition to being non-negative. The construction for the general case is discussed in Appendix C.3.

The idea behind the data pre-processing technique is that the effect of the gain function can be represented in the transformed dataset by amplifying the impact of the guesses in proportion to their reward. For example, consider a pair $(x,y)$ in $\mathcal{D}_{m}$, and assume that the reward for the guess $w$ is $g(w,x)=5$, while for another guess $w^{\prime}$ is $g(w^{\prime},x)=1$. Then in the transformed dataset $\mathcal{D}^{\prime}_{m^{\prime}}$ this pair will contribute with $5$ copies of $(w,y)$ and only $1$ copy of $(w^{\prime},y)$. The transformation is described in Algorithm 1. Note that in general it causes an expansion of the original dataset.

For this technique we assume black-box access to the system, i.e., that we can execute the system while controlling each input, and collect the corresponding output.

The core idea behind this technique is to transform the input of $C$ into entries of type $w$, and to ensure that the distribution on the $w$’s reflects the corresponding rewards expressed by $g$.

More formally, let us define a distribution $\tau$ on $\mathcal{W}$ as follows:

(note that $\beta$ is strictly positive because of the assumptions on $g$ and $\pi$), and let us define the following matrix $R$ from $\mathcal{W}$ to $\mathcal{X}$:

It is easy to check that $R$ is a stochastic matrix, hence the composition $RC$ is a channel. It is important to emphasize the following:

Remark  In the above definitions, $\beta,\tau$ and $R$ depend solely on $g$ and $\pi$, and not on $C$.
The above property is crucial to our goals, because in the black-box approach we are not supposed to rely on the knowledge of $C$’s internals. We now illustrate how we can estimate $V_{g}$ using the pre-processed channel $RC$.

The fundamental advantage of data pre-processing is that it allows to estimate $V_{g}$ from just samples of the system, without even black-box access. In contrast to channel pre-processing, however, this method is particularly sensitive to the values of the gain function $g$. Large gain values will increase the size of $\mathcal{D}^{\prime}_{m^{\prime}}$, with consequent increase of the computational cost for estimating the $g$-vulnerability. Moreover, if $g$ takes real values then we need to apply the technique described in Appendix C.3, which can lead to a large increase of the dataset as well. In contrast, the channel pre-processing method has the advantage of controlling the size of the training set, but it can be applied only when it is possible to interact with the channel by providing input and collecting output. Finally, from the precision point of view, we expect the estimation based on data pre-processing to be more accurate when $g$ consists of small integers, because the channel pre-processing introduces some extra noise in the channel.

We graphically represent the results of the experiment as box plots, using one box for each size. More precisely, given a specific size, let $\widehat{V}^{ij}_{n}$ be the $g$-vulnerability estimation on the $j$-th validation set computed with a model trained over the $i$-th training set (where $i\in\{1,\ldots,5\}$ and $j\in\{1,\ldots,50\}$). Let $V_{g}$ be the real $g$-vulnerability of the system. We define the normalized estimation error $\delta_{ij}$ and the mean value $\overline{\delta}$ of the $\delta_{ij}$’s as follows:

In the graphs, the $\delta_{ij}$’s are reported next to the box corresponding to the size, and $\overline{\delta}$ is the black horizontal line inside the box.

Thanks to the normalization the $\delta_{ij}$’s allow to compare results among different scenario and different levels of (real) $g$-vulnerability. Also, we argue that the percentage of the error is more meaningful than the absolute value. The interested reader, however, can find in Appendix H also plots showing the estimations of the $g$-vulnerability  and their distance from the real value.

We also consider the following typical measures of precision:

The dispersion is an average measure of how far the normalized estimation errors are from their mean value when using same-size training and validation sets. On the other hand, the total error is an average measure of the normalized estimation error, when using same-size training and validation sets.

In order to make a fair comparison between the two pre-processing methods, intuitively we need to use training and validation sets of “equivalent size”. For the validation part, since the “best” $f$ function has been already found and therefore we do not need any pre-processing anymore, “equivalent size” just means same size. But what does it mean, in the case of training sets built with different pre-processing methods? Assume that we have a set of data $\mathcal{D}_{m}$ coming from a third party collector (recall that $m$ represents the size of the set), and let $\mathcal{D}^{\prime}_{m^{\prime}}$ be the result of the data pre-processing on $\mathcal{D}_{m}$. Now, let $\mathcal{D}^{\prime\prime}_{m^{\prime\prime}}$ be the dataset obtained drawing samples according to the channel pre-processing method. Should we impose $m^{\prime\prime}=m$ or $m^{\prime\prime}=m^{\prime}$? We argue that the right choice is the first one, because the amount of “real” data collected is $m$. Indeed, $\mathcal{D}^{\prime}_{m^{\prime}}$ is generated synthetically from $\mathcal{D}_{m}$ and cannot contain more information about $C$ than $\mathcal{D}_{m}$, despite its larger size.

We consider two ML algorithms in the experiments: k-Nearest Neighbors (k-NN) and Artificial Neural Networks (ANN). We have made however a slight modification of k-NN algorithm, due to the following reason: recall that, depending on the particular gain function, the data pre-processing method might create many instances where a certain observable $y$ is repeated multiple times in pair with different $w$’s. For the k-NN algorithm, a very common choice is to consider a number of neighbors which is equivalent to natural logarithm of the total number of training samples. In particular, when the data pre-processing is applied, this means that $k=\log(m^{\prime})$ nearest neighbors will be considered for the classification decision. Since $\log(m^{\prime})$ grows slowly with respect to $m^{\prime}$, it might happen that k-NN fails to find the subset of neighbors from which the best remapping can be learned. To amend this problem, we modify the k-NN algorithm in the following way: instead of looking for neighbors among all the $m^{\prime}$ samples, we only consider a subset of $l\leq m^{\prime}$ samples, where each value $y$ only appears once. After the $\log(l)$ neighbors have been detected among the $l$ samples, we select $w$ according to a majority vote over the $m^{\prime}$ tuples $(w,y)$ created through the remapping.

The distance on which the notion of neighbor is based depends on the experiments. We have considered the standard distance among numbers in the first and fourth experiments, the Euclidean distance in the second one, and the Manhattan distance in the third one, which is a stand choice for DP.

Concerning the ANN models, their specifics are in Appendix D. Note that, for the sake of fairness, we use the same architecture for both pre-processing methods, although we adapt number of epochs and batch size to the particular dataset we are dealing with.

In the experiments, we will compare our method with the frequentist one. This approach has been proposed originally in (Chatzikokolakis et al., 2010) for estimating mutual information, and extended successively also to min-entropy leakage (Chothia et al., 2013). Although not considered in the literature, the extension to the case of $g$-vulnerability  is straightforward. The method consists in estimating the probabilities that constitute the channel matrix $C$, and then calculating analytically the $g$-vulnerability on $C$. The precise definition is in  Appendix E.

In (Cherubin et al., 2019) it was observed that in the case of the Bayes error the frequentist approach performs poorly when the size of the observable domain $|\mathcal{Y}|$ is large with respect to the available data. We want to study whether this is the case also for $g$-vulnerability.

For the experiment on the multiple guesses the comparison is illustrated in the next section. For the other experiments, because of lack of space, we have reported it in the Appendix H.

We consider a system in which the secrets $\mathcal{X}$ are the integers between $0$ and $9$, and the observables $\mathcal{Y}$ are the integers between $0$ and $15999$. Hence $|\mathcal{X}|=10$ and $|\mathcal{Y}|=16$K. The rows of the channel $C$ are geometric distributions centered on the corresponding secret:

where:

• •

  $\nu$ is a parameter that determines how concentrated around $y=x$ the distribution is. In this experiment we set $\nu=0.002$;

• •

  $r$ is an auxiliary function that reports $\mathcal{X}$ to the same scale of $\mathcal{Y}$, and centers $\mathcal{X}$ on $\mathcal{Y}$. Here $r(x)=1000\,x+3499.5$;

• •

  $\lambda=\nicefrac{{e^{\nu}-1}}{{(e^{\nu}+1)}}$ is a normalization factor

Figure 1 illustrates the shape of $C_{xy}$, showing the distributions $P_{Y|X}(\cdot|x)$ for two adjacent secrets $x=5$ and $x=6$. We consider an adversary that can make two attempts to discover the secret (two-tries adversary), and we define the corresponding gain function as follows. A guess $w\in\mathcal{W}$ is one of all the possible combinations of $2$ different secrets from $\mathcal{X}$, i.e., $w=\{x_{0},x_{1}\}$ with $x_{0},x_{1}\in\mathcal{X}$ and $x_{0}\neq x_{1}$. Therefore $|\mathcal{W}|=\binom{10}{2}=45$. The gain function $g$ is then

For this experiment we consider a uniform prior distribution $\pi$ on $\mathcal{X}$. The true $g$-vulnerability  for these particular $\nu$ and $\pi$, results to be $V_{g}=0.892$. As training sets sizes we consider $10$K, $30$K and $50$K, and 50K for the validation sets.

In this section we estimate the $g$-vulnerability of a typical system for location privacy protection. We use data from the open Gowalla dataset (Gow, 2011), which contains the coordinates of users’ check-ins. In particular, we consider a square region in San Francisco, USA, centered in (latitude, longitude) = ($37.755$, $-122.440$), and with $5$Km long sides. In this area Gowalla contains $35162$ check-ins.

We discretize the region in 400 cells of 250m long side, and we assume that the adversary’s goal is to discover the cell of a check-in. The frequency of the Gowalla check-ins per cell is represented by the heat-map in Figure 5. From these frequencies we can directly estimate the distribution representing the prior of the secrets (ElSalamouny and Palamidessi, 2020).

The channel $C$ that we consider here is the optimal obfuscation mechanism proposed in (Shokri et al., 2012) to protect location privacy under a utility constraint. We recall that the framework of (Shokri et al., 2012) assumes two loss functions, one for utility and one for privacy. The utility loss of a mechanism, for a certain prior, is defined as the expected utility loss of the noisy data generated according to the prior and the mechanism. The privacy loss is defined in a similar way, except that we allow the attacker to “remap” the noisy data so to maximize the privacy loss. For our experiment, we use the Euclidean distance as loss function for the utility, and the $g$ function defined in the next paragraph as loss function for the privacy. For further details on the construction of the optimal mechanism we refer to (Shokri et al., 2012).

We define $\mathcal{X},\mathcal{Y}$ and $\mathcal{W}$ to be the set of the cells. Hence $|\mathcal{X}|=|\mathcal{Y}|=|\mathcal{W}|=400$. We consider a $g$ function representing the precision of the guess in terms of Euclidean distance: the closer the guess is to the real location, the higher is the attacker’s gain. Specifically, our $g$ is illustrated in Figure 6, where the central cell represents the real location $x$. For a generic “guess” cell $w$, the number written in $w$ represent $g(w,x)$. ³³3Formally, $g$ is defined as $g(w,x)=\lfloor(\gamma\exp(-\alpha d(w,x)/l))\rceil,$ where $\gamma=4$ is the maximal gain, $\alpha=0.95$ is a normalization coefficient to control the skewness of the exponential, $d$ is the euclidean distance and $l=250$ is the length of the cells’ side. The symbol $\lfloor\cdot\rceil$ in this context represents the rounding to the closest integer operation.