# On Estimating the Strength of Differentially Private Mechanisms in a Black-Box Setting

Daniele Gorla, Louis Jalouzot, Federica Granese, Catuscia Palamidessi, Pablo Piantanida

► To cite this version:

Daniele Gorla, Louis Jalouzot, Federica Granese, Catuscia Palamidessi, Pablo Piantanida. On Estimating the Strength of Differentially Private Mechanisms in a Black-Box Setting. IEEE Transactions on Dependable and Secure Computing, 2025, 22 (5), pp.5494-5507. 10.1109/TDSC.2025.3568160. hal-05454091

HAL Id: hal-05454091

https://hal.science/hal-05454091v1

Submitted on 21 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# On Estimating the Strength of Differentially Private Mechanisms in a Black-Box Setting

Daniele Gorla, Louis Jalouzot, Federica Granese, Catuscia Palamidessi, and Pablo Piantanida, Senior Member, IEEE

**Abstract**—We analyze to what extent final users can infer information about the level of protection of their data when the data obfuscation mechanism is a priori unknown to them (the so-called “black-box” scenario). In particular, we explore four notions of differential privacy, namely local/central ε-DP/Rényi-DP. On the one hand, we prove that, without any assumption on the underlying distributions, it is not possible to have an algorithm able to infer the level of data protection with provable guarantees. On the other hand, we demonstrate that, under reasonable assumptions (namely Lipschitzness of the involved densities on a closed interval), such guarantees exist for the local versions and can be achieved by a simple histogram-based estimator. We validate our results experimentally and note that, in two particularly well behaved distributions (namely the Laplace and the Gaussian noise), our method performs better than expected, in the sense that in practice the number of samples needed to achieve the desired confidence is smaller than the theoretical bound, and the estimate of ε is more precise than predicted.

**Index Terms**—Differential privacy, local differential privacy, rényi differential privacy, the impossibility of provable guarantees, histogram-based sampling.

## I. INTRODUCTION

DIFFERENTIAL privacy (DP) [1] is nowadays one of the best established and theoretically solid tools to ensure data protection. The success of this privacy notion is testified by its wide application, both in academia and in industry (see, e.g. [2], [3], [4], [5], [6], [7], [8]). The classical notion of differential privacy relies on a central model in which a trusted authority, the provider, receives all user data in clear without any privacy

concern. The provider then privatizes the received data by ensuring privacy and utility constraints. Starting from this basic notion, a few variants have been proposed in the literature. The first variant is a distributed version of DP, called *local differential privacy* (LDP) [9]. In this setting, users obfuscate their data by themselves before sending them to the provider; therefore, the privacy constraints can be satisfied locally. A second variant is the so-called *Rényi differential privacy* (RDP) [10], a relaxation of DP based on the notion of Rényi divergence. This notion has been introduced to remedy some unsatisfactory aspects of $(\epsilon, \delta)$-DP [11], and it is well suited to express guarantees of privacy-preserving algorithms and to compose heterogeneous mechanisms. All such notions of DP are built into existing software products by the producing companies, which also declare the claimed level of privacy $\epsilon$ of their mechanisms (that is, the strength of their products). Thus, a milestone for the final users is to have ways to determine whether the claims are valid or not.

In the literature, many examples exist [12], [13], [14], [15], [16], [17], [18], [19] (to cite a few) for testing the level of privacy when the obfuscation mechanism is known (the so-called “white-box” scenario). White-box audits require full access to the mechanism’s source code (the program) and use language-based methods (e.g., static analysis or symbolic evaluation) to verify the privacy level. White-box estimators automatically search and infer a proof of the DP property for the tested mechanism, hence the result (satisfying DP or not) is accurate if they do succeed; however, the verification may fail. Furthermore, even if a white-box method certifies that the algorithm is $\epsilon$-DP, there may be implementation errors that lead to a different $\epsilon'$ or to a complete violation of the differential privacy property.

When you do not have access to the code (for example, because it is proprietary, or you do not trust the code provider), white-box methods are not applicable. Then, the only way for interacting with the mechanism is by providing inputs and observing the resulting output; this is the “black-box” approach. Directly testing the actual mechanism has the advantage of also detecting implementation errors; however, this may need to repeat the execution on the same input a large number of times. Indeed, since a DP mechanism is a probabilistic function obtained by sampling from a noise distribution, different executions with the same input typically produce different outputs, with varying frequencies. This process can be time-consuming and, as we prove in this paper, in some cases it is not even possible to establish how many times we need to execute the test. Nevertheless, recently a few attempts have been done to

Received 31 January 2024; revised 11 April 2025; accepted 23 April 2025. Date of publication 8 May 2025; date of current version 4 September 2025. The work of Catuscia Palamidessi was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under Grant 835294. (Daniele Gorla and Louis Jalouzot contributed equally to the work.) (Corresponding author: Daniele Gorla.)

Daniele Gorla is with the Department of Computer Science, Sapienza University of Rome, 00185 Roma, Italy (e-mail: gorla@di.uniroma1.it).

Louis Jalouzot is with the Department of Computer Science, ENS de Lyon, 69342 Lyon, France.

Federica Granese is with Inria & Université Côte d'Azur, 06560 Valbonne, France.

Catuscia Palamidessi is with Lix, Inria, Institute Polytechnique de Paris, 91120 Palaiseau, France.

Pablo Piantanida is with International Laboratory on Learning Systems (ILLS), Quebec AI Institute (MILA), Montréal, QC H2S 3H1, Canada, and also with CNRS, CentraleSupélec Université Paris-Saclay, 91190 Gif-sur-Yvette, France.

This article has supplementary downloadable material available at https://doi.org/10.1109/TDSC.2025.3568160, provided by the authors.

Digital Object Identifier 10.1109/TDSC.2025.3568160
<figure><img src="image_2.png" /><figcaption>Fig. 1. $\mathcal{X}$ represents the set of adjacent databases in the *central* differential privacy and the set of values in the *local* one; $\mathcal{X}$ denotes a variable representing the value on which the obfuscation mechanism is applied and $Z = \mathcal{K}(\mathcal{X})$. The double arrow means that the user can sample multiple times from the corresponding distributions, i.e., $p_{Z|\mathcal{X}}(z|x_1)$ and $p_{Z|\mathcal{X}}(z|x_2)$. The guarantees the user can specify are: the *precision* $\gamma$ (how far can the claimed $\epsilon$ and the estimated one $\tilde{\epsilon}$ be) and the *confidence* $\delta$ (the probability that the specified precision holds).</figcaption></figure>

audit DP mechanisms in a black-box setting [20], [21], [22], [23], [24], [25], [25], [26], [27], [28], [29], [30]. However, none of such works are able to provide formal guarantees about the estimation provided (in terms of the specified confidence and precision required), together with an upper bound on the number of samples needed to achieve the given guarantees; hence, we want to study to what extent such guarantees are possible. This is in practice the only way for final users to know (with a chosen amount of certainty) whether they can trust the provider or not; this testifies the practical impact and the significance of our study.

We pictorially represent our framework in Fig. 1. The entity depicted in pink represents the *provider*, responsible for the obfuscation mechanism (that is any probabilistic function $\mathcal{K}: \mathcal{X} \rightarrow \mathcal{DZ}$, where $\mathcal{DZ}$ represents the set of probability distributions on $\mathcal{Z}$ and $z \sim \mathcal{K}(x)$ is the reported answer); the entity in blue signifies the *user*, who attempts to ascertain if the claimed level of privacy $\epsilon$ closely aligns, with provable guarantees, with the one she has estimated, i.e. $\tilde{\epsilon}$. We focus on the central and local notions of $\epsilon$-DP (aka *pure* DP) and RDP because there are very few works in the literature that deal with the estimation of their strength, whereas there are quite a few works for $(\epsilon, \delta)$-DP (aka *approximate* DP) — see Table I. Although approximate DP may be more commonly adopted than pure DP, because of its better compositionality property (that leads to less utility degradation), there are still several works that propose the use of pure DP mechanisms: e.g., in the context of location-privacy [31], [32], of image processing [33], [34], natural language processing [35], [36], [37], [38], and personalized FL [39], [40]. All the above proposals use the Laplace mechanism, apart from [38], which uses the von Mises Fisher (VMF) mechanism [41].

To achieve our goals, in Section II we provide the basic notions on differential privacy and C-Lipschitzness. First, in Section III-A we prove that, for every $\gamma > 0$ (precision), $0 < \delta < 1$ (confidence), and probabilistic estimator algorithm $\tilde{\epsilon}$ that almost surely terminates, there exists a probability distribution $p_{Z|\mathcal{X}}$ such that the estimated value for $\epsilon$ differs from the real one by at least $\gamma$ with probability at least $1 - \delta$ (see Theorem 1).

Then, in Section III-B, we focus on the continuous case and on the estimation of $\epsilon$ for a specific pair of values $(x_1, x_2)$. We start by showing that, whenever the densities $p_{Z|\mathcal{X}}(\cdot|x_1)$ and $p_{Z|\mathcal{X}}(\cdot|x_2)$ over a closed interval are C-Lipschitz (for a

proper constant $C$), there exists a probabilistic histogram-based estimator that outputs an answer that differs from the real $\epsilon$ for at most $\gamma$ with probability at least $\delta$, for every $\gamma > 0$ (precision) and $0 < \delta < 1$ (confidence) (see Theorem 2). A key point here is having a Lipschitz mechanism, something on which the provider can lie as well. For this reason, we implement in Section III-C a safety check derived from a necessary condition for Lipschitzness: by making multiple executions of the estimator, one can empirically argue if the provider lied by comparing the obtained probability with the theoretical lower bound from Theorem 3.

Once we have this estimator for a single pair of values, in Section III-D we discuss how to estimate the overall $\epsilon$ (that is obtained as the sup of the $\epsilon$ for all the possible pairs). To this aim, we divide $\mathcal{X}$ into $k$ buckets (for a proper $k$), take the mid-points of all the buckets, run the previous estimator for all pairs of mid-points, and return the maximum. We prove that, if we also assume $p_{Z|\mathcal{X}}(z|\cdot)$ to be D-Lipschitz for some $D$ and for all $z \in \mathcal{Z}$, this new algorithm can estimate the overall $\epsilon$ with provable guarantees (see Theorem 4).

In Section III-E, we first show that the Lipschitzness assumptions required by our theorems are met by the two most widely used DP mechanisms, namely the Laplace and the Gaussian [42], [43], and we validate all our results for both.

However, since our estimator assumes that $\mathcal{Z}$ is a closed interval, we must rely on the *truncated* variations of such distributions [44]. We first consider the number of samples the estimator does; this parameter depends on $\gamma$, $\delta$, $C$ and $|\mathcal{Z}|$, with the strongest dependency being on $\gamma$. Then, we compare the estimated $\epsilon$ against the real one and we discover that the number of samples required for satisfactory results in practice is significantly lower than the theoretical one. Finally, we also practically verify that the safety check for C-Lipschitzness is valuable to discover whether the actual $C$ is close to the claimed one.

