Ashish Dandekar
email: adandekar@ens.fr

Debabrota Basu
email: basud@chalmers.se

Stéphane Bressan

Differential Privacy at Risk: Bridging Randomness and Privacy Budget

Keywords: Differential privacy, cost model, Laplace mechanism

The calibration of noise for a privacypreserving mechanism depends on the sensitivity of the query and the prescribed privacy level. A data steward must make the non-trivial choice of a privacy level that balances the requirements of users and the monetary constraints of the business entity. Firstly, we analyse roles of the sources of randomness, namely the explicit randomness induced by the noise distribution and the implicit randomness induced by the data-generation distribution, that are involved in the design of a privacy-preserving mechanism. The finer analysis enables us to provide stronger privacy guarantees with quantifiable risks. Thus, we propose privacy at risk that is a probabilistic calibration of privacypreserving mechanisms. We provide a composition theorem that leverages privacy at risk. We instantiate the probabilistic calibration for the Laplace mechanism by providing analytical results. Secondly, we propose a cost model that bridges the gap between the privacy level and the compensation budget estimated by a GDPR compliant business entity. The convexity of the proposed cost model leads to a unique fine-tuning of privacy level that minimises the compensation budget. We show its effectiveness by illustrating a realistic scenario that avoids overestimation of the compensation budget by using privacy at risk for the Laplace mechanism. We quantitatively show that composition using the cost optimal privacy at risk provides stronger privacy guarantee than the classical advanced composition. Although the illustration is specific to the chosen cost model, it naturally extends to any convex cost model. We also provide realistic illustrations of how a data steward uses privacy at risk to balance the tradeoff between utility and privacy.

Introduction

Dwork et al. [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF] quantify the privacy level ε in εdifferential privacy (or ε-DP) as an upper bound on the worst-case privacy loss incurred by a privacy-preserving mechanism. Generally, a privacy-preserving mechanism perturbs the results by adding the calibrated amount of random noise to them. The calibration of noise depends on the sensitivity of the query and the specified privacy level. In a real-world setting, a data steward must specify a privacy level that balances the requirements of the users and monetary constraints of the business entity. For example, Garfinkel et al. [START_REF] Simson | Issues encountered deploying differential privacy[END_REF] report on issues encountered when deploying differential privacy as the privacy definition by the US census bureau. They highlight the lack of analytical methods to choose the privacy level. They also report empirical studies that show the loss in utility due to the application of privacypreserving mechanisms.

We address the dilemma of a data steward in two ways. Firstly, we propose a probabilistic quantification of privacy levels. Probabilistic quantification of privacy levels provides a data steward with a way to take quantified risks under the desired utility of the data. We refer to the probabilistic quantification as privacy at risk. We also derive a composition theorem that leverages privacy at risk. Secondly, we propose a cost model that links the privacy level to a monetary budget. This cost model helps the data steward to choose the privacy level constrained on the estimated budget and vice versa. Convexity of the proposed cost model ensures the existence of a unique privacy at risk that would minimise the budget. We show that the composition with an optimal privacy at risk provides stronger privacy guarantees than the traditional advanced composition [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF]. In the end, we illustrate a realistic scenario that exemplifies how the data steward can avoid overestimation of the budget by using the proposed cost model by using privacy at risk.

The probabilistic quantification of privacy levels depends on two sources of randomness: the explicit randomness induced by the noise distribution and the implicit randomness induced by the data-generation distribution. Often, these two sources are coupled with each other. We require analytical forms of both sources of randomness as well as an analytical representation of the query to derive a privacy guarantee. Computing the probabilistic quantification of different sources of randomness is generally a challenging task. Although we find multiple probabilistic privacy definitions in the literature [START_REF] Hall | Random differential privacy[END_REF][START_REF] Machanavajjhala | Privacy: Theory meets practice on the map[END_REF] 1 , we miss an analytical quantification bridging the randomness and privacy level of a privacypreserving mechanism. We propose a probabilistic quantification, namely privacy at risk, that further leads to analytical relation between privacy and randomness. We derive a composition theorem with privacy at risk for mechanisms with the same as well as varying privacy levels. It is an extension of the advanced composition theorem [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF] that deals with a sequential and adaptive use of privacy-preserving mechanisms. We also prove that privacy at risk satisfies convexity over privacy levels and a weak relaxation of the post-processing property. To the best of our knowledge, we are the first to analytically derive the proposed probabilistic quantification for the widely used Laplace mechanism [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF].

The privacy level proposed by the differential privacy framework is too abstract a quantity to be integrated in a business setting. We propose a cost model that maps the privacy level to a monetary budget. The proposed model is a convex function of the privacy level, which further leads to a convex cost model for privacy at risk. Hence, it has a unique probabilistic privacy level that minimises the cost. We illustrate this using a realistic scenario in a GDPR-compliant business entity that needs an estimation of the compensation budget that it needs to pay to stakeholders in the unfortunate event of a personal data breach. The illustration, which uses the proposed convex cost model, shows that the use of probabilistic privacy levels avoids overestimation of the compensation budget without sacrificing utility. The illustration naturally extends to any convex cost model.

In this work, we comparatively evaluate the privacy guarantees using privacy at risk of the Laplace mechanism. We quantitatively compare the composition under the optimal privacy at risk, which is estimated using the cost model, with traditional composition mechanismsbasic and advanced mechanisms [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF]. We observe that it gives stronger privacy guarantees than the ones obtained by the advanced composition without sacrificing on the utility of the mechanism.

In conclusion, benefits of the probabilistic quantification i.e., of the privacy at risk are twofold. It not only quantifies the privacy level for a given privacypreserving mechanism but also facilitates decisionmaking in problems that focus on the privacy-utility trade-off and the compensation budget minimisation.

Background

We consider a universe of datasets D. We explicitly mention when we consider that the datasets are sampled from a data-generation distribution G with support D. Two datasets of equal cardinality x and y are said to be neighbouring datasets if they differ in one data point. A pair of neighbouring datasets is denoted by x ∼ y. In this work, we focus on a specific class of queries called numeric queries. A numeric query f is a function that maps a dataset into a real-valued vector, i.e. f : D → R k . For instance, a sum query returns the sum of the values in a dataset.

In order to achieve a privacy guarantee, researchers use a privacy-preserving mechanism, or mechanism in short, which is a randomised algorithm that adds noise to the query from a given family of distributions. Thus, a privacy-preserving mechanism of a given family, M(f, Θ), for the query f and the set of parameters Θ of the given noise distribution, is a function i.e. M(f, Θ) : D → R. In the case of numerical queries, R is R k . We denote a privacy-preserving mechanism as M, when the query and the parameters are clear from the context. Definition 1 (Differential Privacy [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF]). A privacypreserving mechanism M, equipped with a query f and with parameters Θ, is (ε, δ)-differentially private if for all Z ⊆ Range(M) and x, y ∈ D such that x ∼ y:

P(M(f, Θ)(x) ∈ Z) ≤ e ε × P(M(f, Θ)(y) ∈ Z) + δ.
An (ε, 0)-differentially private mechanism is also simply said to be ε-differentially private. Often, ε-differential privacy is referred to as pure differential privacy whereas (ε, δ)-differential privacy is referred as approximate differential privacy.

A privacy-preserving mechanism provides perfect privacy if it yields indistinguishable outputs for all neighbouring input datasets. The privacy level ε quantifies the privacy guarantee provided by ε-differential privacy. For a given query, the smaller the value of the ε, the qualitatively higher the privacy. A randomised algorithm that is ε-differentially private is also ε -differential private for any ε > ε.

In order to satisfy ε-differential privacy, the parameters of a privacy-preserving mechanism requires a calculated calibration. The amount of noise required to achieve a specified privacy level depends on the query. If the output of the query does not change drastically for two neighbouring datasets, then a small amount of noise is required to achieve a given privacy level. The measure of such fluctuations is called the sensitivity of the query. The parameters of a privacy-preserving mechanism are calibrated using the sensitivity of the query that quantifies the smoothness of a numeric query.

Definition 2 (Sensitivity). The sensitivity of a query

f : D → R k is defined as ∆ f max x,y∈D x∼y f (x) -f (y) 1 .
The Laplace mechanism is a privacy-preserving mechanism that adds scaled noise sampled from a calibrated Laplace distribution to the numeric query.

Definition 3 ([35]

). The Laplace distribution with mean zero and scale b > 0 is a probability distribution with probability density function

Lap(b) 1 2b exp - |x| b ,
where x ∈ R. We write Lap(b) to denote a random variable X ∼ Lap(b) Definition 4 (Laplace Mechanism [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF]). Given any function f : D → R k and any x ∈ D, the Laplace Mechanism is defined as

L ∆ f ε (x) M f, ∆ f ε (x) = f (x) + (L 1 , ..., L k ),
where L i is drawn from Lap Theorem 1 ([10]). The Laplace mechanism, L

∆ f ε0 , is ε 0 -differentially private.

Privacy at Risk: A Probabilistic Quantification of Randomness

