3
$\begingroup$

I was looking into Google's DP library and its implementation of bounded DP-average. The library implemented DP-average following the following algorithm presented in Li et al. (2016):

Proposition 2.22 Algorithm 2.3 satisfies ϵ-DP. [The] proof is quite long and tedious. We include [it] because to our knowledge this algorithm has not been presented in the literature before.

Algorithm 2.3: Noisy average clamping-down

$$\begin{align*} & \textbf{Input: } D\text{: one-dimensional dataset}, \epsilon\text{: privacy parameter},\left[a_\text{min},a_\text{max}\right]\text{: data range} \\ & S \leftarrow D.Sum() \\ & C \leftarrow D.Count() \\ & \textbf{if } C = 0 \textbf{ then} \\ & \ \ \ \ \textbf{return } a_\text{min} \text{ with prob }\frac{1}{2}\text{exp}\left(-\epsilon/2\right) \text{, and a value sampled uniformly from }\left[a_\text{min},a_\text{max}\right]\text{ with prob }1-\frac{1}{2}\text{exp}\left(-\epsilon/2\right)\\ & \textbf{end if}\\ & A \leftarrow \left(\frac{S+\text{Lap}\left(\left(a_\text{max}-a_\text{min}\right)/\epsilon\right)}{C}\right) \\ & \textbf{if } A < a_\text{min} \textbf{ then} \\ & \ \ \ \ \textbf{return } a_\text{min} \\ & \textbf{else if } A > a_\text{max} \textbf{ then} \\ & \ \ \ \ \textbf{return } a_\text{max} \\ & \textbf{else } \\ & \ \ \ \ \textbf{return } A \\ & \textbf{endif} \end{align*}$$

This calculates the DP-average from DP-Sum and True-Count. My question is: is it is possible to improve it by adding noise to the true mean?

For instance, Let's assume there are $N$ sets and each set can have 0 to 100 elements in it. Then the sensitivity of the DP-average should be $100/N$. On the other hand, the sensitivity of the sum-mechanism is 100. Instead of using the sum-mechanism, we could add Laplace noise to the true average as follows:

DP-average = True average + $\text{Lap}\left(100/\left(N\cdot\epsilon\right)\right)$

Wouldn't this add less noise to the DP-average compared to Algorithm 2.3, thus allowing for a smaller $\epsilon$?

$\endgroup$
1
  • $\begingroup$ Give a link or full reference to the document you mention $\endgroup$
    – kodlu
    May 26, 2021 at 22:16

1 Answer 1

2
$\begingroup$

Welcome to Crypto.SE, and thank you for your interest in our open-source DP tooling! To implement BoundedMean, we actually use Algorithm 2.4 from Differential privacy: From Theory to Practice, not Algorithm 2.3.

The reason is because Algorithm 2.3 is not actually differentially private. To the best of my knowledge, the reference that exists for this fact is a footnote in my PhD thesis (at the bottom of this HTML page, or on page 211 of the PDF version). When implementing BoundedMean, we also tried some of the others algorithms proposed in this book, and Algorithm 2.4 was the one that seemed to work best empirically.

Now, to answer your question about adding noise directly: when building DP algorithms, you are only allowed to make decisions based on differentially private data. Even something as simple as "what is the scale of the noise we are adding" can actually leak more information than expected. In your question, $N$ is a private quantity, since it can go up or down by one if a user is added or removed to the dataset. This means that you can't use it as an argument to the noise without adding noise to it first, to make it differentially private as well (and count it towards the privacy budget).

$\endgroup$
4
  • $\begingroup$ Thanks, Ted for the clarification. One follow-up question is why not apply the noise on the true average rather than calculating from sum and count? Does one have benefits over another? $\endgroup$
    – Proy
    May 28, 2021 at 15:22
  • $\begingroup$ I added a paragraph to the answer to address that question. $\endgroup$
    – Ted
    May 28, 2021 at 23:09
  • $\begingroup$ Thanks for hinting at your thesis and the issue with Alg. 2.3. In the footnote, what exactly is meant by "the density of the output"? Is the density constant (for a given privacy budget \epsilon) -- but then for an interval of length 1, the density should be 1? Or is the output some specific value, such as 0 or 1, and "density of the output" is "probability mass" at that value? $\endgroup$
    – Ben JW
    Sep 2, 2022 at 15:05
  • $\begingroup$ Arg, I think I made a mistake I wrote this footnote. Sorry. Here's the corrected counterexample: using clamping bounds $[0,1]$, compare the probability distribution function of the noisy output from databases $D_1=[0]$ with the one from $D_2=[0,1]$. The first one is $\frac\varepsilon2\exp(−x\varepsilon)$, the second one $\varepsilon\exp\left(−2\left|𝑥−\frac12\right|\varepsilon\right)$, and the ratio of the two densities when $x\rightarrow1$ tends to $2$, which breaks the DP property for $\varepsilon<\ln2$. $\endgroup$
    – Ted
    Sep 4, 2022 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.