In Section IV, we adapt all these results to the notions of LRDP. The changes needed for the impossibility result are relatively minor, whereas the estimators, even if formally very similar, require more complex bounds both on the number of experiments and on the number of intervals required; furthermore, the proofs of the desired guarantees are more technical. Then, we run experiments similar to the ones for LDP that confirm the quality of our approach also for LRDP. In particular, for this
<table><caption>TABLE I
COMPARATIVE SUMMARY OF RELATED WORK ON AUDITING/ESTIMATING DP IN A BLACK-BOX SETTING</caption><thead><tr><th>Paper</th><th>DP notion</th><th>Impossibility result</th><th>Auditing/estimation algorithm</th></tr></thead><tbody><tr><td>[20]</td><td>DP on typical datasets (DPTD)</td><td>NO</td><td>A probabilistic algorithm that casts the problem of testing the DPTD property as a problem of testing the Lipschitz property.</td></tr><tr><td>[21]</td><td>ε-DP (ε, δ)-DP</td><td>Verifying ε-DP with finite query complexity is impossible</td><td>A probabilistic algorithm that estimates (ε, δ)-DP with a lower bound on the query complexity, that is finite but can be very large.</td></tr><tr><td>[22]</td><td>(ε, δ)-DP</td><td>NO</td><td>A Minimax optimal estimator for (ε, δ)-DP, assuming two fixed neighbouring databases. It provides a relation between the number of samples and the accuracy of the estimation.</td></tr><tr><td>[23], [24]</td><td>DP stochastic gradient descent (DP-SGD) (ε, δ)-DP</td><td>NO</td><td>Two ML approaches based on data poisoning attacks, to identify a lower bound [23] or an upper bound [24] on ε, but without the possibility of specifying any precision.</td></tr><tr><td>[25]</td><td>ε-DP</td><td>NO</td><td>A ML approach that establishes a relationship between differential distinguishability (DD) and DP: given two neighbouring datasets, it approximates the most powerful attack with a ML classifier. No upper bound on the number of samples is given.</td></tr><tr><td>[26]</td><td>ε-DP</td><td>NO</td><td>A Maximum Privacy Loss algorithm that outputs a confidence interval for ε, for two fixed neighbouring databases x<sub>1</sub> and x<sub>2</sub>. The approach relies on the kernel density estimation, assuming Holder continuity of Equation (4) and that the noise is on a closed interval. The approach is statistical (data-driven assessment of the claimed privacy level) and provides an asymptotic approximation of the real ε.</td></tr><tr><td>[27]</td><td>(ε, δ)-DP (ε, δ)-DP limited to a subset of DBs T ((ε, δ, T)-relative DP)</td><td>A poly-time estimator for (ε, δ)-DP is impossible when the input domain is superpolynomial or unbounded</td><td>A ML approach that provides an estimator for (ε, δ, T)-relative DP: given ε and two neighbouring databases in T, the estimator returns the minimum δ by converting the risk of the Bayes/optimal classifier. The general result is instantiated using the kNN algorithm.</td></tr><tr><td>[28]</td><td>RDP</td><td>NO</td><td>Statistical lower bounds for the Rényi divergence in Equation (10) are established through a carefully regularized version of the plug-in estimator (that follows an approximately normal distribution), by assuming two fixed neighbouring databases; this provides an asymptotic approximation of the real ε.</td></tr><tr><td>[29]</td><td>(ε, δ)-DP</td><td>NO</td><td>A ML approach that, given two neighbouring datasets and using a fixed number of samples, trains a classifier to find an attack that invalidates the claimed ε without guarantees.</td></tr><tr><td>[30]</td><td>(ε, δ)-LDP</td><td>NO</td><td>A framework to estimate the empirical privacy loss of different LDP frequency estimation protocols; the investigation focuses on the factors influencing the audit, including the effect of theoretical privacy loss parameters (ε and δ) in low, mid and high privacy regimes, as well as the impact of the domain size.</td></tr><tr><td>[31]</td><td>ε-DP</td><td>NO</td><td>A ML approach for verifying that a given mechanism cannot be ε-DP by establishing differential distinguishability (this yields a lower bound on differential privacy, in the sense that, if a mechanism is ξ-DD, then it cannot be ε-DP, with ε &lt; ξ). The approach is based on training a classifier to predict if an observed output was generated from one of two possible inputs.</td></tr><tr><td>this paper</td><td>ε-DP / LDP RDP / LRDP</td><td>Impossibility of estimating ε with provable guarantees for all 4 notions of DP</td><td>A histogram-based estimator (with guarantees) for LDP and LRDP, when the densities are Lipschitz on a closed interval. We also provide an upper-bound on the number of samples needed to achieve the desired confidence and precision.</td></tr></tbody></table>

second setting, the gap between the number of samples sufficient for achieving the guarantees of the theorem and the theoretical one (used in the proof of the theorem) is even more dramatic than for LDP.

Finally, Section V concludes the paper by drawing possible developments for future work. Proofs are omitted or only sketched in the body of the paper; full details can be found in the appendix, available online.

## A. Contributions and Challenges

To sum up, our work is the first one that considers auditing DP in a black-box framework with provable guarantees and an upper bound on the number of samples needed to achieve them. Our main contributions are:

* We prove that, without any assumption, no black-box algorithm exists for estimating the privacy parameter ε. This impossibility result is strong in the sense that it holds

no matter how low the level of precision and confidence required. Furthermore, it holds for both continuous and discrete domains and noise distributions.

* Instead, if the densities involved are Lipschitz on a closed interval, we provide algorithms with provable guarantees showing the learnability of ε for both LDP and LRDP and for continuous and finite discrete domains, together with an upper bound on the number of samples needed to achieve the desired guarantees. In practice, the number needed will turn out to be much smaller when we consider experiments based on (the truncated variation of) the Laplace and of the Gaussian obfuscation mechanisms.

Technically, the most challenging part has been the second one. The first challenge was to find assumptions under which an estimation with provable guarantees was possible and that were met by the most common mechanisms for DP present in the literature. The second challenge was finding an upper bound on the number of samples that could ensure the specified
level of precision and confidence; as usual, this number comes from the proofs of our theorems, which have been challenging themselves. Finally, the third challenge was to devise a proper strategy to estimate the overall $\epsilon$, starting from the estimation for a fixed pair of values; in doing this, the crucial point was to keep the provable guarantees without considering a huge (sometimes infinite) set of pairs.

## B. Related Work

Many works in the literature face the problem of verifying the DP of an algorithm, e.g., through formal verification. For instance, ShadowDP [45] uses shadow execution to generate proofs of differential privacy with very few programmer annotations and without relying on customized logics and verifiers; CheckDP [46] takes the source code of a mechanism along with its claimed level of privacy and either generates a proof of correctness or a verifiable counterexample. Finding violations of differential privacy has also been addressed by using counterexample generators [47], [48]. The above works assume that the program generating the obfuscation mechanism is known (white-box scenario) and use the code to guide the verification process, with the exception of [48], which adopts a semi-black-box approach, in the sense that it is mostly based on analyzing the input-output of executions but also uses a symbolic execution model to find values of parameters in the code that makes it easier to detect counterexamples.

Verifying purportedly private algorithms in a fully black-box scenario (i.e., when the data obfuscation mechanism is unknown) has only recently been considered. We comparatively summarize the features of such approaches in Table I.

Still concerning black-box estimation, we want to mention [49], [50] that focus on estimating Bayes risk of a black-box mechanism and prove an impossibility result similar to ours. However, as noticed in the second paper (Section VII), DP/LDP provide lower bounds for Bayes leakage (specifically, $\epsilon$-DP induces a bound on the multiplicative Bayes leakage, where the set of secrets are all the possible databases, and LDP implies a lower bound on Bayes leakage, but not vice versa). We want to remark that, being lower bounds, the impossibility proved for Bayes risk does not entail the impossibility results we prove here.

# II. PRELIMINARIES

This section recalls some useful notions from differential privacy and Lipschitz functions.

## A. (Central) $\epsilon$-Differential Privacy

Assume a set of databases $\mathcal{X}$ and an adjacency relation on them (written $\approx$).<fnref n="1" /> A randomized mechanism for a certain query is any probabilistic function $\mathcal{K}: \mathcal{X} \to \mathcal{D}\mathcal{Z}$, where $\mathcal{D}\mathcal{Z}$ represents the set of probability distributions on $\mathcal{Z}$ and $z \sim \mathcal{K}(x)$ is the reported answer. Furthermore, we let $\mathcal{X}$ denote a variable

representing the database on which the randomized mechanism is applied and $Z = \mathcal{K}(X)$.

**Definition II.1 ($\epsilon$-DP [43]):** A randomized mechanism $\mathcal{K}$ is said to be $\epsilon$-differentially private for some $\epsilon \ge 0$ if, for every $S \subset \mathcal{Z}$ measurable and every $x_1 \approx x_2 \in \mathcal{X}$, we have that

$$ \Pr[\mathcal{K}(x_1) \in S] \le e^{\epsilon} \Pr[\mathcal{K}(x_2) \in S] $$

or equivalently if, for every $z \in \mathcal{Z}$, we have that

$$ p_{Z|X}(z|x_1) \le e^{\epsilon} p_{Z|X}(z|x_2) \quad (1) $$

where $p_{Z|X}(\cdot|x_i)$ denotes either the density distribution of $\mathcal{K}(x_i)$ in the continuous case or $[z \mapsto \Pr(\mathcal{K}(x_i) = z)]$ in the discrete one.

The value of $\epsilon$, called the *privacy budget*, controls the level of privacy: a smaller $\epsilon$ ensures a higher level of privacy. This parameter is what we aim to estimate throughout this paper.

## B. Local Differential Privacy

Sometimes, it is more convenient to rely on a distributed variant of $\epsilon$-DP, called *local differential privacy* (LDP). In this setting, users obfuscate their data by themselves before sending them to the provider [9]; therefore, the privacy constraints can be satisfied locally. In this case, instead of working with a set of databases, the set $\mathcal{X}$ represents all possible values for the data of a generic user.

**Definition II.2 (Local differential privacy [51]):** A randomized mechanism $\mathcal{K}: \mathcal{X} \to \mathcal{D}\mathcal{Z}$ is said to be $\epsilon$-locally differentially private for some $\epsilon \ge 0$ if, for every $z \in \mathcal{Z}$ and $x_1, x_2 \in \mathcal{X}$, it holds that

$$ p_{Z|X}(z|x_1) \le e^{\epsilon} p_{Z|X}(z|x_2) \quad (2) $$

where again $p_{Z|X}(\cdot|x_i)$ denotes either the density distribution of $\mathcal{K}(x_i)$ in the continuous case or $[z \mapsto \Pr(\mathcal{K}(x_i) = z)]$ in the discrete one.

Note that LDP implies DP on the collected data. In addition, LDP allows for a higher level of security since the central authority can be considered malicious and men-in-the-middle attacks can be foreseen; indeed, LDP leaves to the users the freedom of choosing their own level of privacy. Anyway, the algorithms in the local setting usually require more data than the algorithms in the central setting for the statistics to be significant [9]. Some practical implementations of LDP are given by Google [4], Apple [2], and Microsoft [52].

## C. Rényi Differential Privacy

The Rényi differential privacy [10] is a relaxation of differential privacy based on the notion of Rényi divergence [53], that we now recall.

**Definition II.3 (Rényi divergence):** For two probability distributions $P, Q$ with densities $p, q$ defined over the same space, the Rényi divergence of order $\alpha > 1$ is defined as

$$ D_{\alpha}(P||Q) = \frac{1}{\alpha - 1} \log \mathbb{E}_{z \sim Q} \left( \frac{p(z)}{q(z)} \right)^{\alpha} $$

**Definition II.4 (($\alpha, \epsilon$)-RDP [10]):** A randomized mechanism $\mathcal{K}$ is said to have $\epsilon$-Rényi differential privacy of order $\alpha > 1$ if,

<footnote n="1">¹The most common adjacency definitions are: (1) $x_1 \approx x_2$ if $x_2$ can be obtained from $x_1$ by adding or removing one single record; (2) $x_1 \approx x_2$ if $x_2$ can be obtained from $x_1$ by modifying one record.</footnote>
for every $x_1, x_2$ adjacent databases for the central setting or values for the local one, we have that

$$D_{\alpha}(\mathcal{K}(x_1) || \mathcal{K}(x_2)) \leq \epsilon. \quad (3)$$

Notice that RDP can be extended by continuity to $\alpha \in \{1, +\infty\}$. In particular, it holds that $\mathcal{K}$ is $(+\infty, \epsilon)$-RDP if and only if it is $\epsilon$-DP (the same holds for the local versions of RDP and DP, respectively).