The parameters of a privacy-preserving mechanism are calibrated using the privacy level and the sensitivity of the query. A data steward needs to choose an appropriate privacy level for practical implementation. Lee et al. [START_REF] Lee | How much is enough? choosing ε for differential privacy[END_REF] show that the choice of an actual privacy level by a data steward in regard to her business requirements is a non-trivial task. Recall that the privacy level in the definition of differential privacy corresponds to the worst case privacy loss. Business users are however used to taking and managing risks, if the risks can be quantified. For instance, Jorion [START_REF] Jorion | Value at risk: The new benchmark for managing financial risk[END_REF] defines Value at Risk that is used by risk analysts to quantify the loss in investments for a given portfolio and an acceptable confidence bound. Motivated by the formulation of Value at Risk, we propose to use the use of probabilistic privacy level. It provides us with a finer tuning of an ε 0differentially private privacy-preserving mechanism for a specified risk γ.

Definition 5 (Privacy at Risk). For a given data generating distribution G, a privacy-preserving mechanism M, equipped with a query f and with parameters Θ, satisfies ε-differential privacy with a privacy at risk 0 ≤ γ ≤ 1 if, for all Z ⊆ Range(M) and x, y sampled from G such that x ∼ y:

P ln P(M(f, Θ)(x) ∈ Z) P(M(f, Θ)(y) ∈ Z) > ε ≤ γ, ( 1
)
where the outer probability is calculated with respect to the probability space Range(M • G) obtained by applying the privacy-preserving mechanism M on the datageneration distribution G.

If a privacy-preserving mechanism is ε 0 -differentially private for a given query f and parameters Θ, for any privacy level ε ≥ ε 0 , the privacy at risk is 0. We are interested in quantifying the risk γ with which an ε 0 -differentially private privacy-preserving mechanism also satisfies a stronger ε-differential privacy, i.e., with ε < ε 0 .

Unifying Probabilistic and Random DP Interestingly, Equation (1) unifies the notions of probabilistic differential privacy and random differential privacy by accounting for both sources of randomness in a privacy-preserving mechanism. Machanavajjhala et al. [START_REF] Machanavajjhala | Privacy: Theory meets practice on the map[END_REF] define probabilistic differential privacy that incorporates the explicit randomness of the noise distribution of the privacy-preserving mechanism, whereas Hall et al. [START_REF] Hall | Random differential privacy[END_REF] define random differential privacy that incorporates the implicit randomness of the data-generation distribution. In probabilistic differential privacy, the outer probability is computed over the sample space of Range(M) and all datasets are equally probable.

Connection with Approximate DP

Despite a resemblance with probabilistic relaxations of differential privacy [START_REF] Dwork | Concentrated differential privacy[END_REF][START_REF] Hall | Random differential privacy[END_REF][START_REF] Machanavajjhala | Privacy: Theory meets practice on the map[END_REF] due to the added parameter δ, (ε, δ)-differential privacy (Definition 1) is a nonprobabilistic variant [START_REF] Meiser | Approximate and probabilistic differential privacy definitions[END_REF] of regular ε-differential privacy. Indeed, unlike the auxiliary parameters in probabilistic relaxations, such as γ in privacy at risk (ref.

Definition 5), the parameter δ of approximate differential privacy is an absolute slack that is independent of the sources of randomness. For a specified choice of ε and δ, one can analytically compute a matching value of δ for a new value of ε 2 . Therefore, as other probabilistic relaxations, privacy at risk cannot be directly related to approximate differential privacy. An alternative is to find out a privacy at risk level γ for a given privacy level (ε, δ) while the original noise satisfies (ε 0 , δ).

Theorem 2. If a privacy preserving mechanism satisfies (ε, γ) privacy at risk, it also satisfies (ε, γ) approximate differential privacy.

We obtain this reduction as the probability measure induced by the privacy preserving mechanism and data generating distribution on any output set Z ⊆ Range(M) is additive. 3 The proof of the theorem is in Appendix A.

Composition theorem

The application of ε-differential privacy to many realworld problem suffers from the degradation of privacy guarantee, i.e., privacy level, over the composition. The basic composition theorem [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF] dictates that the privacy guarantee degrades linearly in the number of evaluations of the mechanism. The advanced composition theorem [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF] provides a finer analysis of the privacy loss 2 For any 0 < ε ≤ ε, any (ε, δ)-differentially private mechanism also satisfies (ε , (e εe ε + δ))-differential privacy.

3 The converse is not true as explained before.

over multiple evaluations with a square root dependence on the number of evaluations. In this section, we provide the composition theorem for privacy at risk. Definition 6 (Privacy loss random variable). For a privacy-preserving mechanism M : D → R, any two neighbouring datasets x, y ∈ D and an output r ∈ R, the value of the privacy loss random variable C is defined as:

C(r) ln P(M(x) = r) P(M(y) = r)
.

Lemma 1. If a privacy-preserving mechanism M satisfies ε 0 -differential privacy, then

P[|C| ≤ ε 0 ] = 1.
Theorem 3. For all ε 0 , ε, γ, δ > 0, the class of ε 0differentially private mechanisms, which satisfy (ε, γ)privacy at risk under a uniform data-generation distribution, are (ε , δ)-differential privacy under n-fold composition where

ε = ε 0 2n ln 1 δ + nµ, where µ = 1 2 [γε 2 + (1 -γ)ε 2 0 ]. Proof. Let, M 1...n : D → R 1 × R 2 × ... × R n denote the n-fold composition of privacy-preserving mechanisms {M i : D → R i } n i=1
. Each ε 0 -differentially private M i also satisfies (ε, γ)-privacy at risk for some ε ≤ ε 0 and appropriately computed γ. Consider any two neighbouring datasets x, y ∈ D. Let,

B = (r 1 , ..., r n ) n i=1 P(M i (x) = r i ) P(M i (y) = r i ) > e ε
Using the technique in [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF]Theorem 3.20], it suffices to show that P(M 1...n (x) ∈ B) ≤ δ.

Consider ln P(M 1...n (x) = (r 1 , ..., r n )) P(M 1...n (y) = (r 1 , ..., r n )) = ln n i=1 P(M i (x) = r i ) P(M i (y) = r i ) = n i=1 ln P(M i (x) = r i ) P(M i (y) = r i ) n i=1 C i (2)
where C i in the last line denotes the privacy loss random variable related to M i . Consider an ε-differentially private mechanism M ε and ε 0 -differentially private mechanism M ε0 . Let M ε0 satisfy (ε, γ)-privacy at risk for ε ≤ ε 0 and appropriately computed γ. Each M i can be simulated as the mechanism M ε with probability γ and the mechanism M ε0 otherwise. Therefore, the privacy loss random variable for each mechanism M i can be written as

C i = γC i ε + (1 -γ)C i ε0
where C i ε denotes the privacy loss random variable associated with the mechanism M ε and C i ε0 denotes the privacy loss random variable associated with the mechanism M ε0 . Using [START_REF] Bun | Concentrated differential privacy: Simplifications, extensions, and lower bounds[END_REF]Remark 3.4], we can bound the mean of every privacy loss random variable as:

µ E[C i ] ≤ 1 2 [γε 2 + (1 -γ)ε 2 0 ].
We have a collection of n independent privacy random variables C i 's such that P |C i | ≤ ε 0 = 1. Using Hoeffding's bound [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF] on the sample mean for any β > 0,

P 1 n i C i ≥ E[C i ] + β ≤ exp - nβ 2 2ε 2 0 .
Rearranging the inequality by renaming the upper bound on the probability as δ, we get:

P i C i ≥ nµ + ε 0 2n ln 1 δ ≤ δ.
Theorem 3 is an analogue, in the privacy at risk setting, of the advanced composition of differential privacy [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF]Theorem 3.20] under a constraint of independent evaluations. Note that if one takes γ = 0, then we obtain the exact same formula as in [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF]Theorem 3.20]. It provides a sanity check for the consistency of composition using privacy at risk.

Corollary 1 (Heterogeneous Composition

). For all ε l , ε, γ l , δ > 0 and l ∈ {1, . . . , n}, the composition of {ε l } n l=1 -differentially private mechanisms, which satisfy (ε, γ l )-privacy at risk under a uniform data-generation distribution, also satisfies (ε , δ)-differential privacy where

ε = 2 n l=1 ε 2 l ln 1 δ + µ, where µ = 1 2 [ε 2 ( n l=1 γ l ) + n l=1 (1 -γ l )ε 2 l ].
Proof. The proof follows from the same argument as that of Theorem 3 of bounding the loss random variable at step l using γ l C l ε + (1 -γ l )C l ε l and then applying the concentration inequality.

A detailed discussion and analysis of proving such heterogeneous composition theorems is available in [START_REF] Kairouz | The composition theorem for differential privacy[END_REF]Section 3.3].

In fact, if we consider both sources of randomness, the expected value of the loss function must be computed by using the law of total expectation.

E[C] = E x,y∼G [E[C]|x, y]
Therefore, the exact computation of privacy guarantees after the composition requires access to the datageneration distribution. We assume a uniform datageneration distribution while proving Theorem 3. We can obtain better and finer privacy guarantees accounting for data-generation distribution, which we keep as a future work.

Convexity and Post-Processing

We show that privacy at risk satisfies the convexity property and does not satisfy the post-processing property.

Lemma 2 (Convexity). For a given ε 0 -differentially private privacy-preserving mechanism, privacy at risk satisfies the convexity property.

Proof. Let M be a mechanism that satisfies ε 0differential privacy. By the definition of the privacy at risk, it also satisfies (ε 1 , γ 1 )-privacy at risk as well as (ε 2 , γ 2 )-privacy at risk for some ε 1 , ε 2 ≤ ε 0 and appropriately computed values of γ 1 and γ 2 . Let M 1 and M 2 denote the hypothetical mechanisms that satisfy (ε 1 , γ 1 )-privacy at risk and (ε 2 , γ 2 )-privacy at risk respectively. We can write privacy loss random variables as follows:

