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 delve into the investigation of two notions of local diferential privacy (LDP), namely -LDP and Rényi LDP. On 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 and can be achieved by a simple histogram-based estimator.
A second variant is the so-called Rényi diferential privacy (RDP) [8], a relaxation of DP based
on the notion of Rényi divergence. More formally, a randomized mechanism is -LRDP of
order > 1 if, for every 1, 2, we have that
((1)‖(2)) ≤
(
However, both notions of DP are built into existing software products by the producing
companies, and the final users have no way of testing the real level of security (i.e., the real
value of ). They can only trust the producers, sometimes leading to unexpected (and unwanted)
behaviors. For this reason, we would like to study 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, and they can only sample from it (the so-called “black-box" scenario). A few
black-box approaches to related problems have been presented in the literature:
• [10] that, given an oracle who has access to the probability density functions on the
outputs, casts the problem of testing diferential privacy on typical datasets (i.e., datasets
with suficiently high probability mass under a fixed data generating distribution) as a
problem of testing the Lipschitz condition. Their result concerns variants of diferential
privacy called probabilistic DP and approximate DP.
• [11] prove both an impossibility result for DP and a possibility result for approximate
DP. Their impossibility result shows that, for any > 0 and proximity parameter > 0,
no privacy property tester with finite query complexity exists for DP. Moreover, they
achieve their possibility result using randomized algorithms.
• [12, 13], where the authors focus on (, )-DP and the estimation of the DP parameters of
a given (unknown) mechanism. In [12] the authors aim to estimate the parameters for a
ifxed pair of adjacent databases by focusing on the relation between the number of samples
required and the accuracy of the estimation, whereas they estimate the parameters of the
mechanism by repeating their estimation on every possible pair. In [13] the authors aim
at estimating, once is given, the of a certain (unknown) mechanism by focusing on
polynomial-time approximate estimators on a given subset of all the possible databases
(thus defining and estimating the notion of relative DP).
• The paper that is most closely related to ours is [14], but there are some diferences. First,
they only consider central DP, whereas we focus on LDP and LRDP. Second, we both
consider a pair of databases/values and evaluate the for this pair; to compute a better
under-approximation of the overall , they iterate their method over a (somehow chosen)
ifnite set of pairs without provable guarantees, whereas our method comes equipped
with formal guarantees. Third, we use histograms and rely on the Lipschitzness of the
noise function, whereas they use kernel density estimation and rely on Holder continuity
(a generalization of Lipschitzness). Fourth, we upper bound the number of samples
needed to achieve a certain precision and confidence in the estimation of , whereas
their theorem states that the estimation approximates asymptotically (within a certain
confidence range) as grows.
2. Our contributions
We first focus on (
sup ∈(1,2) log ︂( | (|1) )︂ | (|2) where (1, 2) d=ef { ∈ | | (|1) > 0 ∧ | (|2) > 0}. In this setting, an estimator ˜ is an algorithm that takes in input a pair (1, 2), a precision and a confidence (with > 0 and 0 < < 1), and returns a real that is supposed to approximate ⋆(1, 2) for at most the precision with probability at least the confidence. Our first main result states that such an estimator cannot exist: Theorem 1 (Impossibility). For every > 0 (precision), 0 < < 1 (confidence), 1, 2 ∈ , and probabilistic estimator algorithm ˜ that almost surely terminates, there exists a probability distribution | such that
Pr (︀ ⃒⃒ ⋆(1, 2) − ˜(1, 2, , )⃒⃒ > )︀ > 1 − .
We remark that this impossibility result is very strong: it shows that no estimator exists, even
if (
By contrast, if we confine ourselves to the continuous case and assume that the densities 2 | (·| 1) and | (·| 2) over = [, ] are -Lipschitz with < (− )2 , then a probabilistic histogram-based estimator exists, whose pseudocode is provided in Algorithm 1. For the desired precision , the estimator first divides into sub-intervals, each of width d=ef − , where d=ef ⌈︂ 6( − ) ⌉︂ and d=ef
1 − − ( − ) 2 .
In particular, we set 0 = and +1 = + ; one can readily check that = . Then, the estimator chooses (the number of samples) such that where is defined as
2(1 − ) + 4 (, , / 12) ≤ 1 − , (, , ) d=ef exp ︁( − (− 1)2 )︁ 1+ + exp ︁( − (1− − )2 )︁
2
1 − (1 − )
(note that is exponentially decreasing in and ). The estimator then invokes the sampler
times both for 1 and for 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 | (·| 1) and
| (·| 2) in that sub-interval; so, it computes their ratio and returns the highest value. The
fact that this algorithm has provable guarantees is the second main result of our paper.
(
Pr (︀ Algorithm 1 succeeds and | ⋆(1, 2) − ˜(1, 2, , , , )| ≤ )︀ ≥ . Once we have this estimator for a single pair of values, we then aim at estimating the overall , i.e.
⋆(| ) d=ef
sup ⋆(1, 2).
1,2∈
(
Theorem 3. Let = [, ], = [, ], and | be such that, for every ∈ , | (·| ) is -Lipschitz, for < 2/( − )2, and that, for every ∈ , | (|· ) is -Lipschitz, for some . For every > 0 (precision) and 0 < < 1 (confidence), we have that
Pr (︀ Algorithm 2 succeeds and | ⋆(| ) − ˜(, , , , , )| ≤ )︀ ≥ .
We note that the Lipschitzness assumptions required by our theorems are met by the two most widely used DP mechanisms, namely Laplacian and Gaussian [15, 16]. Then, we validate 2: Output: ˜(, , , , ,
) 1: Input: (= [, ]), (= [, ]), , , , 3: Let ≥
3(− ) , where is defined in eq. (
and ||, and we discover that the strongest dependency
is on . Then, we compare the estimated against the real one and we discover that the
number of samples required to have satisfactory results in practice is significantly lower than
the theoretical one (i.e., that of (
Finally, our last bunch of results is on LRDP (see eq. (
− 2(1 − 0) − 2 (, 0, ′) ≥ and ′ = min ︁( 2(′2( −− 11)) , 2lo g− 21 )︁ . The returned value is −1 1 log ∑︀ 1 (︁ )︁ mator ˜ (, , , , ,
) (see Algorithm 2), the new number of buckets is ≥
where is defined in eq. (
and, of course, we invoke the estimator ˜ (1, 2, , , , ) modified as described above for
We run experiments similar to the ones for LDP that confirm the quality of our approach also for LRDP. In particular, for this second setting the gap between the number of samples suficient for achieving the guarantees of the theorem and the theoretical one is even more dramatic than for LDP: here the practical one is around 105 times smaller.