### D. Truncated Laplace Distribution

One of the main obfuscation mechanisms used to reach L(R)DP is replacing the value to obfuscate by a noisy one sampled from a Laplace distribution centered on the actual value [42].

**Definition II.5:** A Laplace distribution $g_L$ with mean $x$ and scale $B > 0$ is defined by the following density on $\mathbb{R}$:

$$g_L(z|x, B) = \frac{1}{2B} e^{-\frac{|z-x|}{B}}$$

Note that, in the framework of DP, $\mathcal{X}$ (the set of possible values to obfuscate) is usually a closed interval. Under this assumption, a Laplace distribution is $\epsilon$-DP, for $\epsilon = \ln \frac{\Delta\mathcal{X}}{B}$ where $\Delta\mathcal{X}$ is the width of $\mathcal{X}$. Indeed, for all $z, x, x' \in \mathcal{X}$:

$$\frac{g_L(z|x, B)}{g_L(z|x', B)} = \exp \left( \frac{|z - x'| - |z - x|}{B} \right) \leq \exp(\Delta\mathcal{X}/B)$$

The closedness of $\mathcal{X}$ is also required in our approach for estimating DP. Moreover, our estimators will require $\mathcal{Z}$ (the set of possible obfuscated values) to be a closed interval as well. Hence, in our experiments, we will consider $\mathcal{X} = \mathcal{Z}$ and rely on an adapted version of the Laplace mechanism called truncated Laplace distribution [44], which is a distribution defined over $\mathcal{Z} = [a, b]$ obtained by conditioning the result of the Laplace distribution to fall in the interval $[a, b]$:

**Definition II.6:** A truncated Laplace distribution $f$ with mode on $x$, scale $B > 0$, and constrained in the interval $[a, b]$, is defined by the following density on $\mathbb{R}$:

$$f(z|x, B) = K_{x,B} e^{-|z-x|/B}$$

where the normalization constant $K_{x,B}$ is:

$$\begin{aligned} K_{x,B} &= \frac{1}{\int_a^b e^{-|z-x|/B} dz} \\ &= \frac{1}{B(2 - e^{-(x-a)/B} - e^{-(b-x)/B})} \end{aligned}$$

Note that, in the above definition, $f$ and $K_{x,B}$ depend on the chosen interval $[a, b]$. However, to keep the notation light, we will not indicate this dependency in an explicit way. Note also that, in $f(z|x, B)$, the actual value we want to obfuscate, i.e., $x$, is not anymore the mean of the distribution, but it is still its mode. Furthermore, the truncation changes the privacy level: the resulting distribution is still an $\epsilon$-DP mechanism, but $\epsilon'$ is different from the original $\epsilon$ (cf. [54]).

### E. Truncated Gaussian Distribution

Another typical L(R)DP obfuscation mechanism is the Gaussian distribution centered on the actual value [42].

**Definition II.7:** A Gaussian distribution $g_G$ with mean $x$ and standard deviation $\sigma > 0$ is defined by the following density on $\mathbb{R}$:

$$g_G(z|x, \sigma) = \frac{1}{\sigma\sqrt{2\pi}} e^{-\frac{(x-z)^2}{2\sigma^2}}$$

Like in the case of the Laplace distribution, a Gaussian in a closed interval $[a, b]$ is $\epsilon$-DP, where $\epsilon$ is the logarithm of the ratio between $g_G(a|a, \sigma)$ and $g_G(a|b, \sigma)$.

As explained before, for our estimators we need $\mathcal{Z}$ to be a closed interval $[a, b]$. Hence we will use the truncated version of the Gaussian distribution [44], [55], obtained by conditioning the result to be in $[a, b]$:

**Definition II.8:** A truncated Gaussian distribution $f$ with mode $x$, parameter $\sigma > 0$, and constrained in the interval $[a, b]$, is defined by the following density on $\mathbb{R}$:

$$f(z|x, \sigma) = \frac{1}{\int_a^b e^{-\frac{(x-z)^2}{2\sigma^2}} dz} e^{-\frac{(x-z)^2}{2\sigma^2}}$$

Like in the case of the Laplace, a truncated Gaussian is still differentially private, but with a level of privacy different from the original (untruncated) case.

### F. Lipschitz Functions

Here, we recall the definition of a classical property on functions that we will assume for densities later in the paper.

**Definition II.9 (Lipschitz functions):** A function $f: \mathbb{R} \to \mathbb{R}$ is said to be $C$-lipschitz, for some constant $C \ge 0$, if, for every $x, y \in \mathbb{R}$, it satisfies

$$|f(x) - f(y)| \leq C|x - y|$$

Notice that the smaller the constant $C$, the smoother the function $f$, and the less it varies.

To conclude this section, we now state a property of Lipschitz densities over a closed interval that will be useful in proving our main results.

**Lemma 1:** Let $p$ be a $C$-lipschitz density over $\mathcal{Z} = [a, b]$; then, for $W = b - a$ and for all $z \in \mathcal{Z}$, it holds that

$$\frac{1}{W} - \frac{CW}{2} \leq p(z) \leq \frac{1}{W} + \frac{CW}{2}.$$

### III. ON THE ESTIMATION OF $\epsilon$ IN LOCAL DIFFERENTIAL PRIVACY

We start by examining whether it is possible to estimate the value of $\epsilon$ in the setting of LDP with fixed guarantees in a black-box scenario. The estimator can call an auxiliary procedure $S(x)$ (the sampler) that samples in an i.i.d. way from $p_{Z|X}(\cdot|x)$. Furthermore, we wish the estimator to give sufficient guarantees, namely to provide a certain precision (the smaller the better) with a certain confidence (the higher the better).

First, we show that, without making any assumption about the distributions we want to estimate, such an estimator does not exist. Then, we show that, under reasonable assumptions on the mechanism itself, we can design an estimator that can achieve any level of precision with any degree of confidence.
Notice that estimating (2) when $p_{Z|X}(z|x_2) > 0$ is equivalent to verifying $\frac{p_{Z|X}(z|x_1)}{p_{Z|X}(z|x_2)} \le e^\epsilon$. Actually, when both $p_{Z|X}(z|x_1) > 0$ and $p_{Z|X}(z|x_2) > 0$, i.e., whenever $z \in \mathcal{Z}(x_1, x_2)$ where

$$ \mathcal{Z}(x_1, x_2) \stackrel{\text{def}}{=} \{z \in \mathcal{Z} \mid p_{Z|X}(z|x_1) > 0 \wedge p_{Z|X}(z|x_2) > 0\}, $$

we shall concentrate on the estimation of

$$ \log \left( \frac{p_{Z|X}(z|x_1)}{p_{Z|X}(z|x_2)} \right) \le \epsilon. $$

We remark that all logarithms in this paper are natural.

For the negative result, we will show that it is impossible to estimate $\epsilon$ even for a fixed pair of values $x_1$ and $x_2$. Namely, we will consider the quantity

$$ \epsilon^*(x_1, x_2) \stackrel{\text{def}}{=} \sup_{z \in \mathcal{Z}(x_1, x_2)} \log \left( \frac{p_{Z|X}(z|x_1)}{p_{Z|X}(z|x_2)} \right). \quad (4) $$

For the positive result, of course, we will need to range on all pairs, i.e., our final aim is to estimate

$$ \epsilon^*(p_{Z|X}) \stackrel{\text{def}}{=} \sup_{x_1, x_2 \in \mathcal{X}} \epsilon^*(x_1, x_2). \quad (5) $$

### A. Impossibility Result

We now prove that (4) has no estimator with guarantees; a fortiori, this, proves that no estimator for (5) exists. We remark that this impossibility result is very strong: it shows that no estimator exists, even if (1) we are not very demanding about the precision and the confidence (namely, even if $\gamma$ is large and $\delta$ is small), (2) even if the number of samples is unbounded, and (3) the estimator is adaptive (namely, it can decide on the fly whether to stop or to continue sampling based on previous samples).

**Theorem 1 (Impossibility):** For every $\gamma > 0$ (precision), $0 < \delta < 1$ (confidence), $x_1, x_2 \in \mathcal{X}$, and probabilistic estimator algorithm $\tilde{\epsilon}$ that almost surely terminates, there exists a probability distribution $p_{Z|X}$ such that

$$ \Pr \left( |\epsilon^*(x_1, x_2) - \tilde{\epsilon}(x_1, x_2, \gamma, \delta)| > \gamma \right) > 1 - \delta. $$

*Proof idea:* No estimator can exist in the general case because $p_{Z|X}$ has no regularity constraint, and the points $z$ for which $\epsilon^*$ is reached can have a low probability of being sampled. Even though the estimator has access to the full range of values $\mathcal{Z}$, since it does not know the probability of each output, it cannot adapt (even on the fly) the number of calls to $\mathcal{S}$ to sample at least once each $z \in \mathcal{Z}$. See the appendix, available online for full details.

**Remark 1:** The proof of Theorem 1 assumes a binary setting both for $\mathcal{X}$ and $\mathcal{Z}$: an impossibility result in this setting clearly implies impossibility in more general ones, e.g., for continuous noise functions. Moreover, we do not use any property of $x_1$ and $x_2$. In particular, $x_1$ and $x_2$ can be the results of a query applied to two adjacent datasets, i.e., we can have $x_1 = \mathcal{K}(y_1)$ and $x_2 = \mathcal{K}(y_2)$ where $y_1 \approx y_2$ (cf. Definition II.1). Hence the result also holds for the estimation of $\epsilon$ in central DP. In contrast, our impossibility result does not hold for $(\epsilon, \delta)$-DP. Indeed, [21] and other papers listed in Table I show that approximate DP

can be estimated, with the desired level of precision, for any distribution. As remarked in the proof sketch given above, this is because the main difficulty in checking the pure DP property lies in those cases in which the probabilities involved in the DP inequality are very small. By contrast, in $(\epsilon, \delta)$-DP, the $\delta$ “covers” the very rare events corresponding to these unlikely outputs (or unlikely inputs), so they can be ignored in the estimation of $\epsilon$.

### B. Estimating $\epsilon^*(x_1, x_2)$

Let us now impose a few reasonable assumptions on the underlying probability distribution, namely that $p_{Z|X}$ is defined over a closed interval $\mathcal{Z} \stackrel{\text{def}}{=} [a, b]$, and that both $p_{Z|X}(\cdot|x_1)$ and $p_{Z|X}(\cdot|x_2)$ are C-Lipschitz, with $C < 2/W^2$ and $W = b - a$ (this condition on $C$ is needed to let $\tau$, as defined in (6), be positive). Once chosen the precision and confidence parameters, we will prove that $n$ samples from the two distributions (for a suitable value of $n$ that depends on $W, \gamma, \delta$ and $C$ – see (7) later on) are enough for estimating (4) with guarantees.

We propose a histogram-based estimator whose pseudocode is provided in Algorithm 1. For the desired precision $\gamma$, the estimator first divides $\mathcal{Z}$ into $m$ sub-intervals, each of width $w \stackrel{\text{def}}{=} W/m$, where

$$ m \stackrel{\text{def}}{=} \left\lfloor \frac{6CW}{\tau\gamma} \right\rfloor \quad \text{and} \quad \tau \stackrel{\text{def}}{=} \frac{1}{W} - \frac{CW}{2}. \quad (6) $$

In particular, we set $z_0 = a$ and $z_{j+1} = z_j + w$; one can readily check that $z_m = b$. Then, the estimator chooses $n$ such that

$$ 2m(1 - w\tau)^n + 4f(n, w\tau, \gamma/12) \le 1 - \delta, \quad (7) $$

where $f$ is defined as