C 1 ≤ γ 1 ε 1 + (1 -γ 1 )ε 0 C 2 ≤ γ 2 ε 2 + (1 -γ 2 )ε 0
where C 1 and C 2 denote privacy loss random variables for M 1 and M 2 .

Let us consider a privacy-preserving mechanism M that uses M 1 with a probability p and M 2 with a probability (1-p) for some p ∈ [0, 1]. By using the techniques in the proof of Theorem 3, the privacy loss random variable C for M can be written as:

C = pC 1 + (1 -p)C 2 ≤ γ ε + (1 -γ )ε 0 where ε = pγ 1 ε 1 + (1 -p)γ 2 ε 2 pγ 1 + (1 -p)γ 2 γ = (1 -pγ 1 -(1 -p)γ 2 )
Thus, M satisfies (ε , γ )-privacy at risk. This proves that privacy at risk satisfies convexity [23, Axiom 2.1.2].

Meiser [START_REF] Meiser | Approximate and probabilistic differential privacy definitions[END_REF] proved that a relaxation of differential privacy that provides probabilistic bounds on the privacy loss random variable does not satisfy post-processing property of differential privacy. Privacy at risk is indeed such a probabilistic relaxation.

Corollary 2 (Post-processing). Privacy at risk does not satisfy the post-processing property for every possible mapping of the output.

Though privacy at risk is not preserved after postprocessing, it yields a weaker guarantee in terms of approximate differential privacy after post-processing. The proof involves reduction of privacy at risk to approximate differential privacy and preservation of approximate differential privacy under post-processing.

Lemma 3 (Weak Post-processing). Let M : D → R ⊆
R k be a mechanism that satisfy (ε, γ)-privacy at risk and f : R → R be any arbitrary data independent mapping. Then, f • M : D → R would also satisfy (ε, γ)approximate differential privacy.

Proof. Let us fix a pair of neighbouring datasets x and y, and also an event Z ⊆ R . Let us define pre-image of Z as Z {r ∈ R : f (r) ∈ Z}. Now, we get

P(f • M(x) ∈ Z ) = P(M(x) ∈ Z) ≤ (a) e ε P(M(y) ∈ Z) + γ = e ε P(f • M(y) ∈ Z ) + δ (a) is a direct consequence of Theorem 2.

Privacy at Risk for Laplace Mechanism

The Laplace and Gaussian mechanisms are widely used privacy-preserving mechanisms in the literature. The Laplace mechanism satisfies pure ε-differential privacy whereas the Gaussian mechanism satisfies approximate (ε, δ)-differential privacy. As previously discussed, it is not straightforward to establish a connection between the non-probabilistic parameter δ of approximate differential privacy and the probabilistic bound γ of privacy at risk. Therefore, we keep privacy at risk for Gaussian mechanism as the future work.

In this section, we instantiate privacy at risk for the Laplace mechanism in three cases: two cases involving two sources of randomness and a third case involving the coupled effect. These three different cases correspond to three different interpretations of the confidence level, represented by the parameter γ, corresponding to three interpretations of the support of the outer probability in Definition 5. In order to highlight this nuance, we denote the confidence levels corresponding to the three cases and their three sources of randomness as γ 1 , γ 2 , and γ 3 , respectively.

The Case of Explicit Randomness

In this section, we study the effect of the explicit randomness induced by the noise sampled from Laplace distribution. We provide a probabilistic quantification for fine tuning for the Laplace mechanism. We fine-tune the privacy level for a specified risk under by assuming that the sensitivity of the query is known a priori.

For a Laplace mechanism L ∆ f ε0 calibrated with sensitivity ∆ f and privacy level ε 0 , we present the analytical formula relating privacy level ε and the risk γ 1 in Theorem 4. The proof is available in Appendix B.

Theorem 4. The risk

γ 1 ∈ [0, 1] with which a Laplace Mechanism L ∆ f ε0 , for a numeric query f : D → R k sat- isfies a privacy level ε ≥ 0 is given by γ 1 = P(T ≤ ε) P(T ≤ ε 0 ) , ( 3
)
where T is a random variable that follows a distribution with the following density function.

P T (t) = 2 1-k t k-1 2 K k-1 2 (t)ε 0 √ 2πΓ(k)∆ f where K n-1 2
is the Bessel function of second kind.

Figure 1a shows the plot of the privacy level against risk for different values of k and for a Laplace mechanism L 1.0 1.0 . As the value of k increases, the amount of noise added in the output of numeric query increases. Therefore, for a specified privacy level, the privacy at risk level increases with the value of k.

The analytical formula representing γ 1 as a function of ε is bijective. We need to invert it to obtain the privacy level ε for a privacy at risk γ 1 . However the analytical closed form for such an inverse function is not explicit. We use a numerical approach to compute privacy level for a given privacy at risk from the analytical formula of Theorem 4.

Result for a Real-valued Query. For the case k = 1, the analytical derivation is fairly straightforward. In this case, we obtain an invertible closed-form of a privacy level for a specified risk. It is presented in Equation 4.

ε = ln 1 1 -γ 1 (1 -e -ε0 ) (4)
Remarks on ε 0 . For k = 1, Figure 1b shows the plot of privacy at risk level ε versus privacy at risk γ 1 for the Laplace mechanism L 1.0 ε0 . As the value of ε 0 increases, the probability of Laplace mechanism generating higher value of noise reduces. Therefore, for a fixed privacy level, privacy at risk increases with the value of ε 0 . The same observation is made for k > 1.

The Case of Implicit Randomness

In this section, we study the effect of the implicit randomness induced by the data-generation distribution to provide a fine tuning for the Laplace mechanism. We fine-tune the risk for a specified privacy level without assuming that the sensitivity of the query.

If one takes into account randomness induced by the data-generation distribution, all pairs of neighbouring datasets are not equally probable. This leads to estimation of sensitivity of a query for a specified datageneration distribution. If we have access to an analytical form of the data-generation distribution and to the query, we could analytically derive the sensitivity distribution for the query. In general, we have access to the datasets, but not the data-generation distribution that generates them. We, therefore, statistically estimate sensitivity by constructing an empirical distribution. We call the sensitivity value obtained for a specified risk from the empirical cumulative distribution of sensitivity the sampled sensitivity (Definition 7). However, the value of sampled sensitivity is simply an estimate of the sensitivity for a specified risk. In order to capture this additional uncertainty introduced by the estimation from the empirical sensitivity distribution rather than the true unknown distribution, we compute a lower bound on the accuracy of this estimation. This lower bound yields a probabilistic lower bound on the specified risk. We refer to it as empirical risk. For a specified absolute risk γ 2 , we denote by γ2 corresponding empirical risk.

For the Laplace mechanism L ∆ S f ε calibrated with sampled sensitivity ∆ S f and privacy level ε, we evaluate the empirical risk γ2 . We present the result in Theorem 5. The proof is available in Appendix C.

f : D → R k is γ2 ≥ γ 2 (1 -2e -2ρ 2 n ) ( 5
)
where n is the number of samples used for estimation of the sampled sensitivity and ρ is the accuracy parameter. γ 2 denotes the specified absolute risk.

The error parameter ρ controls the closeness between the empirical cumulative distribution of the sensitivity to the true cumulative distribution of the sensitivity. Lower the value of the error, closer is the empirical cumulative distribution to the true cumulative distribution. Mathematically,

ρ ≥ sup ∆ |F n S (∆) -F S (∆)|,
where F n S is the empirical cumulative distribution of sensitivity after n samples and F S is the actual cumulative distribution of sensitivity.

Figure 2 shows the plot of number of samples as a function of the privacy at risk and the error parameter. Naturally, we require higher number of samples in order to have lower error rate. The number of samples reduces as the privacy at risk increases. The lower risk demands precision in the estimated sampled sensitivity, which in turn requires larger number of samples.

If the analytical form of the data-generation distribution is not known a priori, the empirical distribution of sensitivity can be estimated in two ways. The first way is to fit a known distribution on the available data and later use it to build an empirical distribution of the sensitivities. The second way is to sub-sample from a large dataset in order to build an empirical distribution of the sensitivities. In both of these ways, the empirical distribution of sensitivities captures the inherent randomness in the data-generation distribution. The first way suffers from the goodness of the fit of the known distribution to the available data. An ill-fit distribution does not reflect the true data-generation distribution and hence introduces errors in the sensitivity estimation. Since the second way involves subsampling, it is immune to this problem. The quality of sensitivity estimates obtained by sub-sampling the datasets depend on the availability of large population. Let, G denotes the data-generation distribution, either known apriori or constructed by subsampling the available data. We adopt the procedure of [START_REF] Benjamin Ip Rubinstein | Pain-free random differential privacy with sensitivity sampling[END_REF] to sample two neighbouring datasets with p data points each. We sample p -1 data points from G that are common to both of these datasets and later two more data points, independently. From those two points, we allot one data point to each of the two datasets.

