Privacy by Postprocessing the Discrete Laplace Mechanism

Quentin Hillebrand, Jacob Imola, Rasmus Pagh, Sia Sejer · 2026

Read Privacy by Postprocessing the Discrete Laplace Mechanism by Quentin Hillebrand, Jacob Imola, Rasmus Pagh, Sia Sejer (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-06502.txt.

Introduction

Quentin Hillebrand, Jacob Imola, Rasmus Pagh, and Sia Sejer show new uses for the discrete Laplace mechanism, a classic privacy tool that adds geometric noise to counts. Post-processing its output, they obtain an unbiased estimator for a broad class of fast-growing but controlled functions of the original data, extending a recent result for the continuous Laplace mechanism.

Post-processing can also reproduce the output distributions of the Laplace and Staircase mechanisms at identical privacy levels, making the discrete version preferable whenever data are discrete. Variance bounds are given, and the estimator is often computable in linear or polynomial time for structured functions. Uses include profile estimation and federated analysis.

Catalog record

CREATORQuentin Hillebrand, Jacob Imola, Rasmus Pagh, Sia Sejer
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE89 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.06502

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Privacy by Postprocessing the Discrete Laplace Mechanism Quentin Hillebrand, Jacob Imola, Rasmus Pagh, Sia Sejer Abstract We show that an “old dog,” the classical discrete Laplace (aka. geometric) mechanism, can “perform new tricks”: 1. It can be post-processed to yield a simple, unbiased estimator of any subexponential function f f of the original data, giving a simple, discrete, multivariate version of the recent unbiasing result for the Laplace mechanism by Calmon et al. (FORC ’25). 2. It can be post-processed to output the same distribution as the Laplace mechanism or the Staircase mechanism with identical privacy parameters. Thus, the discrete Laplace mechanism is a versatile mechanism that should be preferred over the Laplace and Staircase mechanisms whenever the data is discrete (or can be made discrete while controlling ℓ 1 \ell_{1} -sensitivity). We show bounds on the variance of our estimator, compared to the mean square error of the biased estimator that simply evaluates the f f on the output of the mechanism. Though our unbiased estimator has exponential running time for worst-case functions, we show that it can often be computed in linear or polynomial time for some common functions exhibiting structure. We showcase the properties of our methods empirically with several use cases including profile and entropy estimation, as well as distributed/federated data analysis applications in which unbiasedness is key to accuracy. 1 Introduction Differential privacy has a powerful post-processing property: For any differentially private mechanism \mathcal{M} and any function f , we can release f(\mathcal{M}(x)) while preserving the privacy guarantees of \mathcal{M} . As a consequence, we can release all values f_{i}(\mathcal{M}(x)) for any family of functions (f_{i})_{i\in I} with no loss of privacy. In this paper, we consider additive noise mechanisms where \mathbb{E}\left[\mathcal{M}(x)\right]=x . For non-linear functions f , the expected function value \mathbb{E}\left[f(\mathcal{M}(x))\right] , assuming it exists, is in general different from f(x) . Such bias can be a problem in some applications, which led 9 and later 1 to study methods for debiasing via post-processing of the Laplace mechanism. First, 9 showed how to construct unbiased estimators for multivariate polynomials. Later, 1 gave estimators in the univariate setting for a wide class of twice differentiable functions f . Debiasing in Post-Processing. In this paper, we propose a new post-processing method for the discrete Laplace mechanism \mathcal{M}_{\text{DLap}}:\mathbb{Z}^{n}\rightarrow\mathbb{Z}^{n} , first proposed and studied by 8 . For convenience we will use the notation \tilde{x}=\mathcal{M}_{\text{DLap}}(x) , that is, \tilde{x}_{i}=x_{i}+\eta_{i} where \eta_{i} is sampled i.i.d. from the discrete Laplace distribution with parameter p=e^{-\varepsilon} . This mechanism is a canonical way of releasing histograms, and more generally integer-valued data with sensitivity 1, with an \varepsilon -differential privacy guarantee. Given \tilde{x} , our post-processing method returns an unbiased estimator of f(x) for any univariate or multivariate function f where \mathbb{E}\left[f(\tilde{x})\right] exists and is finite. A sufficient condition for this is that f is subexponential (or exponential with low enough rate). Our method thus supports a class of functions f much wider than that of 1 , 9 , both of which can only handle functions that are twice differentiable. Previously, unbiased postprocessing of the discrete Laplace distribution had only been described in the special case of univariate threshold functions, by 7 . We show that our post-processing method is unique in the sense that it is the only deterministic method that constructs unbiased estimates in the discrete setting. From this, it follows that it has the smallest variance of all unbiased estimators. Though our estimator takes exponential time to compute for worst-case functions, we show that for functions which exhibit structure (e.g. decomposable functions such as entropy and order statistics), it is often possible to design linear or polynomial time algorithms for computing the unbiased estimation. Transformations to other Additive Noise Mechanisms. We show how to post-process \tilde{x} so that the resulting distribution is identical to that of the classical (real-valued) Laplace mechanism [ 3 ] or the Staircase mechanism [ 5 , 6 ] on input x with the same privacy parameter \varepsilon . This means the Discrete Laplace Mechanism is a versatile mechanism that should be preferred over the Laplace and Staircase Mechanisms whenever the data is discrete or can be made discrete while still controlling the \ell_{1} -sensitivity. Everything that can be done with these mechanisms can also be based on the Discrete Laplace Mechanism, and the latter may lead to better utility, especially for medium to large values of \varepsilon . Applications to Federated/ Distributed Settings. Unbiased estimators are particularly useful in settings where the statistic of interest can be obtained by summing or averaging many individual contributions. For example, suppose that each of k parties (e.g. hospitals) holds a distribution given by a histogram, that each histogram has been released with the Discrete Laplace mechanism, and we wish to compute the entropy of the joint distribution over all parties. Assuming independence, the joint entropy is the sum of the entropy of each distribution, a non-linear function of the histogram. Summing an unbiased estimator for the entropy of each distribution we get an estimator for the total entropy whose error scales with O(\sqrt{k}) . In contrast, summing biased estimators will result in error proportional to k , which will be worse for sufficiently large k . As another example, suppose we wish to gather statistics across histograms, for example the minimum, maximum, mean and variance of each column in the histograms. We can avoid bias in these estimates by using our estimator on the “transposed” histograms formed by combining information on each column across histograms. 1.1 Overview of Our Contributions. In Section 2 , we first show ( Theorem 1 ) that in the univariate case ( n=1 ) a linear combination of f(\tilde{x}-1) , f(\tilde{x}) , and f(\tilde{x}+1) is an unbiased estimator of f(x) for any function f and input x where \mathbb{E}\left[f(\tilde{x})\right] exists. This estimator can be interpreted as the discrete second derivative of f evaluated in \tilde{x} , analogous to the approach by 1 for univariate functions. We then show ( Theorem 2 ) that our method extends naturally to the multivariate case x\in\mathbb{Z}^{n} where the estimator is a linear combination of the function values f(\tilde{x}+\xi) for \xi\in\{-1,0,+1\}^{n} . Section 3 investigates properties of our unbiased estimator. We first show ( Theorem 4 ) that it is unique among deterministic estimators and has minimum variance among all unbiased estimators. In particular, for a black-box function f , any deterministic estimator requires 3^{n} function evaluations. Then we consider the mean square error (MSE) and show ( Theorem 5 ) that it is at most a factor O(1+1/\varepsilon^{4})^{n} worse than the MSE of the naive estimator f(\tilde{x}) . This bound is tight: Proposition 6 shows that there are functions for which our estimator exhibits this rate of exponential variance growth, but for other functions we instead see that the unbiased estimator is exponentially better . Section 4 shows that it is possible to post-process the Discrete Laplace Mechanism to be identical to either the classical Laplace Mechanism ( Theorem 10 ) or to the Staircase mechanism ( Theorem 17 ) while preserving the same privacy level \varepsilon . The insight is that it is possible to choose random variables X_{\varepsilon} and Y_{\gamma,\varepsilon} (independently of x

Read the complete text