$$ f(x, y, z) \stackrel{\text{def}}{=} \frac{\exp\left(\frac{-xy(e^z - 1)^2}{1+e^z}\right) + \exp\left(\frac{-xy(1-e^{-z})^2}{2}\right)}{1 - (1 - y)^x} \quad (8) $$

(note that $f$ is exponentially decreasing in $x$ and $y$). The estimator then invokes the sampler $n$ times both for $x_1$ and for $x_2$ (lines 4-7), counts the number of samples that appear in each sub-interval (lines 8-14), and considers these numbers as the approximations of $p_{Z|X}(\cdot|x_1)$ and $p_{Z|X}(\cdot|x_2)$ in that sub-interval; so, it computes their ratio and returns the highest value. Notice that the number of samples needed here is $2n$.

We are now able to state our theorem.

**Theorem 2 (Correctness):** Let densities $p = p_{Z|X}(\cdot|x_1)$ and $q = p_{Z|X}(\cdot|x_2)$ over $\mathcal{Z} = [a, b]$ be C-Lipschitz, with $C < 2/W^2$ and $W = b - a$. For every $\gamma > 0$ (precision) and $0 < \delta < 1$ (confidence), we have that

$$ \Pr \left( \text{Algorithm 1 succeeds and} \\ \quad \left| \epsilon^*(x_1, x_2) - \tilde{\epsilon}(x_1, x_2, \mathcal{Z}, \gamma, \delta, C) \right| \le \gamma \right) \ge \delta. $$

*Proof sketch:* First, we know that, since $p$ is smooth, we can set the number of sub-intervals $m$ to reduce $w$ (the width of the sub-intervals) and have the probability $p_j$ of sampling within the sub-interval $j$ to be close to any $wp(z)$, with $z \in [z_j, z_{j+1})$ (see Fig. 2(a) for an intuition). Being this true also for $q$, we get
<caption>**Algorithm 1:** Histogram-Based Estimator for $\epsilon^*(x_1, x_2)$:</caption>

1: **Input:** $\mathcal{Z}([a, b]), \gamma, \delta, C$
2: **Output:** $\tilde{\epsilon}(x_1, x_2, \mathcal{Z}, \gamma, \delta, C)$
3: ▷ differing from
$\epsilon^*(x_1, x_2)$ for $\le \gamma$ with prob. $\ge \delta$
4: Compute $m$ and $n$ as in (6) and (7), resp.
5: **for** $1 \le i \le n$ **do**
6: &nbsp;&nbsp;&nbsp;&nbsp;$s_1[i] \leftarrow S(x_1)$
7: &nbsp;&nbsp;&nbsp;&nbsp;$s_2[i] \leftarrow S(x_2)$
8: **end for**
9: **for** $1 \le j \le m$ **do**
10: &nbsp;&nbsp;&nbsp;&nbsp;$N_j \leftarrow \sum_i 1(z_j \le s_1[i] < z_{j+1})$
11: &nbsp;&nbsp;&nbsp;&nbsp;$M_j \leftarrow \sum_i 1(z_j \le s_2[i] < z_{j+1})$
12: &nbsp;&nbsp;&nbsp;&nbsp;**if** $N_j = 0$ or $M_j = 0$ **then**
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end if**
14: **end for**
15: **return** $\max_j \log(\frac{N_j}{M_j})$

that $\log(\frac{p_j}{q_j})$ is close to $\log(\frac{p(z)}{q(z)})$. In particular, this is true for some $z^*$ for which $\epsilon^*$ is reached.

Second, we consider the case where the binomial variables $N_j$ and $M_j$ are close to their average $np_j$ and $nq_j$. This happens with good probability and ensures that $\log(\frac{N_j}{M_j})$ is close to $\log(\frac{p_j}{q_j})$ and it is true thanks to the following Lemma:

**Lemma 2:** Let $X_1, \dots, X_n$ be i.i.d. Bernoulli random variables with parameter $p > 0$, and $S_n$ denote their sum (hence $\mathbb{E}(S_n) = np$). Then, for every $\gamma > 0$,

$$ \Pr(|\log S_n - \log np| > \gamma | S_n > 0) \le f(n, p, \gamma) $$

where $f$ is defined in (8).

Third, we have that the answer $\log(\frac{N_J}{M_J})$ of the estimator is actually close to $\log(\frac{p_j^*}{q_j^*})$, where $j^*$ is the sub-interval containing $z^*$, that is the value that $\epsilon^*$ originates from (recall that, by definition of $\epsilon$-LDP, $\epsilon^* = \sup_{z \in \mathcal{Z}} \log(p(z)/q(z)))$. Otherwise, if $\log(\frac{N_J}{M_J})$ was much larger, we would have a contradiction with the definition of $\epsilon^*$; similarly, if it was much smaller, it would imply $\log(\frac{N_J}{M_J}) < \log(\frac{N_{j^*}}{M_{j^*}})$ and mean that the estimator had not returned the maximum value.

Finally, $\log(\frac{N_J}{M_J})$ is close to $\log(\frac{p_j^*}{q_j^*})$ which is close to $\log(\frac{p(z^*)}{q(z^*)}) = \epsilon^*$; so the estimator works. See Fig. 2(b) for an illustration of this conclusion.

To conclude, notice that, if $t$ denotes the time complexity of the sampler, the cost of sampling is $O(nt)$, whereas the complexity of calculating each $N_j$ and $M_j$ is $O(n)$; therefore, the total complexity of Algorithm 1 is $O(n(t+m))$.

**Remark 2:** Our method is based on a discretization of the noise function. Obviously, it can be trivially adapted to the case in which the function is discrete with a finite domain provided a lower bound on the probability distribution. For instance, this is the case of the well-known $k$-RR mechanism [56] (randomized response on a domain of $k$ elements).

<figure><img src="image_3.png" /><figcaption>Fig. 2. Proof sketch Theorem 2: (a) The smoothness of $p$ implies that $wp(z)$ is close to $p_j$. (b) Summary of the second and third steps of the proof, illustrating why the answer is close to $\epsilon^*(x_1, x_2)$. The smallest intervals are bounded thanks to the smoothness of the distributions and the largest ones by the bound of Lemma 2, implying that the empirical average tends to the expected value.</figcaption></figure>

### C. On the C-Lipschitzness Assumptions

Our estimator guarantees the bounds on the estimated $\epsilon$ only if the distributions are smooth; this is similar, e.g., to [27]. However, a provider could lie both about $\epsilon$ and about the smoothness of the distributions: it can trick the estimator into answering $\epsilon$ although the system does not actually provide such a level of privacy. Therefore, we have 2 cases to consider:

**Case 1:** The estimator is in contradiction with the claims of the provider. Here, we can conclude that the provider should not be trusted because it lied about $\epsilon$ or the smoothness.

**Case 2:** The estimator agrees on the $\epsilon$ claimed by the provider. Then either the provider did not lie at all, or it lied about the smoothness of the distributions and tricked the estimator.

Unfortunately, checking the Lipschitzness of a given function is well-known to be a hard task [57]. So, to improve the unsatisfactory conclusion drawn in the second case, we can implement a safety check derived from the following theorem:

**Theorem 3 (Necessary condition for Lipschitzness):** Assuming that the distributions are $C$-Lipschitz, then, for any $c > 0$, the event

$$ \forall j. \left[ \frac{1}{n} |N_j - N_{j+1}| \le 2c + Cw^2 \right] \text{ and} $$
$$ \frac{1}{n} |M_j - M_{j+1}| \le 2c + Cw^2 \quad (9) $$

happens with probability at least $1 - 8me^{-nc^2/3}$.

In practice, one can make multiple executions of Algorithm 1, check if (9) occurs for each of them, and compute the empirical probability of this event (proportion of executions for which the event occurred). If the empirical probability of (9) is significantly lower than the theoretical lower bound from Theorem 3, then it is likely (depending on the number of executions) that the distributions are not C-Lipschitz; so, the provider lied.

### D. Estimating $\epsilon^*(p_{Z|X})$

As already said, Algorithm 1 estimates $\epsilon^*(x_1, x_2)$, for a given pair $x_1, x_2$. However, we can ask it to return the maximum between $\max_j \log(\frac{N_j}{M_j})$ and $-\min_j \log(\frac{M_j}{N_j}) = \max_j \log(\frac{M_j}{N_j})$, thus avoiding switching p and q and call the estimator again.

To estimate the overall value of $\epsilon$ (i.e., if we aim at estimating (5)), we have different possibilities. One solution is when $\mathcal{X}$ is finite: we can call the estimator for all 2-subsets $\{x_1, x_2\}$, resulting in $O(|\mathcal{X}|^2)$ calls; this is what is advocated, e.g., in [22]. However, if $\mathcal{X}$ is big, the cost grows dramatically. Alternatively, we can follow [26] and choose a subset of all possible pairs; this gives a statistical lower bound of the overall $\epsilon$. We can also follow [27], where the authors focus on a relative notion of DP, i.e., DP restricted to a subset of $\mathcal{X}$; in this way, we estimate the DP parameter on this subset by running our estimator on all the pairs of this subset (that, indeed, is usually quite small). However, the latter two approaches reduce the computational cost at the price of losing guarantees on the estimation.

We now propose an alternative method that works well even when $\mathcal{X}$ is infinite or very big; the price is another mild assumption on the densities involved. Up to now, we have assumed that, for every $x \in \mathcal{X}$, $p_{Z|X}(\cdot|x)$ is C-Lipschitz, for $C < 2/W^2$ and $W$ is the width of $\mathcal{Z} = [a, b]$. Let us now also assume that, for every $z \in \mathcal{Z}$, $p_{Z|X}(z|\cdot)$ is D-Lipschitz, for some $D$; this new assumption is quite mild since we are not posing any constraint on $D$, and so any doubly differentiable function satisfies this requirement (since $\mathcal{X}$ is a closed interval). Then, the new algorithm that we propose first discretizes the interval $\mathcal{X} = [c, d]$ in $k$ buckets (for a proper value of $k$), then takes $x_i$ to be the mid-point of bucket $i$, runs Algorithm 1 for all possible $\{x_i, x_j\}$ and returns the maximum between all the estimated values, by ignoring the failed computations of $\tilde{\epsilon}_{ij}$ when calculating the returned value. The details are given in Algorithm 2: it requires $k(k-1)n$ samples and its overall time complexity is $O(k^2n(t+m))$. Its correctness is provided by the following result, where we say that the algorithm succeeds if at least one invocation of Algorithm 1 succeeds.

**Theorem 4:** Let $\mathcal{Z} = [a, b]$, $\mathcal{X} = [c, d]$, and $p_{Z|X}$ be such that, for every $x \in \mathcal{X}$, $p_{Z|X}(\cdot|x)$ is C-Lipschitz, for $C < 2/W^2$ and $W = b-a$, and that, for every $z \in \mathcal{Z}$, $p_{Z|X}(z|\cdot)$ is D-Lipschitz, for some $D$. For every $\gamma > 0$ (precision) and $0 < \delta < 1$ (confidence), we have that

$$ \Pr \left( \text{Algorithm 2 succeeds and} \\ \quad |\epsilon^*(p_{Z|X}) - \tilde{\epsilon}(\mathcal{Z}, \mathcal{X}, \gamma, \delta, C, D)| \le \gamma \right) \ge \delta. $$

<table><caption>TABLE II
THE LIPSCHITZ CONSTANTS ($D$ AND $C$) FOR TRUNCATED LAPLACE AND TRUNCATED GAUSSIAN MECHANISMS, VARYING ACCORDING TO THE VALUE OF THEIR DEFINING PARAMETER (VIZ., $B$ AND $\sigma$, RESP.)</caption><thead><tr><th colspan="5">Truncated Laplace</th></tr><tr><th>B</th><th>D</th><th>C</th><th>ε</th><th>C &lt; 2/W<sup>2</sup></th></tr></thead><tbody><tr><td>0.5</td><td>9.25</td><td>4.63</td><td>2.00</td><td>✗</td></tr><tr><td>0.8</td><td>4.38</td><td>2.19</td><td>1.25</td><td>✗</td></tr><tr><td>1</td><td>3.16</td><td>1.58</td><td>1.00</td><td>✓</td></tr><tr><td>2</td><td>1.27</td><td>0.64</td><td>0.50</td><td>✓</td></tr><tr><td>5</td><td>0.44</td><td>0.22</td><td>0.20</td><td>✓</td></tr></tbody></table>