Let, S f = f (x) -f (y) 1 denotes the sensitivity random variable for a given query f , where x and y are two neighbouring datasets sampled from G. Using n pairs of neighbouring datasets sampled from G, we construct the empirical cumulative distribution, F n , for the sensitivity random variable. Definition 7. For a given query f and for a specified risk γ 2 , sampled sensitivity, ∆ S f , is defined as the value of sensitivity random variable that is estimated using its empirical cumulative distribution function, F n , constructed using n pairs of neighbouring datasets sampled from the data-generation distribution G.

∆ S f F -1 n (γ 2 )
If we knew analytical form of the data generation distribution, we could analytically derive the cumulative distribution function of the sensitivity, F , and find the sensitivity of the query as ∆ f = F -1 (1). Therefore, in order to have the sampled sensitivity close to the sensitivity of the query, we require the empirical cumulative distributions to be close to the cumulative distribution of the sensitivity. We use this insight to derive the analytical bound in the Theorem 5.

The Case of Explicit and Implicit Randomness

In this section, we study the combined effect of both explicit randomness induced by the noise distribution and implicit randomness in the data-generation distribution respectively. We do not assume the knowledge of the sensitivity of the query. We estimate sensitivity using the empirical cumulative distribution of sensitivity. We construct the empirical distribution over the sensitivities using the sampling technique presented in the earlier case. Since we use the sampled sensitivity (Definition 7) to calibrate the Laplace mechanism, we estimate the empirical risk γ3 .

For Laplace mechanism L ∆ S f ε0 calibrated with sampled sensitivity ∆ S f and privacy level ε 0 , we present the analytical bound on the empirical sensitivity γ3 in Theorem 6 with proof in the Appendix D.

Theorem 6. Analytical bound on the empirical risk

γ3 ∈ [0, 1] to achieve a privacy level ε > 0 for Laplace mechanism L ∆ S f ε0 with sampled sensitivity ∆ S f of a query f : D → R k is γ3 ≥ γ 3 (1 -2e -2ρ 2 n ) ( 6
)
where n is the number of samples used for estimating the sensitivity, ρ is the accuracy parameter. γ 3 denotes the specified absolute risk defined as:

γ 3 = P(T ≤ ε) P(T ≤ ηε 0 ) • γ 2
Here, η is of the order of the ratio of the true sensitivity of the query to its sampled sensitivity.

The error parameter ρ controls the closeness between the empirical cumulative distribution of the sensitivity to the true cumulative distribution of the sensitivity. Figure 3 shows the dependence of the error parameter on the number of samples. In Figure 3a, we observe that for a fixed number of samples and a privacy level, the privacy at risk decreases with the value of error parameter. For a fixed number of samples, smaller values of the error parameter reduce the probability of similarity between the empirical cumulative distribution of sensitivity and the true cumulative distribution. Therefore, we observe the reduction in the risk for a fixed privacy level. In Figure 3b, we observe that for a fixed value of error parameter and a fixed level of privacy level, the risk increases with the number of samples. For a fixed value of the error parameter, larger values of the sample size increase the probability of similarity between the empirical cumulative distribution of sensitivity and the true cumulative distribution. Therefore, we observe the increase in the risk for a fixed privacy level.

Effect of the consideration of implicit and explicit randomness is evident in the analytical expression for γ 3 in Equation 7. Proof is available in Appendix D. The privacy at risk is composed of two factors whereas the second term is a privacy at risk that accounts for inherent randomness. The first term takes into account the implicit randomness of the Laplace distribution along with a coupling coefficient η. We define η as the ratio of the true sensitivity of the query to its sampled sensitivity. We provide an approximation to estimate η in the absence of knowledge of the true sensitivity. It can be found in Appendix D.

γ 3 P(T ≤ ε) P(T ≤ ηε 0 ) • γ 2 (7)

Minimising Compensation Budget for Privacy at Risk

Many service providers collect users' data to enhance user experience. In order to avoid misuse of this data, we require a legal framework that not only limits the use of the collected data but also proposes reparative measures in case of a data leak. General Data Protection Regulation (GDPR) 4 is such a legal framework. Section 82 in GDPR states that any person who suffers from material or non-material damage as a result of a personal data breach has the right to demand compensation from the data processor. Therefore, every GDPR compliant business entity that either holds or processes personal data needs to secure a certain budget in the scenario of the personal data breach. In order to reduce the risk of such an unfortunate event, the business entity may use privacy-preserving mechanisms that provide provable privacy guarantees while publishing their results. In order to calculate the compensation budget for a business entity, we devise a cost model that maps the privacy guarantees provided by differential privacy and privacy at risk to monetary costs. The discussions demonstrate the usefulness of probabilistic quantification of differential privacy in a business setting.

4 https://gdpr-info.eu/

Cost Model for Differential Privacy

Let E be the compensation budget that a business entity has to pay to every stakeholder in case of a personal data breach when the data is processed without any provable privacy guarantees. Let E dp ε be the compensation budget that a business entity has to pay to every stakeholder in case of a personal data breach when the data is processed with privacy guarantees in terms of ε-differential privacy.

Privacy level, ε, in ε-differential privacy is the quantifier of indistinguishability of the outputs of a privacypreserving mechanism when two neighbouring datasets are provided as inputs. When the privacy level is zero, the privacy-preserving mechanism outputs all results with equal probability. The indistinguishability reduces with increase in the privacy level. Thus, privacy level of zero bears the lowest risk of personal data breach and the risk increases with the privacy level. E dp ε needs to be commensurate to such a risk and, therefore, it needs to satisfy the following constraints.

1. For all ε ∈ R ≥0 , E dp ε ≤ E. 2. E dp ε is a monotonically increasing function of ε. 3. As ε → 0, E dp
ε → E min where E min is the unavoidable cost that business entity might need to pay in case of personal data breach even after the privacy measures are employed. 4. As ε → ∞, E dp ε → E.

There are various functions that satisfy these constraints. In absence of any further constraints, we model E dp ε as defined in Equation ( 8).

E dp ε E min + Ee -c ε . ( 8
)
E dp ε has two parameters, namely c > 0 and E min ≥ 0. c controls the rate of change in the cost as the privacy level changes and E min is a privacy level independent bias. For this study, we use a simplified model with c = 1 and E min = 0.

Cost Model for Privacy at Risk

Let, E par ε0 (ε, γ) be the compensation that a business entity has to pay to every stakeholder in case of a personal data breach when the data is processed with an ε 0 -differentially private privacy-preserving mechanism along with a probabilistic quantification of privacy level. Use of such a quantification allows us to provide a stronger privacy guarantee viz. ε < ε 0 for a specified privacy at risk at most γ. Thus, we calculate E par ε0 using Equation 9.

E par ε0 (ε, γ) γE dp ε + (1 -γ)E dp ε0 (9)
Note that the analysis in this section is specific to the cost model in Equation 8. It naturally extends to any choice of convex cost model.

Existence of Minimum Compensation Budget

We want to find the privacy level, say ε min , that yields the lowest compensation budget. We do that by minimising Equation 9with respect to ε. 8,

Lemma 4. For the choice of cost model in Equation

E par ε0 (ε, γ) is a convex function of ε.
By Lemma 4, there exists a unique ε min that minimises the compensation budget for a specified parametrisation, say ε 0 . Since the risk γ in Equation 9is itself a function of privacy level ε, analytical calculation of ε min is not possible in the most general case. When the output of the query is a real number, i. e. k = 1, we derive the analytic form (Equation 4) to compute the risk under the consideration of explicit randomness. In such a case, ε min is calculated by differentiating Equation 9with respect to ε and equating it to zero. It gives us Equation 10 that we solve using any root finding technique such as Newton-Raphson method [START_REF] William | Numerical recipes 3rd edition: The art of scientific computing[END_REF] to compute ε min .

1 ε -ln 1 - 1 -e ε ε 2 = 1 ε 0 (10)

Fine-tuning Privacy at Risk

For a fixed budget, say B, re-arrangement of Equation 9gives us an upper bound on the privacy level ε. We use the cost model with c = 1 and E min = 0 to derive the upper bound. If we have a maximum permissible expected mean absolute error T , we use Equation 12to obtain a lower bound on the privacy at risk level. Equation 11 illustrates the upper and lower bounds that dictate the permissible range of ε that a data publisher can promise depending on the budget and the permissible error constraints.

1 T ≤ ε ≤ ln γE B -(1 -γ)E dp ε0 -1 (11)
Thus, the privacy level is constrained by the effectiveness requirement from below and by the mone- tary budget from above. [START_REF] Hsu | Differential privacy: An economic method for choosing epsilon[END_REF] calculate upper and lower bound on the privacy level in the differential privacy. They use a different cost model owing to the scenario of research study that compensates its participants for their data and releases the results in a differentially private manner. Their cost model is different than our GDPR inspired modelling.

Illustration

Suppose that the health centre in a university that complies to GDPR publishes statistics of its staff health checkup, such as obesity statistics, twice in a year. In January 2018, the health centre publishes that 34 out of 99 faculty members suffer from obesity. In July 2018, the health centre publishes 35 out of 100 faculty members suffer from obesity. An intruder, perhaps an analyst working for an insurance company, checks the staff listings in January 2018 and July 2018, which are publicly available on website of the university. The intruder does not find any change other than the recruitment of John Doe in April 2018. Thus, with high probability, the intruder deduces that John Doe suffers from obesity. In order to avoid such a privacy breach, the health centre decides to publish the results using the Laplace mechanism. In this case, the Laplace mechanism operates on the count query.

