Private Lossless Multiple Release

We thank the reviewer for their reading and comments on our paper. We address some of the perceived weaknesses below:

W1: only applicable to Gaussian additive noise. Theorem 3.5 holds for any additive noise mechanism based on a noise distribution satisfying a convolution preorder (Definition 1.1). Besides the Gaussian distribution, the Laplace, zero-mean Skellam, and Poisson distributions all meet this criterion. In an updated version of the manuscript, we include more details on sampling for general distributions and for the Poisson distribution in particular.

The exponential mechanism cannot in general be expressed as a noise additive mechanism. Whether it can be implemented to satisfy lossless multiple release is an interesting open problem.

W2: computational cost. The computational efficiency of our methods is fairly straightforward, so we did not really discuss it, but we agree with the reviewer that a discussion should be included. Since the additive noise mechanisms we consider add independent noise in each dimension, the space and time complexity of implementing it with lossless multiple release scales linearly with each dimension. We consider one-dimensional noise henceforth. To allow for releases in arbitrary privacy order, we need to store all $k$ past releases when making the $k+1$’st release. For time complexity, note that any release requires drawing one (possibly conditioned) noise sample. The time complexity of the sampling depends on the particular distribution: In the case of Gaussian noise, it always corresponds to a single sample from a Gaussian.

W3: comparing to mechanisms beyond gradual release, e.g. Renyi-DP. Lossless multiple release (Definition 3.1) does not rely on a fixed privacy notion but rather ensures, information-theoretically, that a set of releases contain no more information than the least private release. In particular, for any fixed $\alpha$, we support $(\alpha, \varepsilon)$-RDP lossless multiple release with respect to $\rho=\varepsilon$.

W4: practical deployment requiring careful calibration. Generally, implementations of differential privacy require carefully choosing privacy parameters. Our contributions in this paper arguably make this easier in some contexts: If multiple releases of a statistic are to be made, we can sometimes (Theorem 3.5) do it dynamically at no cost in the privacy-utility trade-off. Not having to decide on privacy parameters up front saves resources spent on planning.

We thank the reviewer for their careful reading and comments on our paper. We address the perceived weaknesses below:

W1: Relation between Algorithm 1 and the Brownian mechanism. We agree with the reviewer that Algorithm 1 can be interpreted as the Brownian mechanism combined with Brownian bridge sampling, but we would argue that it is not a trivial translation. Given the focus on ex-post $(\varepsilon, \delta)$-DP in [WWRR’22], it is not immediate that the Brownian mechanism as stated can be sampled in arbitrary order and that it is lossless.

Second, we believe that there is a value in deriving these results from first principles. Avoiding the language of continuous time processes makes for a less technically demanding exposition, increasing the chance that these results see real-world uptake.

W2: technical contribution. We emphasize that our Theorem 3.5 makes a statement not only for Gaussian noise but (as the reviewer points out) for any additive noise distribution satisfying Definition 1.1. There are many such distributions, including the Laplace, zero-mean Skellam, and Poisson distributions.

In an updated version of the manuscript, we include a version of Algorithm 1 for generic noise distributions. We also give privacy guarantees for the Poisson distribution, and use it as an illustrative example of lossless multiple release for discrete probability distributions (which is what can be implemented on discrete computers).

We thank the reviewer for the feedback and questions. Our technique applies to additive noise mechanisms as well as to invertible post-processing of additive noise mechanisms. In particular, it applies to factorization mechanisms for which the noise added to queries is correlated. This is a rather large class of mechanisms, but the reviewer is correct that it does not include all mechanisms. For example, we do not know how to do lossless private multiple release of iterative methods such as private SGD.

Regarding the question about factorization mechanisms with multiple strategy matrices this is a general question that is not specific to multiple release. The situation is usually modeled by combining all strategy matrices into one. The workload matrix can be changed freely as long as it can be expressed as a matrix product LR, where R is the strategy matrix.

We thank the reviewer for the positive review and the question about the lossless multiple release setting.

Realistic privacy settings could be the military setting itself (which Bell-LaPadula was designed for), or other settings where analysts have different trust levels (here the more trusted analysts would get more accurate releases). Another example is if a company wants to release a statistic, say, user statistics: they could make an accurate release for their own data analysts, a less accurate release for external consultants, and include an even less accurate release in a report for shareholders or other external actors. A benefit of this is that lossless multiple release allows for dynamic updates: an external consultant that later gets employed directly by the company could get the more accurate release without constituting a privacy violation or requiring an increased privacy budget to reach the same accuracy.