<table><thead><tr><th colspan="5">Truncated Gaussian</th></tr><tr><th>σ</th><th>D</th><th>C</th><th>ε</th><th>C &lt; 2/W<sup>2</sup></th></tr></thead><tbody><tr><td>0.3</td><td>7.06</td><td>5.40</td><td>5.56</td><td>✗</td></tr><tr><td>0.5</td><td>2.42</td><td>2.03</td><td>2.00</td><td>✗</td></tr><tr><td>0.6</td><td>1.62</td><td>1.49</td><td>1.39</td><td>✓</td></tr><tr><td>1</td><td>0.54</td><td>0.70</td><td>0.50</td><td>✓</td></tr><tr><td>2</td><td>0.13</td><td>0.23</td><td>0.13</td><td>✓</td></tr></tbody></table>

We also display the resulting level of privacy $\epsilon$ and A check mark indicating if the guarantees of our theorems hold for the displayed values or not (Recall that $\mathcal{X} \equiv \mathcal{Z} = [0, 1]$ and so $W=1$).

### Algorithm 2: Estimator for $\epsilon^*(p_{Z|X})$.

1: **Input:** $\mathcal{Z} = [a, b])$, $\mathcal{X} = [c, d])$, $\gamma$, $\delta$, $C$, $D$

2: **Output:** $\tilde{\epsilon}(\mathcal{Z}, \mathcal{X}, \gamma, \delta, C, D)$

3: Let $k \ge \frac{3D(d-c)}{\tau\gamma}$, where $\tau$ is defined in (6)

4: Divide $\mathcal{X}$ in $k$ buckets, with $x_i$ the mid-point of bucket $i$

5: **for all** $\{x_i, x_j\} \subseteq \{1, \dots, k\}$ **do**

6: $\tilde{\epsilon}_{ij} \leftarrow \tilde{\epsilon}(x_i, x_j, \mathcal{Z}, \frac{\gamma}{3}, \sqrt{\delta}, C)$, by invoking Algorithm 1

7: **end for**

8: **return** $\max_{ij} \tilde{\epsilon}_{ij}$

## E. Experiments

We now test the validity of our approach by using the truncated Laplace and Gaussian mechanisms defined in Section II-D and II-E, respectively. For our experiments we set $\mathcal{X} = \mathcal{Z} = [0, 1]$, so $W=1$, and we choose $\gamma$ to be $\frac{1}{4}$ of the value of $\epsilon$. If the provider claims a value for $\epsilon$ (as it is generally the case), we can use such a value for defining $\gamma$. Moreover, since the estimation (viz., $\tilde{\epsilon}$) generally decreases as the number of samples increases, we can dynamically re-adjust $\gamma$ (which determines the value of $n$), if we observe that the estimation falls below four times the value of $\gamma$.

**On the Lipschitzness assumptions:** We start by showing that the Lipschitzness requirements (that are needed for our theorems to hold) are met by our two mechanisms. Such functions are continuous with respect to $x$ or $z$ on closed intervals; so, they are Lipschitz, and in Table II we show the constants $D$ and $C$ that they exhibit for various values of their defining parameter (viz., $B$ and $\sigma$). Furthermore, we also provide the resulting $\epsilon$, and we see in which cases the condition $C < \frac{2}{W^2}$ holds.
<figure><img src="image_4.png" /><figcaption>Fig. 3. Logarithm of the number of samples required to run Algorithm 1 as functions of $\delta$, $\gamma$ and $C$ for LDP with $W = 1$; when not varying, we set $C = 1$, $\delta = 0.9$ and $\gamma = 0.1$.</figcaption></figure>

<table><caption>TABLE III
$\tilde{\epsilon}(x_i, x_j)$ FOR SOME PAIRS AMONG THE $\frac{k(k-1)}{2}$ COMPUTED BY ALGORITHM 2
WITH $\delta = 0.9$ AND $\gamma = 0.25$ FOR A TRUNCATED LAPLACE OF PARAMETER $B = 1$</caption><thead><tr><th>x<sub>i</sub></th><th>x<sub>j</sub></th><th>&epsilon;&#770;(x<sub>i</sub>, x<sub>j</sub>)</th><th>x<sub>i</sub></th><th>x<sub>j</sub></th><th>&epsilon;&#770;(x<sub>i</sub>, x<sub>j</sub>)</th></tr></thead><tbody><tr><td>0.00</td><td>1.00</td><td><b>1.00</b></td><td>0.54</td><td>0.44</td><td>0.12</td></tr><tr><td>0.06</td><td>0.49</td><td>0.62</td><td>0.60</td><td>0.94</td><td>0.52</td></tr><tr><td>0.11</td><td>0.99</td><td>0.96</td><td>0.67</td><td>0.43</td><td>0.26</td></tr><tr><td>0.18</td><td>0.48</td><td>0.40</td><td>0.72</td><td>0.93</td><td>0.34</td></tr><tr><td>0.23</td><td>0.98</td><td>0.89</td><td>0.79</td><td>0.42</td><td>0.45</td></tr><tr><td>0.30</td><td>0.47</td><td>0.21</td><td>0.84</td><td>0.92</td><td>0.14</td></tr><tr><td>0.36</td><td>0.97</td><td>0.80</td><td>0.91</td><td>0.41</td><td>0.65</td></tr><tr><td>0.42</td><td>0.46</td><td>0.06</td><td>0.97</td><td>0.91</td><td>0.10</td></tr><tr><td>0.48</td><td>0.96</td><td>0.66</td><td>1.00</td><td>0.00</td><td><b>1.00</b></td></tr></tbody></table>

The bold values are those returned by Algorithm 2 (the maximum among all the values calculated).

**Number of samples:** To massively sample from a truncated Laplace distribution, we follow the well-known inverse transform sampling method. Details about the computation of the inverse CDF are provided in Appendix A, available online. For truncated Gaussian we used SciPy's `truncnorm` [58].

As for the number of samples required for the estimation, in Fig. 3, we depict the logarithm of the $n$ in Algorithm 1 as functions of $\gamma$, $\delta$ and $C$. The analysis points out that $n$ strongly depends on $\gamma$ (in particular, the figure shows an inverse proportionality between $n$ and $\gamma$), while the dependency on $\delta$ and $C$ is very mild. Since the time complexity of the estimator mostly depends on the number of samples (indeed, we always have that $m \ll n$), $\gamma$ is the parameter that most deeply influences the overall time complexity.

**Analysis of Algorithm 2.** In the following experiment, we focus on the Laplace with $B = 1$ and we set $\gamma = 0.25$ and $\delta = 0.8$. The latter implies that $D \approx 3.16$, $C \approx 1.58$, and $\epsilon = 1$; so, we set $n$ and $k$ (as defined in Algorithms 1 and 2) to 1863132 and 91, respectively. In Table III we display $\tilde{\epsilon}(x_i, x_j)$ for some pairs $x_i$ and $x_j$ among the $\frac{k(k-1)}{2} (= 4095)$ computed during an execution of Algorithm 2. The maximum $\tilde{\epsilon}(x_i, x_j)$ is 1, so the algorithm correctly returns 1. Notice that this value is reached only for $\{x_1, x_2\} = \{0, 1\}$ (the extremes of $\mathcal{X}$). This result is not surprising since the Laplace density (as well as the Gaussian one) is unimodal, first increasing then decreasing; so, $\epsilon$ is reached when the modes are placed as far away from each other as possible. For this reason, we will focus our next experiments

<figure><img src="image_5.png" /><figcaption>Fig. 4. Analysis on $n$ across 100 executions of Algorithm 1 with $\delta = 0.95$ and $\gamma \approx \epsilon/4$; for Laplace we use $B = 1$ (so, $\epsilon = 1$ and $\gamma = 0.2$) and for Gaussian we use $\sigma = 0.6$ (so, $\epsilon = 1.39$ and $\gamma = 0.4$).</figcaption></figure>

on the pair of extremes $\{0, 1\}$, as any other pair would lead to an underestimation of $\epsilon$.

**Analysis of Algorithm 1:** Let us fix the confidence $\delta$ to 0.95 and the precision $\gamma$ to $\epsilon/4$ (as discussed before). In Fig. 4 we plot the outputs returned by Algorithm 1 with different values of $n$ for a truncated Laplace of parameter $B = 1$ and for a truncated Gaussian of parameter $\sigma = 0.6$ (there, the real value of $\epsilon$ is shown with the red dashed line, whilst the precision region is in yellow). Notably, the *theoretical* $n$ (i.e., the one from Theorem 2) is in the order of $10^9$ and $10^8$, respectively. However, the estimated $\tilde{\epsilon}$ across 100 executions of Algorithm 1 reaches a good precision and confidence in much less iterations (in the order of $10^5$); this is what we call the *practical* number of samples, that is several magnitude orders lower than the theoretical one.

This discrepancy is made more apparent in Table IV, where we show the theoretical vs practical $n$, and the $m$ used under the practical one. That Table also shows that, even if the assumptions of Theorem 2 are not met, the estimator still works (see the Nan-rows therein). However, one drawback when using the estimator without the theoretical bound is that the user has to set both $m$ and $n$, and needs to balance between them.

The fact that the desired precision is reached much sooner than the theoretical bound is not surprising: Theorem 2 makes no assumption on the distributions, apart from Lipschitzness,
<table><caption>TABLE IV
NUMBERS OF SAMPLES NEEDED BY ALGORITHM 1 ON DIFFERENT MECHANISMS (TRUNCATED LAPLACE OR GAUSSIAN) WITH $\delta = 0.95$</caption><thead><tr><th>Mechanism</th><th>Scale<br>(B/σ)</th><th>ε</th><th>γ</th><th>n<sub>TH</sub></th><th>n<sub>PR</sub></th><th>m</th></tr></thead><tbody><tr><td>Laplace</td><td>.5</td><td>2</td><td>.5</td><td>NaN</td><td>3e+04</td><td>200</td></tr><tr><td>Laplace</td><td>.8</td><td>1.25</td><td>.3</td><td>NaN</td><td>7e+04</td><td>334</td></tr><tr><td>Laplace</td><td>1</td><td>1</td><td>.2</td><td>1e+09</td><td>5e+05</td><td>678</td></tr><tr><td>Laplace</td><td>2</td><td>.5</td><td>.1</td><td>4e+08</td><td>3e+05</td><td>170</td></tr><tr><td>Laplace</td><td>5</td><td>.2</td><td>.05</td><td>6e+08</td><td>5e+05</td><td>89</td></tr><tr><td>Gaussian</td><td>.3</td><td>5.56</td><td>1.4</td><td>NaN</td><td>7e+04</td><td>72</td></tr><tr><td>Gaussian</td><td>.5</td><td>2</td><td>.5</td><td>NaN</td><td>7e+04</td><td>200</td></tr><tr><td>Gaussian</td><td>.6</td><td>1.39</td><td>.3</td><td>2e+08</td><td>1e+05</td><td>351</td></tr><tr><td>Gaussian</td><td>1</td><td>.5</td><td>.1</td><td>4e+08</td><td>5e+05</td><td>194</td></tr><tr><td>Gaussian</td><td>2</td><td>.13</td><td>.05</td><td>6e+08</td><td>5e+05</td><td>94</td></tr></tbody></table>