In order to control the amount of noise, the health centre needs to appropriately set the privacy level. Suppose that the health centre decides to use the expected mean absolute error, defined in Equation 12, as the mea-sure of effectiveness for the Laplace mechanism.

E |L 1 ε (x) -f (x)| = 1 ε (12)
Equation 12 makes use of the fact that the sensitivity of the count query is one. Suppose that the health centre requires the expected mean absolute error of at most two in order to maintain the quality of the published statistics. In this case, the privacy level has to be at least 0.5.

In order to compute the budget, the health centre requires an estimate of E. Moriarty et al. [START_REF] James P Moriarty | The effects of incremental costs of smoking and obesity on health care costs among adults: a 7-year longitudinal study[END_REF] show that the incremental cost of premiums for the health insurance with morbid obesity ranges between $5467 to $5530. With reference to this research, the health centre takes $5500 as an estimate of E. For the staff size of 100 and the privacy level 0.5, the health centre uses Equation 8 in its simplified setting to compute the total budget of $74434.40.

Is it possible to reduce this budget without degrading the effectiveness of the Laplace mechanism? We show that it is possible by fine-tuning the Laplace mechanism. Under the consideration of the explicit randomness introduced by the Laplace noise distribution, we show that ε 0 -differentially private Laplace mechanism also satisfies ε-differential privacy with risk γ, which is computed using the formula in Theorem 4. Fine-tuning allows us to get a stronger privacy guarantee, ε < ε 0 that requires a smaller budget. In Figure 4, we plot the budget for various privacy levels. We observe that the privacy level 0.274, which is same as ε min computed by solving Equation 10, yields the lowest compensation budget of $37805.86. Thus, by using privacy at risk, the health centre is able to save $36628.532 without sacrificing the quality of the published results.

Cost Model and the Composition of Laplace Mechanisms

Convexity of the proposed cost function enables us to estimate the optimal value of the privacy at risk level. We use the optimal privacy value to provide tighter bounds on the composition of Laplace mechanism. In Figure 5, we compare the privacy guarantees obtained by using basic composition theorem [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF], advanced composition theorem [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF] and the composition theorem for privacy at risk. We comparatively evaluate them for composition of Laplace mechanisms with privacy levels 0.1, 0.5 and 1.0. We compute the privacy level after composition by setting δ to 10 -5 . Basic Compositio [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF] Adva ced Compositio [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF] Compositio (ith Privac) at Risk (c) L 1 1.0 satisfies (0.42, 0.54)-privacy at risk.

Fig. 5.

Comparing the privacy guarantee obtained by basic composition and advanced composition [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF] with the composition obtained using optimal privacy at risk that minimises the cost of Laplace mechanism L 1 ε 0 . For the evaluation, we set δ = 10 -5 .

We observe that the use of optimal privacy at risk provided significantly stronger privacy guarantees as compared to the conventional composition theorems. Advanced composition theorem is known to provide stronger privacy guarantees for mechanism with smaller εs. As we observe in Figure 5c and Figure 5b, the composition provides strictly stronger privacy guarantees than basic composition, in the cases where the advanced composition fails.

Comparison with the Moment Accountant

Papernot et al. [START_REF] Papernot | Semi-supervised knowledge transfer for deep learning from private training data[END_REF][START_REF] Papernot | Scalable private learning with PATE[END_REF] empirically showed that the privacy guarantees provided by the advanced composition theorem are quantitatively worse than the ones achieved by the state-of-the-art moment accountant [START_REF] Abadi | Deep learning with differential privacy[END_REF]. The moment accountant evaluates the privacy guarantee by keeping track of various moments of privacy loss random variables. The computation of the moments is performed by using numerical methods on the specified dataset. Therefore, despite the quantitative strength of privacy guarantee provided by the moment accountant, it is qualitatively weaker, in a sense that it is specific to the dataset used for evaluation, in constrast to advanced composition.

Papernot et al. [START_REF] Papernot | Semi-supervised knowledge transfer for deep learning from private training data[END_REF] introduced the PATE framework that uses the Laplace mechanism to provide privacy guarantees for a machine learning model trained in an ensemble manner. We comparatively evaluate the privacy guarantees provided by their moment accountant on MNIST dataset with the privacy guarantees obtained using privacy at risk. We do so by using privacy at risk while computing a data dependent bound [START_REF] Papernot | Semi-supervised knowledge transfer for deep learning from private training data[END_REF]Theorem 3]. Under the identical experimental setup, we use a 0.1-differentially private Laplace mechanism, which optimally satisfies (0.08, 0.8)-privacy at risk. We list the calculated privacy guarantees in Table 1. The reported privacy guarantee is the mean privacy guarantee over 30 experiments.

Balancing Utility and Privacy

In this section, we empirically illustrate and discuss the steps that a data steward needs to take and the issues that she needs to consider in order to realise a required privacy at risk level ε for a confidence level γ when seeking to disclose the result of a query.

We consider a query that returns the parameter of a ridge regression [START_REF] Murphy | Machine Learning: A Probabilistic Perspective[END_REF] for an input dataset. It is a basic and widely used statistical analysis tool. We use the privacy-preserving mechanism presented by Ligett et al. [START_REF] Ligett | Accuracy first: Selecting a differential privacy level for accuracy constrained erm[END_REF] for ridge regression. It is a Laplace mechanism that induces noise in the output parameters of the ridge regression. The authors provide a theoretical upper bound on the sensitivity of the ridge regression, which we refer as sensitivity, in the experiments.

Dataset and Experimental Setup.

We conduct experiments on a subset of the 2000 US census dataset provided by Minnesota Population Center in its Integrated Public Use Microdata Series [START_REF] Ruggles | Integrated public use microdata series: Version 6[END_REF]. The census dataset consists of 1% sample of the original census data. It spans over 1.23 million households with records of 2.8 million people. The value of several attributes is not necessarily available for every household. We have therefore selected 212, 605 records, corresponding to the household heads, and 6 attributes, namely, 1. Comparative analysis of privacy levels computed using three composition theorems when applied to 0.1-differentially private Laplace mechanism, which optimally satisfies (0.08, 0.8)-privacy at risk. The observations for the moment accountant on MNIST datasets are taken from [START_REF] Papernot | Semi-supervised knowledge transfer for deep learning from private training data[END_REF].

Age, Gender, Race, Marital Status, Education, Income, whose values are available for the 212, 605 records.

In order to satisfy the constraint in the derivation of the sensitivity of ridge regression [START_REF] Ligett | Accuracy first: Selecting a differential privacy level for accuracy constrained erm[END_REF], we, without loss of generality, normalise the dataset in the following way. We normalise Income attribute such that the values lie in [0, 1]. We normalise other attributes such that l 2 norm of each data point is unity.

All experiments are run on Linux machine with 12-core 3.60GHz Intel ® Core i7™processor with 64GB memory. Python ® 2.7.6 is used as the scripting language.

Result Analysis

We train ridge regression model to predict Income using other attributes as predictors. We split the dataset into the training dataset (80%) and testing dataset (20%). We compute the root mean squared error (RMSE) of ridge regression, trained on the training data with regularisation parameter set to 0.01, on the testing dataset. We use it as the metric of utility loss. Smaller the value of RMSE, smaller the loss in utility. For a given value of privacy at risk level, we compute 50 runs of an experiment of a differentially private ridge regression and report the means over the 50 runs of the experiment.

Let us now provide illustrative experiments under the three different cases. In every scenario, the data steward is given a privacy at risk level ε and the confidence level γ and wants to disclose the parameters of a ridge regression model that she trains on the census dataset. She needs to calibrate the Laplace mechanism by estimating either its privacy level ε 0 (Case 1) or sensitivity (Case 2) or both (Case 3) to achieve the privacy at risk required the ridge regression query.

The Case of Explicit Randomness (cf. Section 4.1). In this scenario, the data steward knows the sensitivity for the ridge regression. She needs to compute the privacy level, ε 0 , to calibrate the Laplace mechanism. She uses Equation 3 that links the desired privacy at risk level ε, the confidence level γ 1 and the privacy level of noise ε 0 . Specifically, for given ε and γ 1 , she computes ε 0 by solving the equation:

γ 1 P(T ≤ ε 0 ) -P(T ≤ ε) = 0.
Since the equation does not give an analytical formula for ε 0 , the data steward uses a root finding algorithm such as Newton-Raphson method [START_REF] William | Numerical recipes 3rd edition: The art of scientific computing[END_REF] to solve the above equation. For instance, if she needs to achieve a privacy at risk level ε = 0.4 with confidence level γ 1 = 0.6, she can substitute these values in the above equation and solve the equation to get the privacy level of noise ε 0 = 0.8.

Figure 6 shows the variation of privacy at risk level ε and confidence level γ 1 . It also depicts the variation of utility loss for different privacy at risk levels in Figure 6.

In accordance to the data steward's problem, if she needs to achieve a privacy at risk level ε = 0.4 with confidence level γ 1 = 0.6, she obtains the privacy level of noise to be ε 0 = 0.8. Additionally, we observe that the choice of privacy level 0.8 instead of 0.4 to calibrate the Laplace mechanism gives lower utility loss for the data steward. This is the benefit drawn from the risk taken under the control of privacy at risk. Thus, she uses privacy level ε 0 and the sensitivity of the function to calibrate Laplace mechanism.

