Calculating differentially private average of a dataset I was looking into Google's DP library and its implementation of bounded DP-average. The library implemented DP-average following the algorithm presented in Li et al.[1].
Algorithm 2.3, calculates the DP-average from DP-Sum and True-Count. My question is if 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 sum-mechanism is 100. Instead of using the sum-mechanism, we can add Laplace noise with true average as follows.
DP-average = True average + laplace (100/N*epsilon)
Isn't this going to add less noise to the DP-average compared to Algorithm 2.3? This will further allow for smaller epsilon.
[1] Li, Ninghui, Min Lyu, Dong Su, and Weining Yang. &quot;Differential privacy: From theory to practice.&quot; Synthesis Lectures on Information Security, Privacy, &amp; Trust 8, no. 4 (2016): 1-138.
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 &quot;what is the scale of the noise we are adding&quot; 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).