We repeat here the values of $\epsilon$ (from table ii) and use $\gamma \approx \epsilon/4$. We then provide: the theoretical $n(n_{th})$, the practical one ($n_{pr}$), and the number of sub-intervals ($m$). When $C$ is too large (see again table ii), $n_{th}$ is undefined and so is the number of sub-intervals, that has to be set by hand in practice (we used $m = [100/\gamma]$).

and so the bound on the probability of success is far from being tight for the distributions considered in practice.

**The safety check:** We now aim to verify whether the safety check (w.r.t. $(x_1, x_2)$) in Theorem 3 works in practice when the provider lies about the smoothness of the distribution. In particular, we focus on the Laplace mechanism and suppose that the provider can lie about the C-Lipschitz parameter.

As in the section before, we start by fixing precision and confidence (we put $\gamma = 2$ and $\delta = 0.8$ for efficiency issues, since we do not need to be very precise in the estimation of $\epsilon$ for this experiment), and we set the $c$ of Theorem 3 to $(Cw^2)/2$. Moreover, we choose some required probability (say 0.9) and, if needed, we increase $n$ so that the theoretical lower bound $1 - 8me^{-nc^2/3}$ on the probability of the safety check to be met is greater than our required probability. Then, we perform 1000 execution of Algorithm 1 by considering first the $C$ claimed by the provider (i.e., $C = 1$) and then the actual $C$ (i.e., the true one). Therefore, we look at the proportion of executions that do not trigger the safety check. This empirically approximates the probability of the safety check being met in Theorem 3. The results are shown in Fig. 5, where we can see that, if the actual $C$ is close to the claimed one (viz., when the curve is between 1.5 and 2), the safety check does not allow us to detect the lie from the provider. This is because, once again, Theorem 3 does not assume the particular kind of distributions used, so its bound cannot be tight for truncated Laplace distributions.

## IV. ON THE ESTIMATION OF $\epsilon$ IN LOCAL RÉNYI DIFFERENTIAL PRIVACY (LRDP)

We now adapt all previous results to LRDP. As before, we first concentrate on a fixed pair $x_1, x_2 \in \mathcal{X}$ to estimate

$$ \epsilon_{\alpha}^{*}(x_1, x_2) \stackrel{\text{def}}{=} D_{\alpha} \left( p_{Z|X}(\cdot|x_1) \middle\| p_{Z|X}(\cdot|x_2) \right). \quad (10) $$

Again, without reasonable assumptions, it is impossible to estimate (10) with guarantees. On the other hand, this quantity

<figure><img src="image_6.png" /><figcaption>Fig. 5. Experiments on the safety check.</figcaption></figure>

can be estimated by having the same assumptions as for LDP. Then, these results will transfer to the estimation of

$$ \epsilon_{\alpha}^{*}(p_{Z|X}) \stackrel{\text{def}}{=} \sup_{x_1, x_2 \in \mathcal{X}} \epsilon_{\alpha}^{*}(x_1, x_2). \quad (11) $$

### A. Impossibility Result

The impossibility result in Section III-A also holds for LRDP. This is more surprising than the analogous one for LDP: indeed, if there is again some output where the probabilities differ significantly, but the probability of this output is low, then one would think that this would not violate the RDP guarantee since Rényi divergence averages over all outputs, instead of taking the pointwise maximum. However, as the following theorem proves, this is not the case.

**Theorem 5 (Impossibility):** For every $\alpha > 1$ (LRDP order), $\gamma > 0$ (precision), $0 < \delta < 1$ (confidence), $x_1, x_2 \in \mathcal{X}$, and probabilistic estimator $\tilde{\epsilon}_{\alpha}$ that almost surely terminates, there exists a probability distribution $p_{Z|X}$ such that

$$ \Pr \left( |\epsilon_{\alpha}^{*}(x_1, x_2) - \tilde{\epsilon}_{\alpha}(x_1, x_2, \gamma, \delta)| > \gamma \right) > 1 - \delta. $$

**Proof Sketch:** Let us set the distributions

$$ p_{Z|X}(\cdot|x_1) = \mathcal{B}(d^{\frac{1}{\alpha}}) \quad \text{and} \quad p_{Z|X}(\cdot|x_2) = \mathcal{B}\left(\frac{d^{\frac{1}{\alpha-1}}}{h}\right) $$

where $\mathcal{B}(p)$ denotes a Bernoulli distribution with parameter $p$, and we can consider the case when $\tilde{\epsilon}$ samples only 0s. In that case, the behaviour of $\tilde{\epsilon}$ is independent of $d^{\frac{1}{\alpha}}$ and $\frac{d^{\frac{1}{\alpha-1}}}{h}$ since its a priori distributions for $p_{Z|X}(\cdot|x_1)$ and $p_{Z|X}(\cdot|x_2)$ are $\mathcal{B}(0)$. Therefore, we can freely set $d$ so that the probability for $\tilde{\epsilon}$ of sampling only 0s is high enough and $h$ is sufficiently large so that $\epsilon^* \ge \log(h)$ is far enough from the answers of $\tilde{\epsilon}$. See Fig. 6 for an illustration of such Bernoulli distributions and the appendix, available online for full details. ■

We remark that also for RDP, the previous result (stated for the local setting) holds for the central setting as well, where $x_1$ and $x_2$ are the result of a query applied to two adjacent databases (cf. Remark 1).
<figure><img src="image_7.png" /><figcaption>Fig. 6. Illustration of the two Bernoulli distributions in the proof of Theorem 5.</figcaption></figure>

### B. Estimating $\epsilon_{\alpha}^{*}(x_1, x_2)$

For estimating LRDP, we follow the same setting as the one followed for LDP. So, we still assume the distributions to be C-Lipschitz over $\mathcal{Z} \stackrel{\text{def}}{=} [a, b]$, with $a, b \in \mathbb{R}$, $C < 2/W^2$ and $W = b - a$.

The new estimator, that we call Algorithm 3, can be adapted from Algorithm 1 by changing the values of $m$ and $n$, and the returned value. In particular, let us define

$$ \tau_0 \stackrel{\text{def}}{=} \frac{1}{W} - \frac{CW}{2} \quad \text{and} \quad \tau_1 \stackrel{\text{def}}{=} \frac{1}{W} + \frac{CW}{2}, \qquad (12) $$

$$ K \stackrel{\text{def}}{=} \frac{2\tau_1^{\alpha}}{\tau_0^{\alpha-1}} \quad \text{and} \quad K' \stackrel{\text{def}}{=} \frac{\tau_0^{\alpha}}{\tau_1^{\alpha-1}}, \qquad (13) $$

$$ \gamma' = \min \left( \frac{\gamma K'(\alpha - 1)}{2K(2\alpha - 1)}, \frac{\log 2}{2\alpha - 1} \right). \qquad (14) $$

The new algorithm will divide $\mathcal{Z}$ in $m$ sub-intervals s.t.