The Case of Implicit Randomness (cf. Section 4.2). In this scenario, the data steward does not know the sensitivity of ridge regression. She assesses that she can afford to sample at most n times from the population dataset. She understands the effect of the uncertainty introduced by the statistical estimation of the sensitivity. Therefore, she uses the confidence level for empirical privacy at risk γ2 .

Given the value of n, she chooses the value of the accuracy parameter using Figure 2. For instance, if the number of samples that she can draw is 10 4 , she chooses the value of the accuracy parameter ρ = 0.01. Next, she uses Equation 13 to determine the value of probabilistic tolerance, α, for the sample size n. For instance, if the data steward is not allowed to access more than 15, 000 samples, for the accuracy of 0.01 the probabilistic tolerance is 0.9.

α = 1 -2e (-2ρ 2 n) ( 13)
She constructs an empirical cumulative distribution over the sensitivities as described in Section 4.2. Such an empirical cumulative distribution is shown in Figure 7.

Using the computed probabilistic tolerance and desired confidence level γ2 , she uses equation in Theorem 5 to determine γ 2 . She computes the sampled sensitivity using the empirical distribution function and the confidence level for privacy ∆ S f at risk γ 2 . For instance, using the empirical cumulative distribution in Figure 7 she calculates the value of the sampled sensitivity to be approximately 0.001 for γ 2 = 0.4 and approximately 0.01 for γ 2 = 0.85 Thus, she uses privacy level ε, sets the number of samples to be n and computes the sampled sensitivity ∆ S f to calibrate the Laplace mechanism.

The Case of Explicit and Implicit Randomness (cf. Section 4.3). In this scenario, the data steward does not know the sensitivity of ridge regression. She is not allowed to sample more than n times from a population dataset. For a given confidence level γ 2 and the privacy at risk ε, she calibrates the Laplace mechanism using illustration for Section 4.3. The privacy level in this calibration yields utility loss that is more than her requirement. Therefore, she wants to re-calibrate the Laplace mechanism in order to reduce utility loss.

For the re-calibration, the data steward uses privacy level of the pre-calibrated Laplace mechanism, i.e. ε, as the privacy at risk level and she provides a new confidence level for empirical privacy at risk γ3 . Using Equation 25 and Equation 23, she calculates:

γ3 P(T ≤ ηε 0 ) -αγ 2 P(T ≤ ε) = 0
She solves such an equation for ε 0 using the root finding technique such as Newton-Raphson method [START_REF] William | Numerical recipes 3rd edition: The art of scientific computing[END_REF]. For instance, if she needs to achieve a privacy at risk level ε = 0.4 with confidence levels γ3 = 0.9 and γ 2 = 0.9, she can substitute these values and the values of tolerance parameter and sampled sensitivity, as used in the previous experiments, in the above equation. Then, solving the equation leads to the privacy level of noise ε 0 = 0.8.

Thus, she re-calibrates the Laplace mechanism with privacy level ε 0 , sets the number of samples to be n and sampled sensitivity ∆ S f .

Related Work

Calibration of mechanisms. Researchers have proposed different privacy-preserving mechanisms to make different queries differentially private. These mechanisms can be broadly classified into two categories. In one category, the mechanisms explicitly add calibrated noise, such as Laplace noise in the work of [START_REF] Dwork | Calibrating Noise to Sensitivity in Private Data Analysis[END_REF] or Gaussian noise in the work of [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF], to the outputs of the query. In the other category, [START_REF] Acs | Differentially private histogram publishing through lossy compres-sion[END_REF][START_REF] Chaudhuri | Differentially private empirical risk minimization[END_REF][START_REF] Hall | Differential privacy for functions and functional data[END_REF][START_REF] Zhang | Functional mechanism: regression analysis under differential privacy[END_REF] propose mechanisms that alter the query function so that the modified function satisfies differentially privacy. Privacy-preserving mechanisms in both of these categories perturb the original output of the query and make it difficult for a malicious data analyst to recover the original output of the query. These mechanisms induce randomness us-ing the explicit noise distribution. Calibration of these mechanisms require the knowledge of the sensitivity of the query. Nissim et al. [START_REF] Nissim | Smooth sensitivity and sampling in private data analysis[END_REF] consider the implicit randomness in the data-generation distribution to compute an estimate of the sensitivity. The authors propose the smooth sensitivity function that is an envelope over the local sensitivities for all individual datasets. Local sensitivity of a dataset is the maximum change in the value of the query over all of its neighboring datasets. In general, it is not easy to analytically estimate the smooth sensitivity function for a general query. Rubinstein et al. [START_REF] Benjamin Ip Rubinstein | Pain-free random differential privacy with sensitivity sampling[END_REF] also study the inherent randomness in the datageneration algorithm. We adopt their approach of sampling the sensitivity from the empirical distribution of the sensitivity. They use order statistics to choose a particular value of the sensitivity. We use the risk, which provides a mediation tool for business entities to assess the actual business risks, on the sensitivity distribution to estimate the sensitivity.

Refinements of differential privacy. In order to account for both sources of randomness, refinements of ε-differential privacy are proposed in order to bound the probability of occurrence of worst case scenarios. Machanavajjhala et al. [START_REF] Machanavajjhala | Privacy: Theory meets practice on the map[END_REF] propose probabilistic differential privacy that considers upper bounds of the worst case privacy loss for corresponding confidence levels on the noise distribution. Definition of probabilistic differential privacy incorporates the explicit randomness induced by the noise distribution and bounds the probability over the space of noisy outputs to satisfy the ε-differential privacy definition. Dwork et al. [START_REF] Dwork | Concentrated differential privacy[END_REF] propose Concentrated differential privacy that considers the expected values of the privacy loss random variables for the corresponding. Definition of concentrated differential privacy incorporates the explicit randomness induced by the noise distribution but considering only the expected value of privacy loss satisfying ε-differential privacy definition instead of using the confidence levels limits its scope.

Hall et al. [START_REF] Hall | Differential privacy for functions and functional data[END_REF] propose random differential privacy that considers the privacy loss for corresponding confidence levels on the implicit randomness in the datageneration distribution. Definition of random differential privacy incorporates the implicit randomness induced by the data-generation distribution and bounds the probability over the space of datasets generated from the given distribution to satisfy the ε-differential privacy definition. Dwork et al. [START_REF] Dwork | Our data, ourselves: Privacy via distributed noise generation[END_REF] define approximate differential privacy by adding a constant bias to the privacy guarantee provided by the differential privacy. It is not a probabilistic refinement of the differential privacy.

Around the same time of our work, Triastcyn et al. [START_REF] Triastcyn | Federated learning with bayesian differential privacy[END_REF] independently propose Bayesian differential privacy that takes into account both of the sources of randomness. Despite this similarity, our works differ in multiple dimensions. Firstly, they have shown the reduction of their definition to a variant of Renyi differential privacy. The variant depends on the data-generation distribution. Secondly, they rely on the moment accountant for the composition of the mechanisms. Lastly, they do not provide a finer case-by-case analysis of the source of randomness, which leads to analytical solutions for the privacy guarantee.

Kifer et al. [START_REF] Kifer | A rigorous and customizable framework for privacy[END_REF] define Pufferfish privacy framework, and its variant by Bassily et al. [START_REF] Bassily | Coupled-worlds privacy: Exploiting adversarial uncertainty in statistical data privacy[END_REF], that considers randomness due to data-generation distribution as well as noise distribution. Despite the generality of their approach, the framework relies on the domain expert to define a set of secrets that they want to protect.

We refer interested readers to [START_REF] Desfontaines | Sok: Differential privacies[END_REF] for an extensive review of the differential privacy and its refinements.

Composition theorem. Recently proposed technique of the moment accountant [START_REF] Abadi | Deep learning with differential privacy[END_REF] has become the state-of-the-art of composing mechanisms in the area of privacy-preserving machine learning. Abadi et al. show that the moment accountant provides much strong privacy guarantees than the conventional composition mechanisms. It works by keeping track of various moments of privacy loss random variable and use the bounds on them to provide privacy guarantees. The moment accountant requires access to data-generation distribution to compute the bounds on the moment. Hence, the privacy guarantees are specific to the dataset.

Cost models. [START_REF] Chen | Truthful mechanisms for agents that value privacy[END_REF][START_REF] Ghosh | Selling privacy at auction[END_REF] propose game theoretic methods that provide the means to evaluate the monetary cost of differential privacy. Pejó et al. [START_REF] Pejo | Together or alone: The price of privacy in collaborative learning[END_REF] also propose a game theoretic cost model in the setting of private collaborative learning. Our approach is inspired by the approach in the work of Hsu et al. [START_REF] Hsu | Differential privacy: An economic method for choosing epsilon[END_REF]. They model the cost under a scenario of a research study wherein the participants are reimbursed for their participation. Our cost modelling is driven by the scenario of securing a compensation budget in compliance with GDPR. Our requirement differs from the requirements of [START_REF] Hsu | Differential privacy: An economic method for choosing epsilon[END_REF], particularly in our model participants do not have any monetary incentive to share their data.

Conclusion and Future Works

In this paper, we provide a means to fine-tune the privacy level of a privacy-preserving mechanism by analysing various sources of randomness. Such a finetuning leads to probabilistic quantification on privacy levels with quantified risks, which we call as privacy at risk. We also provide composition theorem that leverages privacy at risk. We analytical calculate privacy at risk for Laplace mechanism. We propose a cost model that bridges the gap between the privacy level and the compensation budget estimated by a GDPR compliant business entity. Convexity of the cost function ensures existence of unique privacy at risk that minimises compensation budget. The cost model helps in not only reinforcing the ease of application in a business setting but also providing stronger privacy guarantees on the composition of mechanism.

It is possible to instantiate privacy at risk for Gaussian mechanism. The mechanism is (ε, δ)-differential private for γ = 0 and a non-zero risk calculated by accounting for the sources of randomness. We save it for future work. Privacy at risk may be fully analytically computed in cases where the data-generation, or the sensitivity distribution, the noise distribution and the query are analytically known and take convenient forms. We are now looking at such convenient but realistic cases.

A Proof of Theorem 2 (Section 3)

Proof. Let us fix a pair of neighbouring datasets x and y, and also fix a subset of outputs Z ⊆ Range(M). Choose OUT ⊆ Z such that

OUT z ∈ Z P(M(f, Θ)(x) = z) P(M(f, Θ)(y) = z) > e ε
Thus, we also obtain a complementary set of outputs Z \ OUT, where the privacy loss is upper bounded i.e.

P(M(f, Θ)(x) = z) ≤ e ε P(M(f, Θ)(y) = z). Thus,

P(M(f, Θ)(x) ∈ Z) = P(M(f, Θ)(x) ∈ Z\OUT) + P(M(f, Θ)(x) ∈ OUT) ≤ (a) e ε P(M(f, Θ)(y) ∈ Z\OUT) + P(M(f, Θ)(x) ∈ OUT) ≤ (b) e ε P(M(f, Θ)(y) ∈ Z \ OUT) + γ ≤ e ε P(M(f, Θ)(y) ∈ Z) + γ (a)

B Proof of Theorem 4 (Section 4.1)

Although a Laplace mechanism L ∆ f ε induces higher amount of noise on average than a Laplace mechanism L ∆ f ε0 for ε < ε 0 , there is a non-zero probability that L ∆ f ε induces noise commensurate to L ∆ f ε0 . This non-zero probability guides us to calculate the privacy at risk γ 1 for the privacy at risk level ε. In order to get an intuition, we illustrate the calculation of the overlap between two Laplace distributions as an estimator of similarity between the two distributions. Definition 8. [Overlap of Distributions, [START_REF] Papoulis | Probability, random variables, and stochastic processes[END_REF]] The overlap, O, between two probability densities P 1 , P 2 with support X is defined as

O = X min[P 1 (x), P 2 (x)] dx.

Lemma 5. The overlap O between two probability distributions, Lap(

∆ f ε1 ) and Lap( ∆ f ε2 ), such that ε 2 ≤ ε 1 , is given by O = 1 -(exp (-µε 2 /∆ f ) -exp (-µε 1 /∆ f )), where µ = ∆ f ln (ε1/ε2) ε1-ε2
.

Using the result in Lemma 5, we note that the overlap between two distributions with ε 0 = 1 and ε = 0.6 is 0.81. Thus, L ∆ f 0.6 induces noise that is more than 80% times similar to the noise induced by L ∆ f 1.0 . Therefore, we can loosely say that at least 80% of the times a Laplace Mechanism L ∆ f 1.0 will provide the same privacy as a Laplace Mechanism L ∆ f 0.8 . Although the overlap between Laplace distributions with different scales offers an insight into the relationship between different privacy levels, it does not capture the constraint induced by the sensitivity. For a given query f , the amount of noise required to satisfy differential privacy is commensurate to the sensitivity of the query. This calibration puts a constraint on the noise that is required to be induced on a pair of neighbouring datasets. We state this constraint in Lemma 6, which we further use to prove that the Laplace Mechanism L

→ R k . For any output z ∈ R k of the Laplace Mechanism L ∆ f ε0 , k i=1 (|f (y i ) -z i | -|f (x i ) -z i |) ≤ k i=1 (|f (x i ) -f (y i )|) ≤ ∆ f .
We use triangular inequality in the first step and Definition 2 of sensitivity in the second step.

We write Exp(b) to denote a random variable sampled from an exponential distribution with scale b > 0. We write Gamma(k, θ) to denote a random variable sampled from a gamma distribution with shape k > 0 and scale θ > 0.

Lemma 7. [[35]] If a random variable

P T (t; n, θ) = 2 2-n t n-1 2 K n-1 2 (t) √ 2πΓ(n)θ where K n-1 2
is the modified Bessel function of second kind.

Proof. Let X 1 and X 2 be two i.i.d. Gamma(n, θ) random variables. Characteristic function of a Gamma random variable is given as

φ X1 (z) = φ X2 (z) = (1 -ιzθ) -n . Therefore, φ X1-X2 (z) = φ X1 (z)φ * X2 (z) = 1 (1 + (zθ) 2 ) n
Probability density function for the random variable X 1 -X 2 is given by,

P X1-X2 (x) = 1 2π ∞ -∞ e -izx φ X1-X2 (z)dz = 2 1-n | x θ | n-1 2 K n-1 2 (| x θ |) √ 2πΓ(n)θ where K n-1 2
is the Bessel function of second kind. Let

T = | X1-X2 θ |. Therefore, P T (t; n, θ) = 2 1-n t n-1 2 K n-1 2 (t) √ 2πΓ(n)θ
We use Mathematica [START_REF][END_REF] to solve the above integral.

∆ f ε0 ), ε ≤ ε 0 , γ 1 P ln P(L ∆ f ε0 (x) ∈ Z) P(L ∆ f ε0 (y) ∈ Z) ≤ ε = P(T ≤ ε) P(T ≤ ε 0 )
, where T follows the distribution in Lemma 9, P T (t; k,

∆ f ε0 ).
Proof. Let, x ∈ D and y ∈ D be two datasets such that x ∼ y. Let f : D → R k be some numeric query. Let P x (z) and P y (z) denote the probabilities of getting the output z for Laplace mechanisms L ∆ f ε0 (x) and L ∆ f ε0 (y) respectively. For any point z ∈ R k and ε = 0,

P x (z) P y (z) = k i=1 exp -ε0|f (xi)-zi| ∆ f exp -ε0|f (yi)-zi| ∆ f = k i=1 exp ε 0 (|f (y i ) -z i | -|f (x i ) -z i |) ∆ f = exp ε ε 0 k i=1 (|f (y i ) -z i | -|f (x i ) -z i |) ε∆ f . ( 14
)
By Definition 4,

(f (x) -z), (f (y) -z) ∼ Lap(∆ f /ε 0 ). (15)
Application of Lemma 7 and Lemma 8 yields,

k i=1 (|f (x i ) -z i |) ∼ Gamma(k, ∆ f /ε 0 ). (16)
Using Equations 15, 16, and Lemma 6, 10, we get

ε 0 ∆ f k i=1 |(|f (y i ) -z| -|f (x i ) -z|)| ∼ P T (t; k, ∆ f /ε 0 , ∆ f ). (17) since, k i=1 |(|f (y i ) -z| -|f (x i ) -z|)| ≤ ∆ f . There- fore, P ε 0 ∆ f k i=1 |(|f (y i ) -z| -|f (x i ) -z|)| ≤ ε = P(T ≤ ε) P(T ≤ ε 0 ) , (18)
where T follows the distribution in Lemma 9. We use Mathematica [START_REF][END_REF] to analytically compute,

P(T ≤ x) ∝ 1 F 2 ( 1 2 ; 3 2 -k, 3 2 ; x 2 4 ) √ π4 k x] - 2 1 F 2 (k; 1 2 + k, k + 1; x 2 4 )x 2k Γ(k)
where 1 F 2 is the regularised generalised hypergeometric function as defined in [START_REF] Ra Askey | Generalized hypergeometric functions and meijer g-function[END_REF]. From Equation 14

∆ S f = exp ε k i=1 (|f (y i ) -z i | -|f (x i ) -z i |) ∆ S f ≤ exp ε k i=1 |f (y i ) -f (x i )| ∆ S f = exp ε f (y) -f (x) 1 ∆ S f ( 19
)
We used triangle inequality in the penultimate step. Using the trick in the work of [START_REF] Benjamin Ip Rubinstein | Pain-free random differential privacy with sensitivity sampling[END_REF], we define following events. Let, B ∆ S f denotes the set of pairs neighbouring dataset sampled from G for which the sensitivity random variable is upper bounded by ∆ S f . Let, C

∆ S f ρ denotes the set of sensitivity random variable values for which F n deviates from the unknown cumulative distribution of S, F , at most by the accuracy value ρ. These events are defined in Equation 20.

B ∆ S f {x, y ∼ G such that f (y) -f (x) 1 ≤ ∆ S f } C ∆ S f ρ sup ∆ |F n S (∆) -F S (∆)| ≤ ρ (20)
Thus, we obtain

P B ∆ S f = P B ∆ S f C ∆ S f ρ P C ∆ S f ρ + P B ∆ S f C ∆ S f ρ P C ∆ S f ρ ≥ P B ∆ S f C ∆ S f ρ P C ∆ S f ρ = F n (∆ S f )P C ∆ S f ρ ≥ γ 2 • 1 -2e -2ρ 2 n (21)
In the last step, we use the definition of the sampled sensitivity to get the value of the first term. The last term is obtained using DKW-inequality, as defined in [START_REF] Massart | The tight constant in the dvoretzkykiefer-wolfowitz inequality[END_REF], where the n denotes the number of samples used to build empirical distribution of the sensitivity, F n . From Equation 19, we understand that if f (y)f (x) 1 is less than or equals to the sampled sensitivity then the Laplace mechanism L ∆ S f ε satisfies ε-differential privacy. Equation 21provides the lower bound on the probability of the event f (y) -f (x) 1 ≤ ∆ S f . Thus, combining Equation 19 and Equation 21 completes the proof.