$$ \frac{CwK(2\alpha - 1)}{2\tau_0 K'(\alpha - 1)} \leq \gamma/2, \qquad (15) $$

where $w = W/m$. Let $n$ be such that

$$ 1 - 2m(1 - w\tau_0)^n - 2mf(n, w\tau_0, \gamma') \geq \delta \qquad (16) $$

where $f$ is defined in (8). Finally, the returned value is

$$ \frac{1}{\alpha - 1} \log \sum_j \left( \frac{N_j}{M_j} \right)^{\alpha} \frac{1}{n} M_j. \qquad (17) $$

**Theorem 6 (Correctness):** Let densities $p = p_{Z|X}(\cdot|x_1)$ and $q = p_{Z|X}(\cdot|x_2)$ over $\mathcal{Z} = [a, b]$ be C-Lipschitz, with $C < 2/W^2$ and $W = b - a$. For every $\alpha > 1$ (LRDP order), $\gamma > 0$ (precision), and $0 < \delta < 1$ (confidence), it holds that

$$ \Pr \left( \text{Algorithm 3 succeeds and} \\ \left| \epsilon_{\alpha}^{*}(x_1, x_2) - \tilde{\epsilon}_{\alpha}(x_1, x_2, \mathcal{Z}, \gamma, \delta, C) \right| \leq \gamma \right) \geq \delta. $$

### C. Estimating $\epsilon_{\alpha}^{*}(p_{Z|X})$

We now focus on estimating (11). To this aim, we follow the approach in Section III-D: We assume D-Lipschitzness of all $p_{Z|X}(z|\cdot)$, divide $\mathcal{X}$ in a proper number of buckets, run Algorithm 3 for every pair of buckets’ mid-points, and return the maximum returned value. The new algorithm, which we call

<figure><img src="image_8.png" /><figcaption>Fig. 7. Logarithm of the number of samples for Algorithm 3 as functions of $\alpha, \delta, \gamma$ and $C$ for LRDP ($W = 1$; when not varying, we set $\alpha = 2, C = 1, \delta = 0.9$ and $\gamma = 1$).</figcaption></figure>

Algorithm 4, is identical to Algorithm 2 except for choosing

$$ k \geq \frac{3(2\alpha - 1)KD(d - c)}{2(\alpha - 1)K'\tau_0\gamma} \qquad (18) $$

and for invoking Algorithm 3 in place of Algorithm 1.

**Theorem 7:** Let $\mathcal{Z} = [a, b]$, $\mathcal{X} = [c, d]$, and $p_{Z|X}$ be such that, for every $x \in \mathcal{X}$, $p_{Z|X}(\cdot|x)$ is C-Lipschitz, for $C < 2/W^2$ and $W = b - a$, and that, for every $z \in \mathcal{Z}$, $p_{Z|X}(z|\cdot)$ is D-Lipschitz, for some $D$. For every $\alpha > 1$ (LRDP order), $\gamma > 0$ (precision) and $0 < \delta < 1$ (confidence), we have that

$$ \Pr \left( \text{Algorithm 4 succeeds and} \\ \left| \epsilon_{\alpha}^{*}(p_{Z|X}) - \tilde{\epsilon}_{\alpha}(\mathcal{Z}, \mathcal{X}, \gamma, \delta, C, D) \right| \leq \gamma \right) \geq \delta. $$

### D. Experiments on LRDP

We test the validity of our approach by repeating the same experiments about LDP as presented in the previous section but using the new algorithms for LRDP estimation. The results confirm that our approach is practical and useful also in this framework, and confirm that the theoretical bound for sampling is higher than the actual number needed in practice.

**Number of samples:** First of all, for LRDP, the number of samples also depends on another parameter (apart from $\gamma, \delta$, and $C$), viz. $\alpha$. In Fig. 7, we depict the dependencies of $n$ as functions of the other parameters; as we can see, the higher dependency is on $\gamma$ and $C$, with a similar contribution.

**Analysis of Algorithm 4:** As we have done for LDP, we begin by analyzing the behavior of the estimator in Algorithm 4 for the truncated Laplace with $B = 1$ (the case for the Gaussian is similar). We suppose the same experimental environment in Section III-E with parameters $\gamma \approx \epsilon/4$ and $\delta = 0.9$; so, $\epsilon \approx 0.027$, $D \approx 0.66$ and $C \approx 0.33$; moreover, we let $\alpha = 2$ and, consequently, $k = 39$. In Table V we display $\tilde{\epsilon}(x_i, x_j)$ for some pairs $x_i$ and $x_j$ among the $\frac{k(k-1)}{2} (= 741)$ computed during an execution of Algorithm 4. Once again, the algorithm correctly returns $\tilde{\epsilon} = 0.027$, and again, this value is reached only for the pair of extremes $\{x_i, x_j\} = \{0, 1\}$. Therefore, we will focus on $x_1 = 0$ and $x_2 = 1$ to analyze Algorithm 3.

**Analysis of Algorithm 3:** We show in Fig. 8 the values of the estimated $\epsilon$ across 100 executions of the proposed algorithm for LRDP. As already anticipated, also here we have a clear gap between the theoretical $n$ and the practical number of samples needed to satisfy Theorem 6. Indeed, for LRDP, $n_{TH}$ is way too large, and $n_{PR}$ is very small: there is a factor $\sim 10^7$ between the
<table><caption>TABLE V
$\tilde{\epsilon}(x_i, x_j)$ FOR SOME PAIRS AMONG THE $\frac{k(k-1)}{2}$ COMPUTED BY ALGORITHM 4 WITH $\delta = 0.9$ AND $\gamma = 0.006$ FOR A TRUNCATED LAPLACE OF PARAMETER $B = 3.5$</caption><thead><tr><th>x<sub>i</sub></th><th>x<sub>j</sub></th><th>ε̃(x<sub>i</sub>, x<sub>j</sub>)</th><th>x<sub>i</sub></th><th>x<sub>j</sub></th><th>ε̃(x<sub>i</sub>, x<sub>j</sub>)</th></tr></thead><tbody><tr><td>0.00</td><td>1.00</td><td><strong>0.027</strong></td><td>0.55</td><td>0.47</td><td>0.000</td></tr><tr><td>0.05</td><td>0.87</td><td>0.024</td><td>0.61</td><td>0.32</td><td>0.005</td></tr><tr><td>0.11</td><td>0.71</td><td>0.017</td><td>0.66</td><td>0.16</td><td>0.013</td></tr><tr><td>0.16</td><td>0.55</td><td>0.008</td><td>0.71</td><td>0.00</td><td>0.018</td></tr><tr><td>0.21</td><td>0.39</td><td>0.002</td><td>0.79</td><td>0.87</td><td>0.000</td></tr><tr><td>0.26</td><td>0.24</td><td>0.000</td><td>0.84</td><td>0.71</td><td>0.001</td></tr><tr><td>0.32</td><td>0.08</td><td>0.002</td><td>0.89</td><td>0.55</td><td>0.006</td></tr><tr><td>0.39</td><td>0.95</td><td>0.012</td><td>0.95</td><td>0.39</td><td>0.012</td></tr><tr><td>0.45</td><td>0.79</td><td>0.007</td><td>1.00</td><td>0.24</td><td>0.021</td></tr><tr><td>0.50</td><td>0.63</td><td>0.001</td><td>1.00</td><td>0.00</td><td><strong>0.027</strong></td></tr></tbody></table>

The bold values are those returned by Algorithm 2 (the maximum among all the values calculated).

<table><caption>TABLE VI
NUMBERS OF SAMPLES NEEDED BY ALGORITHM 3 ON DIFFERENT MECHANISMS (TRUNCATED LAPLACE OR GAUSSIAN) WITH $\delta = 0.95$</caption><thead><tr><th>Mechanism</th><th>Scale<br>(B/σ)</th><th>ε</th><th>γ</th><th>n<sub>TH</sub></th><th>n<sub>PR</sub></th><th>m</th></tr></thead><tbody><tr><td>Laplace</td><td>1.5</td><td>.143</td><td>.04</td><td>8e+12</td><td>5e+05</td><td>4850</td></tr><tr><td>Laplace</td><td>2</td><td>.082</td><td>.02</td><td>1e+12</td><td>3e+05</td><td>2066</td></tr><tr><td>Laplace</td><td>3</td><td>.037</td><td>.01</td><td>5e+11</td><td>3e+05</td><td>1013</td></tr><tr><td>Laplace</td><td>5</td><td>.013</td><td>.004</td><td>6e+11</td><td>5e+05</td><td>720</td></tr><tr><td>Gaussian</td><td>1.5</td><td>.016</td><td>.004</td><td>6e+12</td><td>2e+06</td><td>2232</td></tr><tr><td>Gaussian</td><td>2</td><td>.0052</td><td>.002</td><td>6e+12</td><td>2e+06</td><td>1560</td></tr><tr><td>Gaussian</td><td>3</td><td>.001</td><td>.0003</td><td>3e+14</td><td>3e+07</td><td>3240</td></tr><tr><td>Gaussian</td><td>5</td><td>.00013</td><td>5e-05</td><td>1e+16</td><td>3e+08</td><td>5523</td></tr></tbody></table>

We repeat here the values of $\epsilon$ (from table ii) and use $\gamma \approx \epsilon/4$. We then provide: the theoretical $n$ ($n_{th}$), the practical one ($n_{pr}$), and the number of sub-intervals ($m$).

<figure><img src="image_9.png" /><figcaption>Fig. 8. Analysis on $n$ across 100 execution of Algorithm 3 with $\delta = 0.95$ and $\gamma \approx \epsilon/4$. In both cases, the scale ($B$ and $\sigma$) is 1.5; so, $\epsilon = 0.143$ and $\gamma = 0.04$ for Laplace, whereas $\epsilon = 0.016$ and $\gamma = 0.004$ for Gaussian.</figcaption></figure>

two. To show this, we report in Table VI a comparison between such values for different sets of parameters.

## V. CONCLUSION AND FUTURE WORK

In this paper, we studied to what extent final users can infer information about the level of protection of their data in the differential privacy setting when the obfuscation mechanism is unknown to them (the so-called “black-box” scenario). We first proved that, without any assumption on the underlying distributions, it is not possible to estimate the degree of protection of the data, not even with low levels of precision and confidence. Our proof is stated for LDP and LRDP, but it also holds for (the central versions of) DP and RDP. By contrast, when the densities involved are Lipschitz in a closed interval, such guarantees exist for both $\epsilon$-LDP and LRDP. This fills a gap in the literature by providing both general impossibility results and limited possibility results for the estimation of the strength of (L)DP and (L)RDP.

We validated our results using two of the best known DP data obfuscation mechanisms (namely, the Laplace and the Gaussian ones). What we provided here is the first such estimator for local

DP; indeed, to the best of our knowledge, the very few existing tools for LDP only do auditing, so they are used to disprove the $\epsilon$ claimed by the providers (see, e.g., [30]). In particular, differently from our approach, they do not estimate the real $\epsilon$ with guarantees; so, comparative studies are not possible at the moment.

This is just the starting point of our investigations. Possible directions for future research involve finding other possible assumptions on the distributions that allow for theoretical guarantees of the estimator, in particular for discrete distributions. In any case, as our impossibility results make evident, the crucial thing is to have distributions without peaks; so, some form of smoothness is needed. Orthogonally, we can renounce to any theoretical guarantee and use estimators for ratios of probability distributions that may perform well in practice. Many works in this direction have been done (see, e.g., [59], [60], [61], [62], [63]) and it would be interesting to see their performances in the setting of DP. This would also have the advantage of not making any assumptions on the distributions involved.
REFERENCES

[1] C. Dwork, "Differential privacy," in *Proc. Int. Colloq. Automata Lang. Program.*, Springer, 2006, pp. 1-12.

[2] Differential Privacy Team (Apple Inc.), "Learning with privacy at scale," 2017. [Online]. Available: https://machinelearning.apple.com/research/learning-with-privacy-at-scale

[3] C. Dwork, "Differential privacy: A survey of results," in *Proc. 5th Int. Conf. Theory Appl. Models Comput.*, Springer, 2008, pp. 1-19.

[4] Ú. Erlingsson, V. Pihur, and A. Korolova, "RAPPOR: Randomized aggregatable privacy-preserving ordinal response," in *Proc. 2014 ACM SIGSAC Conf. Comput. Commun. Secur.*, 2014, pp. 1054-1067.

[5] A. Machanavajjhala, D. Kifer, J. Abowd, J. Gehrke, and L. Vilhuber, "Privacy: Theory meets practice on the map," in *Proc. IEEE 24th Int. Conf. Data Eng.*, 2008, pp. 277-286.

[6] A. Narayanan and V. Shmatikov, "De-anonymizing social networks," in *Proc. IEEE 30th Symp. Secur. Privacy*, 2009, pp. 173-187.

[7] F. Galli, S. Biswas, K. Jung, T. Cucinotta, and C. Palamidessi, "Group privacy for personalized federated learning," 2022, arXiv:2206.03396.

[8] Z. Xu et al., "Federated learning of gboard language models with differential privacy," 2023, arXiv:2305.18465.

[9] M. S. Alvim, K. Chatzikokolakis, C. Palamidessi, and A. Pazii, "Local differential privacy on metric spaces: Optimizing the trade-off with utility," in *Proc. IEEE 31st Comput. Secur. Found. Symp.*, 2018, pp. 262-267.

[10] I. Mironov, "Rényi differential privacy," in *Proc. IEEE 30th Comput. Secur. Found. Symp.*, 2017, pp. 263-275.

[11] C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor, "Our data, ourselves: Privacy via distributed noise generation," in *Proc. 24th Annu. Int. Conf. Theory Appl. Cryptographic Techn.*, Springer, 2006, pp. 486-503.

[12] A. Albarghouthi and J. Hsu, "Synthesizing coupling proofs of differential privacy," in *Proc. ACM Prog. Lang.*, vol. 2, pp. 58:1-58:30, 2018.

[13] G. Barthe, M. Gaboardi, E. J. G. Arias, J. Hsu, C. Kunz, and P. Strub, "Proving differential privacy in hoare logic," in *Proc. IEEE 27th Comput. Secur. Found. Symp.*, 2014, pp. 411-424.

[14] D. Chistikov, A. S. Murawski, and D. Purser, "Asymmetric distances for approximate differential privacy," in *Proc. 30th Int. Conf. Concurrency Theory*, 2019, pp. 10:1-10:17.

[15] J. P. Near et al., "Duet: An expressive higher-order language and linear type system for statically enforcing differential privacy," in *Proc. ACM Prog. Lang.*, vol. 3, no. OOPSLA, pp. 172:1-172:30, 2019.

[16] J. Reed and B. C. Pierce, "Distance makes the types grow stronger: A calculus for differential privacy," in *Proc. ACM SIGPLAN Int. Conf. Funct. Program.*, 2010, pp. 157-168.

[17] D. Zhang and D. Kifer, "LightDP: Towards automating differential privacy proofs," in *Proc. 44th ACM SIGPLAN Symp. Princ. Program. Lang.*, 2017, pp. 888-901.

[18] M. Bun, M. Gaboardi, and L. Glinskih, "The complexity of verifying boolean programs as differentially private," in *Proc. IEEE 35th Comput. Secur. Found. Symp.*, 2022, pp. 396-411.

[19] M. Nasr et al., "Tight auditing of differentially private machine learning," in *Proc. 32nd USENIX Secur. Symp.*, 2023, pp. 1631-1648.

[20] K. Dixit, M. Jha, S. Raskhodnikova, and A. Thakurta, "Testing the lipschitz property over product distributions with applications to data privacy," in *Proc. 10th Theory Cryptogr. Conf.*, Springer, 2013, pp. 418-436.

[21] A. C. Gilbert and A. McMillan, "Property testing for differential privacy," in *Proc. IEEE 56th Annu. Allerton Conf. Commun. Control Comput.*, 2018, pp. 249-258.

[22] X. Liu and S. Oh, "Minimax optimal estimation of approximate differential privacy on neighboring databases," in *Proc. Int. Conf. Neural Inf. Process. Syst.*, 2019, pp. 2417-2428.

[23] M. Jagielski, J. R. Ullman, and A. Oprea, "Auditing differentially private machine learning: How private is private SGD?," in *Proc. Proc. Int. Conf. Neural Inf. Process. Syst.*, 2020, pp. 22205-22216.

[24] F. Lu et al., "A general framework for auditing differentially private machine learning," in *Proc. Int. Conf. Neural Inf. Process. Syst.*, 2022, pp. 4165-4176.

[25] B. Bichsel, S. Steffen, I. Bogunovic, and M. T. Vechev, "DP-Sniper: Black-box discovery of differential privacy violations using classifiers," in *Proc. IEEE Symp. Secur. Privacy*, 2021, pp. 391-409.

[26] Ö. Askin, T. Kutta, and H. Dette, "Statistical quantification of differential privacy: A local approach," in *Proc. 43rd IEEE Symp. Secur. Privacy*, 2022, pp. 402-421.

[27] Y. Lu, Y. Wei, M. Magdon-Ismail, and V. Zikas, "Eureka: A general framework for black-box differential privacy estimators," in *Proc. IEEE Symp. Secur. Privacy*, 2024, pp. 913-931.

[28] T. Kutta, Ö. Askin, and M. Dunsche, "Lower bounds for Rényi differential privacy in a black-box setting," 2022, arXiv:2212.04739.

[29] J. Lokna, A. Paradis, D. I. Dimitrov, and M. Vechev, "Group and attack: Auditing differential privacy," in *Proc. ACM SIGSAC Conf. Comput. Commun. Secur.*, 2023, pp. 1905-1918.

[30] H. H. Arcolezi and S. Gambis, "Revealing the true cost of locally differentially private protocols: An auditing perspective," in *Proc. Privacy Enhancing Technol.*, vol. 2024, pp. 123-141, 2024.

[31] S. Oya, C. Troncoso, and F. Pérez-González, "Back to the drawing board: Revisiting the design of optimal location privacy-preserving mechanisms," in *Proc. ACM SIGSAC Conf. Comput. Commun. Secur.*, 2017, pp. 1959-1972.

[32] U. I. Atmaca, S. Biswas, C. Maple, and C. Palamidessi, "A privacy-preserving querying mechanism with high utility for electric vehicles," *IEEE Open J. Veh. Technol.*, vol. 5, pp. 262-277, 2024.

[33] W. L. Croft, J.-R. Sack, and W. Shi, "Differentially private obfuscation of facial images," in *Machine Learning and Knowledge Extraction*. Berlin, Germany: Springer, 2019, pp. 229-249.

[34] W. L. Croft, J. R. Sack, and W. Shi, "Differentially private facial obfuscation via generative adversarial networks," *Future Gener. Comput. Syst.*, vol. 129, pp. 358-379, 2022.

[35] N. Fernandes, M. Dras, and A. McIver, "Generalised differential privacy for text document processing," in *Proc. Int. Conf. Princ. Secur. Trust*, Springer, 2019, pp. 123-148.

[36] O. Feyisetan, T. Diethe, and T. Drake, "Leveraging hierarchical representations for preserving privacy and utility in text," in *Proc. 2019 IEEE Int. Conf. Data Mining*, 2019, pp. 210-219.

[37] O. Klymenko, S. Meisenbacher, and F. Matthes, "Differential privacy in natural language processing the story so far," in *Proc. Workshop Privacy Natural Lang. Process.*, 2022, pp. 1-11.

[38] P. Faustini, N. Fernandes, S. Tonni, A. McIver, and M. Dras, "Directional privacy for deep learning," 2023, arXiv:2211.04686.

[39] F. Galli, S. Biswas, K. Jung, T. Cucinotta, and C. Palamidessi, "Group privacy for personalized federated learning," in *Proc. Workshop Federated Learn. Recent Adv. New Challenges*, 2022, pp. 252-263.

[40] F. Galli, K. Jung, S. Biswas, C. Palamidessi, and T. Cucinotta, "Advancing personalized federated learning: Group privacy, fairness, and beyond," *SN Comput. Sci.*, vol. 4, no. 6, 2023, Art. no. 831.

[41] B. Weggenmann and F. Kerschbaum, "Differential privacy for directional data," in *Proc. ACM SIGSAC Conf. Comput. Commun. Secur.*, 2021, pp. 1205-1222.

[42] C. Dwork, F. McSherry, K. Nissim, and A. D. Smith, "Calibrating noise to sensitivity in private data analysis," in *Proc. 3d Theory Cryptogr. Conf. Theory Cryptogr.*, S. Halevi and T. Rabin, Eds., Springer, 2006, pp. 265-284.

[43] C. Dwork and A. Roth, "The algorithmic foundations of differential privacy," *Found. Trends Theor. Comput. Sci.*, vol. 9, no. 3-4, pp. 211-407, 2014.

[44] J. Fu, Z. Sun, H. Liu, and Z. Chen, "Truncated laplace and gaussian mechanisms of RDP," 2023, doi: 10.48550/arXiv.2309.12647.

[45] Y. Wang, Z. Ding, G. Wang, D. Kifer, and D. Zhang, "Proving differential privacy with shadow execution," in *Proc. ACM SIGPLAN Conf. Program. Lang. Des. Implementation*, 2019, pp. 655-669.

[46] Y. Wang, Z. Ding, D. Kifer, and D. Zhang, "CheckDP: An automated and integrated approach for proving differential privacy or finding precise counterexamples," in *Proc. ACM SIGSAC Conf. Comput. Commun. Secur.*, 2020, pp. 919-938.

[47] B. Bichsel, T. Gehr, D. Drachsler-Cohen, P. Tsankov, and M. T. Vechev, "DP-finder: Finding differential privacy violations by sampling and optimization," in *Proc. ACM SIGSAC Conf. Comput. Commun. Secur.*, 2018, pp. 508-524.

[48] Z. Ding, Y. Wang, G. Wang, D. Zhang, and D. Kifer, "Detecting violations of differential privacy," in *Proc. ACM SIGSAC Conf. Comput. Commun. Secur.*, 2018, pp. 475-489.

[49] G. Cherubin, K. Chatzikokolakis, and C. Palamidessi, "F-BLEAU: Fast black-box leakage estimation," in *Proc. 2019 IEEE Symp. Secur. Privacy*, 2019, pp. 835-852.

[50] K. Chatzikokolakis, G. Cherubin, C. Palamidessi, and C. Troncoso, "The bayes security measure," 2020, arXiv: 2011.03396.

[51] J. C. Duchi, M. I. Jordan, and M. J. Wainwright, "Local privacy and statistical minimax rates," in *Proc. IEEE 54th Annu. Symp. Found. Comput. Sci.*, 2013, pp. 429-438.

[52] B. Ding, J. Kulkarni, and S. Yekhanin, "Collecting telemetry data privately," in *Proc. Int. Conf. Neural Inf. Process. Syst.*, 2017, pp. 3571-3580.

[53] A. Rényi, "On measures of entropy and information," in *Proc. 4th Berkeley Symp. Math. Statist. Probability*, 1961, pp. 547-561.
[54] F. Liu, "Statistical properties of sanitized results from differentially private laplace mechanism with univariate bounding constraints," *Trans. Data Priv.*, vol. 1, no. 2, pp. 169-195, 2019.

[55] J. Burkardt, "The truncated normal distribution," *Dept. Sci. Comput. website, Florida State Univ.*, vol. 1, no. 35, pp. 582014. [Online]. Available: https://people.sc.fsu.edu/~jburkardt/presenta_ons/truncated_normal.pdf

[56] P. Kairouz, S. Oh, and P. Viswanath, "Extremal mechanisms for local differential privacy," *J. Mach. Learn. Res.*, vol. 17, pp. 17:1-17:51, 2016.

[57] M. Jha and S. Raskhodnikova, "Testing and reconstruction of lipschitz functions with applications to data privacy," in *Proc. IEEE 52nd Annu. Symp. Found. Comput. Sci.*, 2011, pp. 433-442.

[58] P. Virtanen et al., "SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python," *Nat. Methods*, vol. 17, pp. 261-272, 2020.

[59] T. Kanamori, S. Hido, and M. Sugiyama, "Efficient direct density ratio estimation for non-stationarity adaptation and outlier detection," in *Proc. Adv. Neural Inf. Process. Syst.*, 2008, pp. 809-816.

[60] T. Kanamori, T. Suzuki, and M. Sugiyama, "Theoretical analysis of density ratio estimation," *IEICE Trans. Fundam. Electron., Commun. Comput. Sci.*, vol. E93-A, no. 4, pp. 787-798, 2010.

[61] M. Sugiyama, T. Suzuki, and T. Kanamori, "Density-ratio matching under the bregman divergence: A unified framework of density-ratio estimation," *Ann. Inst. Statist. Math.*, vol. 64, pp. 1009-1044, 2012.

[62] S. Liu, A. Takeda, T. Suzuki, and K. Fukumizu, "Trimmed density ratio estimation," in *Proc. Int. Conf. Neural Inf. Process. Syst.*, 2017, pp. 4521-4531.

[63] S. Kpotufe, "Lipschitz density-ratios, structured data, and data-driven tuning," in *Proc. 20th Int. Conf. Artif. Intell. Statist., PMLR*, 2017, pp. 1320-1328.

<figure><img src="image_10.png" /></figure>

Daniele Gorla is an associate professor with the Department of Computer Science of the University of Rome "Sapienza". His research interest are focused on the semantics of concurrent programming, formal methods for security, algorithms, machine learning and software engineering. He was the PC co-chair of several events, most notably for CONCUR 2014; he was also a PC member for ACM CCS 2025, CONCUR 2024, CONCUR 2022, and many others. He currently is the editor-in-chief of ACM SigLOG News (since 2023), an associate editor of *ACM Transactions on Computational Logic* (since 2023) and a member of the Editorial Board of the *Journal of Logical and Algebraic Methods in Computer Science*, Elsevier (since 2020).

<figure><img src="image_11.png" /></figure>

Louis Jalouzot received the master's degree in applied mathematics (ENS Paris-Saclay, MVA) and in fundamental computer science (ENS Lyon). He is currently working toward the PhD degree in neuroscience and machine learning with CEA and ENS, Paris. His research focuses on bridging symbolic theories and vectorial representations to understand neural coding in both artificial intelligence models and the human brain, particularly for language processing.

<figure><img src="image_12.png" /></figure>

Federica Granese received the PhD degree in computer science from École Polytechnique and Sapienza University. She holds a Starting Research Position (SRP) with Inria Center, the Université Côte d'Azur, joint with the Defense Security Mission at Inria. She was previously a postdoctoral fellow with Sorbonne Université - IRD (UMMISCO) in Paris. Her research focuses on securing machine learning algorithms with applications in the NLP and medical fields.

<figure><img src="image_13.png" /></figure>

Catuscia Palamidessi is director of Research with Inria Saclay. Her research interests include privacy, machine learning, fairness, and secure information flow. She has been leading various scientific projects, including an ERC advanced grant to conduct research on Privacy and Machine Learning. In recognition of her research achievements, in 2022 she received the Grand Prix of the French Academy of Science. She has been on the Editorial Board of several journals, including *IEEE Transactions in Dependable and Secure Computing*, and *ACM Transactions on Privacy and Security*. She is the chair of the SIGLOG executive committee.

<figure><img src="image_14.png" /></figure>

Pablo Piantanida (Senior Member, IEEE) received the BSc degree in electrical engineering and the MSc degree from the University of Buenos Aires (Argentina) in 2003, and the PhD degree from Université Paris-Sud (Orsay, France) in 2007. In October 2007 he has joined the Department of Telecommunications at Supélec and in 2015 the Laboratoire des Signaux et Systèmes (L2S) - CNRS at CentraleSupélec within Université Paris-Saclay. He is currently director of the International Laboratory and Learning Systems (IRL - ILLS), professor with CentraleSupélec (Université Paris-Saclay) with CNRS and Associate Academic Member Mila - Quebec AI Institute (Mila). He has served as general co-chair of the 2019 IEEE International Symposium on Information Theory, and as area chair for several conferences and he was associate editor for *IEEE Transactions on Information Forensics and Security*. In the past, he has worked on the information-theoretic principles beyond distributed compression, statistical decision, universal source coding, cooperation, feedback, index coding, key generation, security and privacy, among others. His current research is in the areas of machine learning, computer vision and natural language processing.