D Proof of Theorem 6 (Section 4.3)

Proof of Theorem 6 builds upon the ideas from the proofs for the rest of the two cases. In addition to the events defined in Equation 20, we define an additional event A

∆ S f ε0 , defined in Equation 22, as a set of outputs of Laplace mechanism L ∆ S f ε0 that satisfy the constraint of ε-differential privacy for a specified privacy at risk level ε. where T follows the distribution P T (t; ∆ S f /ε 0 ) and η = ∆ f ∆ S f . For this case, we do not assume the knowledge of the sensitivity of the query. Using the empirical estimation presented in Section 4.2, if we choose the sampled sensitivity for privacy at risk γ 2 = 1, we obtain an approximation for η. |F n (F -1 n (1)) -

F n (F -1 (1))| ≤ |F -1 n (1) -F -1 (1)| |F n (F -1 n (1)) -F n (F -1 (1))| ≤ |∆ * S f -∆ f | ρ ≤ ∆ f -∆ * S f 1 + ρ ∆ * S f ≤ ∆ f ∆ * S f
where we used result from Equation 23 where n is the number of samples used to find sampled sensitivity, ρ ∈ [0, 1] is a accuracy parameter and η =

∆ f ∆ S f
. The outer probability is calculated with respect to support of the data-generation distribution G.

Proof. The proof follows from the proof of Lemma 11 and Lemma 13. Consider,

P(A ∆ S f ε0 ) ≥ P(A ∆ S f ε0 |B ∆ S f )P(B ∆ S f |C ∆ S f ρ )P(C ∆ S f ρ ) ≥ P(T ≤ ε) P(T ≤ ηε 0 ) • γ 2 • (1 -2e -2ρ 2 n ) (24)
The first term in the final step of Equation 24follows from the result in Corollary 4 where T follows BesselK(k,

∆ S f ε0
). It is the probability with which the Laplace mechanism L ∆ S f ε0 satisfies ε-differential privacy for a given value of sampled sensitivity.

Probability of occurrence of event A

∆ S f ε0 calculated by accounting for both explicit and implicit sources of randomness gives the risk for privacy level ε. Thus, the proof of Lemma 13 completes the proof for Theorem 6.

Comparing the equations in Theorem 6 and Lemma 13, we observe that

γ 3 P(T ≤ ε) P(T ≤ ηε 0 ) • γ 2 (25)
The privacy at risk, as defined in Equation 25, is free from the term that accounts for the accuracy of sampled estimate. If we know cumulative distribution of the sensitivity, we do not suffer from the uncertainty of introduced by sampling from the empirical distribution.

  the i th component of f (x).

Theorem 5 .

 5 Analytical bound on the empirical risk, γ2 , for Laplace mechanism L ∆ S f ε with privacy level ε and sampled sensitivity ∆ S f for a query

Fig. 1 .Fig. 2 .

 12 Fig.1. Privacy level ε for varying privacy at risk γ 1 for Laplace mechanism L 1.0 ε 0 . In Figure1a, we use ε 0 = 1.0 and different values of k. In Figure1b, for k = 1 and different values of ε 0 .

Fig. 3 .

 3 Fig. 3. Dependence of error and number of samples on the privacy at risk for Laplace mechanism L ∆ S f 1.0 . For the figure on the left hand side, we fix the number of samples to 10000. For the Figure 3b we fix the error parameter to 0.01.

Fig. 4 .

 4 Fig. 4. Variation in the budget for Laplace mechanism L 1 ε 0 under privacy at risk considering explicit randomness in the Laplace mechanism for the illustration in Section 5.3.

  for ε0 = 0.10, δ = 10(5 Basic Com osition[START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF] Advanced Com osition[START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF] Com osition with Privacy at Risk (a) L 1 0.1 satisfies (0.08, 0.80)-privacy at risk. le(el after co position (ε ′ ) Ad(anced co position for ε0 = 0.50, δ = 10 -5 Basic Co position[10] Ad(anced Co position[10] Co position )ith Pri(acy at Risk (b) L 1 0.5 satisfies (0.27, 0.61)-privacy at risk. for ε0 = 1.00, δ = 10 -5

Fig. 6 .

 6 Fig. 6. Utility, measured by RMSE (right y-axis), and privacy at risk level ε for Laplace mechanism (left y-axis) for varying confidence levels γ 1 .

Fig. 7 .

 7 Fig. 7. Empirical cumulative distribution of the sensitivities of ridge regression queries constructed using 15000 samples of neighboring datasets.

  is obtained from the fact that the privacy loss is upper bounded in the complimentary set of outputs Z \ OUT. (b) is a consequence of the definition of (ε, γ) privacy at risk. The definition upper bounds the probability measures of the subset OUT by γ.

Lemma 6 .

 6 ∆ f ε0satisfies (ε, γ 1 )-privacy at risk. For a Laplace Mechanism L ∆ f ε0 , the difference in the absolute values of noise induced on a pair of neighbouring datasets is upper bounded by the sensitivity of the query.Proof. Suppose that two neighbouring datasets x and y are given input to a numeric query f : D

Corollary 3 . 2 )

 32 and 18, P ln P(L ∆ f ε0 (x) ∈ S) P(L ∆ f ε0 (y) ∈ S) ≤ ε = P(T ≤ ε) P(T ≤ ε 0 ) . This completes the proof of Theorem 4. Laplace Mechanism L ∆ f ε0 with f : D → R k satisfies (ε, δ)-probabilistic differentially private where δ = 1 -P(T ≤ε) P(T ≤ε0) ε ≤ ε 0 0 ε > ε 0 and T follows BesselK(k, ∆ f /ε 0 ). Proof. Let, x and y be any two neighbouring datasets sampled from the data generating distribution G. Let, ∆ S f be the sampled sensitivity for query f : D → R k . Let, P x (z) and P y (z) denote the probabilities of getting the output z for Laplace mechanisms L ∆ S f ε (x) and L ∆ S f ε (y) respectively. For any point z ∈ R k and ε = 0, P x (z) P y (z) = k i=1 exp -ε|f (xi)-zi| ∆ S f exp -ε|f (yi)-zi|

A

  ≤ ε) P(T ≤ ηε 0 )where T follows the distribution P T (t; ∆ S f /ε 0 ) in Lemma 9 and η = ∆ f ∆ S f . Proof. We provide the sketch of the proof. Proof follows from the proof of Lemma 11. For a Laplace mechanism calibrated with the sampled sensitivity ∆ S f and privacy level ε 0 , Equation 17 translates to,ε 0 ∆ S f k i=1 |(|f (y i ) -z| -|f (x i ) -z|)| ∼ P T (t; k, ∆ S f /ε 0 , ∆ S f ). since, k i=1 |(|f (y i ) -z| -|f (x i ) -z|)| ≤ ∆ f .Using Lemma 10 and Equation 18, ≤ ε) P(T ≤ ηε 0 )

Lemma 12 .for some k ≥ 1 .

 121 For a given value of accuracy parameter ρ,Proof. For a given value of accuracy parameter ρ and any ∆ > 0,F n (∆) -F (∆) ≤ ρSince above inequality is true for any value of ∆, let ∆ = F -1 (1). Therefore,F n (F -1 (1)) -F (F -1 (1)) ≤ ρ F n (F -1 (1)) ≤ 1 + ρ (23)Since a cumulative distribution function is 1-Lipschitz [[START_REF] Papoulis | Probability, random variables, and stochastic processes[END_REF]],

in step 3 Lemma 13 .

 313 For Laplace Mechanism L ∆ S f ε0 with sampled sensitivity ∆ S f of a query f : D → R k and for anyZ ⊆ Range(L ∆ S f ε ), P ln P(L ε0 (x) ∈ Z) P(L ε0 (y) ∈ Z) ≤ ε ≥ P(T ≤ ε) P(T ≤ ηε 0 ) γ 2 (1-2e -2ρ 2 n )

  X follows Laplace Distribution with mean zero and scale b, |X| ∼ Exp(b). If X 1 and X 2 are two i.i.d. Gamma(n, θ) random variables, the probability density function for the random variable T = |X 1 -X 2 |/θ is given by

	Lemma 9.
	Lemma 8. [[35]] If X 1 , ..., X n are n i.i.d. random vari-
	ables each following the Exponential Distribution with
	scale b,

n i=1 X i ∼ Gamma(n, b).

A widely-used (ε, δ)-differential privacy is not a probabilistic relaxation of differential privacy[START_REF] Meiser | Approximate and probabilistic differential privacy definitions[END_REF].

Acknowledgement

This work was supported by the National Research Foundation (NRF) Singapore under its Corporate Laboratory@University Scheme, National University of Singapore, and Singapore Telecommunications Ltd. This research was also funded in part by the BioQOP project of the French ANR (ANR-17-CE39-0006). We thank Pierre Senellart for his help in reviewing derivations of privacy at risk for the Laplace mechanism.