Dithered Gaussian Mechanism for Randomness-Efficient Differential Privacy
Nikita P. Kalinin Institute of Science and Technology Austria [email protected]
Rasmus Pagh BARC University of Copenhagen [email protected]
arXiv:2607.06320v1 [cs.CR] 7 Jul 2026
Abstract We present the dithered Gaussian mechanism, a novel alternative to the discrete Gaussian mechanism for differential privacy that discretizes the private output rather than the noise distribution itself. By interpreting this discretization as post-processing of the Gaussian mechanism, our construction directly inherits the privacy guarantees of the standard Gaussian mechanism while avoiding vulnerabilities caused by finite-precision floating-point outputs. We show that the mechanism is provably randomness-efficient: by sampling the discretized output values directly, the number of high-quality random bits required for privacy can be reduced significantly and made independent of the noise level. This is achieved by separating the randomness into two sources: a high-quality source used for the privacy-critical sampling step, and a high-performance public source, possibly known to the adversary, that supplies the additional randomness needed for randomized discretization. This separation enables the use of cryptographically secure randomness without substantial performance loss. As an application, we study model training with DP-SGD and show that cryptographically secure noise generation with reduced exposure to floating-point vulnerabilities can be achieved with modest practical overhead.
1
Introduction
Modern machine learning increasingly relies on sensitive individual-level data, making formal privacy guarantees essential. Differential privacy provides one such guarantee by limiting how much any single data point can influence the output of an algorithm. The Gaussian mechanism [18] is one of the most widely used primitives for ensuring differential privacy. It is especially central in private machine learning, where it forms the noise-addition step of differentially private stochastic gradient descent (DP-SGD) [1]. Despite its ubiquity, the Gaussian mechanism has important practical limitations. First, it is an idealized continuous mechanism, whereas real implementations run on finite-precision computers. As a result, a faithful implementation of a continuous Gaussian distribution is impossible: naive samplers can leave detectable “holes” in the set of representable floating-point values, creating privacy vulnerabilities of the kind first observed for the Laplace mechanism [39] and later identified for the Gaussian mechanism itself [33]. A second limitation is the amount of randomness required to sample Gaussian noise. In the ideal continuous model, exact sampling requires infinitely many random bits, while high-precision implementations can still require many random bits in practice. This cost becomes substantial at scale: recent efforts to train language models entirely under differential privacy, such as the VaultGemma 1B model, required quadrillions of Gaussian random draws and petabytes of randomness to obtain a formal privacy guarantee [46]. At this scale, randomness generation itself can become a bottleneck [20]. Several discrete-valued mechanisms, most prominently the discrete Gaussian mechanism [9], address finite-precision concerns by adding discrete noise. However, these mechanisms can still require many privacy-critical random bits. Moreover, because their privacy Preprint.
guarantees do not directly follow from those of the continuous Gaussian mechanism, they require separate privacy analyses for composition and amplification by subsampling, making them difficult to use as drop-in replacements for Gaussian noise in DP-SGD. Unlike existing discrete mechanisms, which approximate Gaussian noise and typically require separate privacy analyses, our construction inherits the privacy guarantees of the standard Gaussian mechanism directly, making it compatible with existing Gaussian-based analyses. At the same time, the mechanism avoids vulnerabilities arising from finite-precision floating-point representations and is provably randomness-efficient, improving on prior efficient constructions. Finally, we apply the mechanism to DP-SGD and show that it enables cryptographically secure noise generation with reduced floating-point vulnerabilities and a modest time overhead. Compared with methods that use floating-point Gaussian noise sampled from pseudorandom number generators without cryptographic guarantees, our method incurs an overhead of about 30%, and only about 20% when compared with cryptographically secure noise generation in experiments on CIFAR-10. Our contributions. We propose a drop-in replacement for the Gaussian mechanism that is cryptographically secure, resistant to floating-point attacks, and time-efficient. This is achieved with a novel approach to noise addition that we call the dithered Gaussian mechanism. The mechanism is defined through the distribution of a rounded, dithered Gaussian output: we consider the value that would be obtained by adding Gaussian noise to the sensitive vector, adding a public random offset, or dither, and rounding the result to a discrete grid determined by the same public offset. Crucially, this discrete output distribution can be written down explicitly after conditioning on the dither, and our mechanism samples from it directly using high-quality private randomness, rather than sampling the intermediate continuous Gaussian noise. The key observation is that the rounded output is a post-processing of the standard Gaussian mechanism, so it directly inherits the privacy guarantees of the Gaussian mechanism. The public dither is not needed for privacy, but improves the quality of the discretization and helps reduce the amount of private randomness required for direct sampling. In particular, we show that the number of private random bits can be made independent of the Gaussian noise scale, without significantly changing the distribution of the perturbation relative to the Gaussian mechanism. This substantially reduces the cost of using cryptographically secure randomness. Since the released output is discrete by construction (conditioned on the public dither), the mechanism avoids finite-precision issues associated with floating-point outputs. Finally, we apply the mechanism to DP-SGD and show that it enables cryptographically secure private randomness with modest practical overhead. 1.1
Related work
Floating-point vulnerabilities and discrete mechanisms. A subtle but important issue in the implementation of differentially private mechanisms is the use of finite-precision floating-point arithmetic. Mironov [39] showed that naive implementations of the Laplace mechanism can leave detectable “holes” in the set of representable noisy outputs, which can be sufficient to reconstruct a significant part of the underlying data. Similar finite-precision issues have since been identified for other mechanisms, including the exponential mechanism [32], Noisy Max [17], and the Gaussian mechanism [33]. A related class of attacks exploits precision-dependent leakage: the precision of the released noisy value may depend on the exponent of the original value, thereby leaking information about the input [28]. Several implementation-level mitigations have been proposed [30, 28] and adopted in practical differential privacy libraries, including diffprivlib [31], OpenDP [41], and the “secure mode” of Opacus [49]. These approaches improve the robustness of floating-point implementations, but they do not remove the underlying mismatch between continuous idealized mechanisms and finite-precision computation. A more direct way to avoid this kind of vulnerability is to work only with values from a discrete domain. Several discrete-valued mechanisms have been proposed for this purpose, including the discrete Laplace mechanism, also known as the geometric mechanism [27]; the discrete Gaussian mechanism [9]; the binomial mechanism [18, 3]; and mechanisms based on Poisson random variables, such as the Skellam mechanism [2], the Skellam Mixture Mechanism [7], and the Poisson Binomial Mechanism [12]. By adding discrete noise and releasing discrete outputs, these mechanisms avoid the floating-point artifacts described above. However, they have two important limitations from the perspective of our work. First, they can still require substantial amounts of randomness for noise generation, unless one uses coarse approximations. Second, mechanisms such as the discrete 2
Gaussian, Skellam, and binomial mechanisms approximate Gaussian noise but do not automatically inherit the privacy guarantees of the continuous Gaussian mechanism. Consequently, analyses for composition, amplification by subsampling, or other accounting procedures generally have to be established separately. Randomness complexity. From a theoretical standpoint, the large randomness requirements of practical differentially private algorithms raise a natural question at the intersection of privacy and complexity: how much randomness is actually necessary for privacy? Canonne, Su, and Vadhan [10] initiated the study of the randomness complexity of differential privacy, showing that highly accurate private mechanisms can sometimes be implemented with surprisingly few random bits, in some settings as few as logarithmically many in the number of released statistics. This contrasts with the common intuition that the randomness required for privacy should scale with the dimension of the output. Their construction is based on a connection to secluded partitions from computational geometry [47], but is not computationally efficient. More recently, Ghentiyala [26] gave a computationally efficient alternative, at the cost of a polylogarithmic loss in the randomness-error trade-off. While both approaches are theoretically interesting, we are not aware of any demonstrations of their practical value. DP-SGD and discrete mechanisms. One of the most important applications of Gaussian noise in differential privacy is the training of machine learning models, most commonly through differentially private stochastic gradient descent (DP-SGD) [45, 8, 1]. The privacy guarantees of DP-SGD are typically established using privacy accountants that exploit the structure of the sampling procedure, including Poisson subsampling [1, 40, 36, 50, 37], shuffling [21, 22, 23, 48], sampling without replacement [6, 44], and random allocations such as Balls-in-Bins [14, 24]. Many of these analyses are developed specifically for the Gaussian mechanism, making it difficult to replace Gaussian noise with a different noise distribution without redoing the privacy analysis. Discrete mechanisms have also been studied in combination with DP-SGD, especially in federated learning with secure aggregation [3, 34, 2, 7, 12]. In this setting, the main goals are to obtain integer-valued noisy gradient sums, which integrate naturally with secure aggregation, and to reduce communication complexity. To the best of our knowledge, however, tight analyses of subsampled discrete mechanisms are not available even for the standard Poisson subsampling scheme. Existing approaches therefore typically start from concentrated DP or Rényi DP guarantees for the underlying discrete mechanism, combine them with a generic subsampling amplification lemma, and then apply generic composition within the chosen privacy framework, as in [34, 2]. This contrasts with our approach, where the discretized mechanism inherits Gaussian privacy guarantees by post-processing and can therefore reuse Gaussian-based analyses directly.
2
Background
In this section, we first introduce the notions of sensitivity, randomness complexity, and privacy that will be used throughout the paper. Second, we present the properties of the discrete Gaussian mechanism with respect to these notions. Sensitivity. Consider datasets X that are finite subsets of some set X. We work in the add/remove adjacency notion: two datasets X ∼ X ′ are neighbors if one can be obtained from the other by inserting or deleting a single data point. For a dataset of n elements we write its elements as X = {x(1) , . . . , x(n) } ⊆ X. For p ≥ 1, the global ℓp -sensitivity of a function f : X∗ → Rd is defined as ∆p (f ) := sup ∥f (X) − f (X ′ )∥p . X∼X ′
Randomness complexity. The randomness complexity of M is the expected number of random bits required to produce an output of the mechanism. As noted by Canonne, Su, and Vadhan [10], this quantity is tightly linked, up to an additive constant, to the Shannon entropy of the mechanism. When running a sequence of mechanisms independently (keeping public randomness fixed), the total private randomness complexity can be bounded by the sum of entropies plus an additive constant. Differential privacy. We can release an estimate of f (X) while satisfying differential privacy by adding noise to f (X) scaled according to the sensitivity. Intuitively, differential privacy means that the information released has roughly the same distribution for neighboring datasets X and X ′ . For 3
example, the Laplace mechanism (for p = 1) attains (ε, 0)-differential privacy and the Gaussian mechanism (for p = 2) attains (ε, δ)-differential privacy. We refer to Appendix A for definitions of differential privacy and properties of basic noise addition mechanisms. Discrete Gaussian mechanism. Traditionally, differential privacy has been analyzed under the idealized assumption that mechanisms have access to samples from continuous distributions. Under this viewpoint, the amount of randomness required by a mechanism is typically not accounted for explicitly, and no finite upper bound on the number of random bits is established. In practice, however, implementations must operate on finite-precision computers and therefore rely on discrete distributions or finite procedures for sampling. This issue has been studied, for example, by Balcer and Vadhan [5] and by Canonne, Kamath, and Steinke [9], who show that discrete analogues of standard private mechanisms admit finite bounds on the required randomness. A canonical example is the discrete Gaussian mechanism [9], which replaces continuous Gaussian noise with noise drawn from a discrete distribution over the integers with probabilities derived from the density of a Gaussian. Besides being implementable on finite computers, this mechanism provides a natural starting point for studying the randomness complexity of differentially private algorithms. Definition 1 (Discrete Gaussian mechanism). Let f : X n → Zd be a function with sensitivity ∆2 (f ). For σ > 0, the discrete Gaussian mechanism with scale σ∆2 (f ) releases M (x) = f (x) + Z, where Z = (Z1 , . . . , Zd ) ∈ Zd has independent coordinates, and each Zj is sampled from the one-dimensional discrete Gaussian distribution centered at 0 with scale σ∆2 (f ), that is, 2 exp − 2σ2 ∆z 2 (f )2 for all z ∈ Z. P(Zj = z) = P u2 exp − 2 2 u∈Z 2σ ∆2 (f ) Discretization. Note that the discrete Gaussian mechanism is defined only for integer-valued functions. To apply it to general real-valued functions, one must first discretize the values of f . Let f (x) ∈ Rd have sensitivity ∆2 (f ), and let h > 0 be a discretization parameter. If each coordinate is rounded to the nearest integer multiple of h, then the sensitivity of the discretized function f˜ satisfies √ h d ˜ ∆2 (f ) ≤ ∆2 (f ) + . (1) 2 However, such deterministic rounding introduces bias. Randomizing the √ decision whether to round up or down removes this bias, but increases the sensitivity to ∆2 (f ) + h d. A better trade-off can be obtained by allowing a resampling probability β ∈ (0, 1), resulting in a small bias, as described by Kairouz, Liu, and Steinke [34]. They use a random rotation technique to ensure that, with high probability, the sensitivity of the rounded vector is bounded by v ! u √ 2 2 p √ u dh dh ˜ 2 (f ) ≤ min ∆2 (f ) + h d, t∆2 (f ) + ∆ + 2 ln(1/β) ∆2 (f )h + . (2) 2 4 2 To guarantee privacy, the rotation must be repeated until the required condition on the ℓ2 norm is satisfied. Randomness complexity of the discrete Gaussian. The choice of discretization parameter h creates a tension for the discrete Gaussian mechanism because the noise must be generated on the lattice hZd . Equivalently, one may first scale the function by 1/h, round and apply the discrete Gaussian mechanism on Zd , and then rescale the output by multiplying with h. If σ > 0 is the noise level required by the Gaussian mechanism for differential privacy, then the corresponding discrete mechanism uses scale τ = σ∆2 (f˜)/h, before the resulting noise is ultimately rescaled by h. The variance of the resulting mechanism is close to that of the continuous Gaussian mechanism provided √ that h ≪ ∆2 (f )/ d. However, even in the regime where the variance increase is small, the entropy increases significantly as h approaches 0. In particular, the binary entropy of Zj sampled from the one-dimensional discrete Gaussian distribution with scale τ is 1 (3) H(Zj ) = log2 (2πe τ 2 ) + oτ (1), 2 4
ξ ξγ f (X) + y M(f (X))
Figure 1: From a privacy perspective, the dithered Gaussian mechanism can be thought of as mapping the Gaussian mechanism output f (X) + y to the nearest point on a randomly shifted axis-aligned grid {ξ(γ + z) | z ∈ Zd }. From an implementation perspective, we directly sample from a discrete distribution over the grid. see Lemma 6 of [38]. Since the coordinates of Z = (Z1 , . . . , Zd ) are independent, it follows that the binary entropy of the d-dimensional discrete Gaussian is d X
d log2 (2πe τ 2 ) + oτ (d). (4) 2 j=1 ˜ With τ = σ∆2 (f˜)/h this is approximately d log2 σ∆h2 (f ) + 2d for large enough d. We note that this bound is not tight for the case where h is large compared to σ∆2 (f˜), where in fact the entropy can be o(d). H(Z) =
3
H(Zj ) =
Dithered Gaussian Mechanism
We now present an alternative to the discrete Gaussian that avoids the need to discretize the input. Unlike the methods described in Section 2 it does not incur any increase in sensitivity. Moreover, our method uses provably fewer random bits, making it practical even when noise must be generated using slow cryptographically secure randomness. In addition, the method directly inherits the privacy guarantees of the (continuous) Gaussian mechanism, and therefore does not require separate proofs for composition or amplification by subsampling. Conceptual description. Our method, the dithered Gaussian mechanism, is illustrated in Figure 1. It can be thought of as a post-processing of the Gaussian mechanism with noise scale σ, i.e., the mechanism that outputs f (X) + y, where y ∼ N (0, σ 2 Id ). The post-processing simply rounds each coordinate to an axis-aligned grid of points with distance ξ > 0 between consecutive points along all axes. Performing this rounding deterministically would introduce bias, but we avoid this with a random shift of the grid: Sample public randomness (a, b) ∼ Uniform([0, 1)2 ) and define the coordinate-dependent dither by γi = (ai + b) mod 1 for each i ∈ [d]. Given f (X) ∈ Rd and y ∼ N (0, σ 2 Id ), the mechanism outputs M(f (X)) where, for i = 1, . . . , d, f (X)i + yi 1 M(f (X))i = ξ − γi + + γi . (5) ξ 2 Direct sampling from a discrete distribution. To avoid generating the Gaussian vector y we observe that it is possible to sample the integer-valued random variable f (X)i + yi 1 Zi := − γi + ξ 2 directly without first sampling yi . Indeed, for each k ∈ Z, the event Zi = k is equivalent to ξ k + γi − 12 − f (X)i ξ k + γi + 12 − f (X)i f (X)i + yi yi 1 k≤ − γi + 2 < k + 1 ⇔ ≤ < . ξ σ σ σ Denoting the cumulative distribution function of yσi ∼ N (0, 1) by Φ we thus have: ! ! ξ k + γi + 12 − f (X)i ξ k + γi − 12 − f (X)i Pr[Zi = k] = Φ −Φ , k ∈ Z. (6) σ σ 5
Algorithm 1 Dithered Gaussian mechanism Require: Function value f (X) ∈ Rd , parameters ξ > 0, σ > 0 1: Sample public randomness (a, b) ∼ Uniform([0, 1)2 ) 2: for i = 1, . . . , d do 3: γi ← (a · i + b) mod 1 4: Sample an integer Zi ∈ Z such that, for every k ∈ Z, ! ! ξ k + γi + 21 − f (X)i ξ k + γi − 12 − f (X)i Pr[Zi = k] = Φ −Φ σ σ 5: M(f (X))i ← ξ(Zi + γi ) 6: end for 7: return M(f (X))
Since M(f (X))i = ξ(Zi + γi ), this shows that to compute M(f (X))i it suffices to sample directly from a discrete distribution over Z. Algorithm details. We summarize the algorithm implementation in Algorithm 1. This abstract description uses real-valued variables and functions to determine sampling probabilities for the random variable Zi . In theory it is possible to generate samples from the distribution of Zi exactly even on a finite computer using a standard technique: Compute values only to the precision needed for a sample. For example, one may first propose a finite range of candidate integer values k ∈ Z together with a target precision for the computation of the probabilities Pr[Zi = k]. One then samples a uniform random variable from [0, 1) and uses the computed probability masses to locate the corresponding outcome. If the sampled value falls within the unresolved numerical precision margin, or within the probability mass of the truncated tail, the range of candidate values and the precision of the probability computation can be refined, for example by doubling both, and the procedure repeated. While exact sampling is thus possible in principle, such a procedure appears difficult to implement efficiently in practice, especially in the setting of model training on GPUs within existing machine learning frameworks. For this reason, we instead use an approximate, randomness-efficient sampling procedure based on high-probability interval truncation and arithmetic coding. Details can be found in Appendix B. This approach is vectorizable and can be efficiently implemented in PyTorch. Noise distribution. We characterize the distribution of M(X) over the random choice of γ and Z: Lemma 1. Over the randomness of the shift γi and index Zi , M(f (X))i is identically distributed to f (X)i + yi + ui ,
(7)
where ui ∼ Uniform(−ξ/2, ξ/2) and yi ∼ N (0, σ 2 ) are independent. The lemma is a consequence of the fact that the grid shift γi is uniformly distributed and independent of the Gaussian noise yi , which causes the perturbation caused by rounding to the nearest grid point to follow a uniform distribution on (−ξ/2, ξ/2). The full proof is provided in Appendix D. From a utility perspective, the dithered Gaussian mechanism is therefore equivalent to adding Gaussian noise N (0, σ 2 ) and uniform noise Uniform(−ξ/2, ξ/2). The variance of the resulting noise is Var(yi + ui ) = σ 2 + ξ 2 /12.
(8)
The density of the resulting noise distribution is pyi +ui (t) =
1 t + ξ/2 t − ξ/2 Φ −Φ . ξ σ σ
(9)
Integrating the density by parts, we obtain an expression for the cumulative distribution function of the noise introduced by the dithered Gaussian mechanism. Using ϕ to denote the standard Gaussian 6
distribution function
0.4
density
0.3 0.2 0.1 0.0
4
2
0
4
2
1.0 0.8
(0, 2) =1 =2 =4
0.6 0.4 0.2 0.0
4
2
0
2
4
Figure 2: Density and cumulative distribution function of the noise distribution of the dithered Gaussian mechanism for various choices of ξ, compared to the Gaussian mechanism with the same privacy guarantee. density: 1 Fyi +ui (t) = ξ
"
t + ξ/2 t + ξ/2 Φ + σϕ σ σ # ξ t − ξ/2 t − ξ/2 − t− Φ − σϕ . 2 σ σ t+
ξ 2
(10)
We can also quantify directly how close this noise distribution is to the Gaussian distribution used by the standard Gaussian mechanism in terms of the total variation distance. Proposition 2. Let Gσ ∼ N (0, σ 2 ), and let Uξ ∼ Uniform(−ξ/2, ξ/2) be independent of Gσ . Then 2 ξ dTV (Gσ + Uξ , Gσ ) ≤ 0.0202 . (11) σ Thus the distributional error introduced by dithering is quadratic in the relative grid width ξ/σ. For a d-dimensional mechanism with independent coordinates, the corresponding product-distribution distance is at most 0.0202 d(ξ/σ)2 by a standard coupling bound. Densities for dithered Gaussians for various choices of ξ can be seen in Figure 2. For ξ = σ we see that the density is nearly indistinguishable from that of the standard Gaussian, while larger values of ξ somewhat flatten the distribution. Randomness complexity. Next, we analyze the randomness complexity of the dithered Gaussian mechanism. We distinguish between the private (high-quality) randomness used for discrete sampling and the public randomness used to generate the pair (a, b) of uniform random variables defining the grid shift γ. The value γ may be shared with the adversary without compromising privacy, its purpose is solely to improve utility. We bound the entropy of the dithered Gaussian mechanism in the following lemma: Lemma 3. The worst-case private binary entropy of the dithered Gaussian mechanism is bounded by " #! 2 d σ 1 1 H(Z | γ) ≤ log2 2πe + + . (12) 2 ξ 2 12 The full proof is given in Appendix D. As noted above one can choose ξ ≈ σ and get an error distribution that is close to Gaussian. In this case, the lemma says that the entropy per coordinate is a small constant. More precise plots of the entropy are shown in Figure 3. Intuition for why this mechanism has low entropy, in expectation over the randomness of γi , is that for large enough ξ, the random noise yi is unlikely to make M(f (X))i differ from the output with fixed yi = 0. Thus each coordinate is close to deterministic in expectation, which implies low entropy. This argument extends and refines similar observations by Ghentiyala [26]. In theory, using techniques for sampling from low-entropy distributions based on 7
RMSE Normalized
Entropy (bits)
23 22 21 20
Expected Max
2−1 10−2
10−1
100
2.5
2.0
1.5
1.0 10−2
101
ξ/σ
10−1
100
101
ξ/σ (b) Root mean squared error normalized by σ.
(a) Entropy of the dithered Gaussian distribution.
Figure 3: The expected and maximum entropy (a) and normalized RMSE of the dithered Gaussian mechanism (b) as functions of ξ/σ.
explicit, ordered sampling probabilities [35, 16], multiple runs of the mechanism can be implemented in time near-linear in d using an expected number of random bits that matches the sum of all private entropy bounds plus O(log(1/β)) bits with probability 1 − β. As mentioned above, details of the implementation of our sampling mechanism can be found in Appendix B. 3.1
Comparison to the mechanism of Ghentiyala
Ghentiyala [26] recently proposed an efficient derandomization method for differentially private summation that, like our approach, relies on adding noise followed by a random grid shift and rounding. Both constructions exploit the fact that, after a suitable random shift, we expect only a small subset of coordinates to be “ambiguous” in the sense that their rounded values are likely to depend on the value of the added noise vector y. While our analysis relies on entropy, Ghentiyala’s construction uses discrete Laplace or Gaussian noise and achieves efficiency by selectively sampling noise only on coordinates whose values might change after rounding. This results in multiplicative polylogarithmic factors in the expected randomness complexity, making it higher than that of [10] and ours. Unlike our pairwise independent offset vector γ, Ghentiyala uses the same random offset for every coordinate. A consequence of this is that even though the expected randomness complexity is similar to that of [10], the variance in the number of random bits can be much higher than in the construction of [10] as well as ours. Like our construction, Ghentiyala’s is explicit and computationally efficient. Though no attempt is made in [26] to distinguish between public and private randomness complexity, it seems that the randomness used for the shift can be made public without affecting privacy. Lower Bound. In Appendix C, we prove the following lower bound on the private entropy of any differentially private mechanism for releasing a sensitivity-C statistic. To make the binary entropy well-defined we consider the special case where the statistic is integer-valued. Inputs z and z ′ are considered neighboring if |z − z ′ | ≤ C where C ∈ N. Let U denote the public randomness, and write MU for the mechanism obtained after conditioning on U . Theorem 4. There are absolute constants c, c0 > 0 such that for ε ∈ (0, 1) and δ ≤ c0 ε the following holds. Suppose MU : Z → Z is an (ε, δ)-differentially private mechanism under sensitivity C, for 1 every fixed value of public randomness U . If, for some α ∈ N and β ∈ (0, 10 ), for every z ∈ Z it holds that PrU,R [|MU (z) − z| > α] ≤ β (where R is the private randomness) then there exists z ∈ Z such that C EU H(MU (z)) ≥ c . εα The proof proceeds by fixing a suitable value of the public randomness and using a graph-theoretic argument based on component stability and barrier structure to derive a lower bound on the achievable accuracy. Since the Gaussian noise scale needed for privacy is proportional to the clipping radius C (up to the usual dependence on ε, δ), this lower bound shows that the relevant scale for private entropy is the ratio between the privacy noise scale and the accuracy scale. This is consistent with Lemma 3: 8
8 6
Dithered ξ = 0.5σ Dithered ξ = σ Dithered ξ = 2σ
RMSE Normalized
Entropy (bits)
10
Discrete h = 0.5/√ d Discrete h = 1/√ d Discrete h = 2/√ d
4 2
Discrete h = 0.5/√ d
1.6
Discrete h = 1/√ d Discrete h = 2/√ d Dithered ξ = 0.5σ Dithered ξ = σ Dithered ξ = 2σ Gaussian Mechanism
1.5 1.4 1.3 1.2 1.1 1.0
2−5 2−4 2−3 2−2 2−1
20
21
22
2−5 2−4 2−3 2−2 2−1
23
20
21
22
23
σ
σ
(a) Entropy in bits.
(b) Normalized RMSE.
Figure 4: Comparison of the dithered and discrete Gaussian mechanisms as a function of the noise scale σ. The left panel reports the entropy per coordinate. The right panel reports the RMSE on vectors in dimension d = 1000 sampled uniformly from the unit sphere. For each value of σ, we run each mechanism 1000 times and compute the average reconstruction error. The RMSE is normalized by the Gaussian mechanism baseline, which is equivalent to dividing by σ. The proposed dithered Gaussian mechanism requires a much smaller number of bits, which is independent of σ.
the private entropy of the dithered Gaussian mechanism depends on the dimensionless ratio σ/ξ, where σ is the Gaussian noise scale and ξ is the discretization width. In particular, choosing ξ = Θ(σ) gives constant private entropy per coordinate, while taking a finer grid increases the entropy only logarithmically in σ/ξ. Dithered Laplace mechanism. The proposed dithering scheme can also be applied to the Laplace mechanism. In Appendix E, we provide an additional set of results specifically for the Laplace mechanism. In particular, Theorem 9 establishes an upper bound on the randomness complexity, improving on the recent result of Canonne, Su, and Vadhan [10].
4
Experiments
In this section, we numerically study the utility and randomness complexity of the dithered Gaussian mechanism in comparison with the discrete Gaussian mechanism. Entropy and RMSE. Assume that the sensitive vectors are drawn from the unit sphere in dimension d = 1000. In the case of the discrete Gaussian mechanism, these vectors are further discretized with 0.5 √1 √2 discretization levels h ∈ { √ , d , d }. We set the resampling parameter to β = e−1/2 , as suggested d by Kairouz, Liu, and Steinke [34]. For the dithered Gaussian mechanism, we vary ξ ∈ {0.5σ, σ, 2σ}. In Figure 4, we show that, for a sufficiently large noise level σ, our method has much lower entropy and therefore requires fewer random bits to sample. In terms of utility, measured by the root mean squared error normalized by σ, the dithered Gaussian mechanism is much closer to the Gaussian mechanism, partly because it does not require discretizing the vectors. Model Training. We next study how the use of the dithered Gaussian mechanism affects the accuracy of DP-SGD. In Figure 5, we show the test accuracy on the CIFAR-10 dataset for different privacy budgets ϵ ∈ { 12 , 1, 2, 4, 8} with δ = 10−5 , comparing a standard implementation of Opacus [49] that samples non-secure Gaussian noise with the dithered Gaussian mechanism for different values of ξ ∈ { σ2 , σ, 2σ}. The dithered Gaussian mechanism uses cryptographically secure noise generated by the secrets module in the Python standard library [43]. We observe that the accuracy remains almost the same for ξ ∈ { σ2 , σ} and drops for ξ = 2σ, which is consistent with the findings in Figures 4 and 2. The cost of using the dithered sampling scheme together with secure noise generation is an increase in training time of about 30% compared with the standard Opacus implementation of DP-SGD, and about 20% compared with Opacus’ “secure mode”, which includes cryptographically secure noise generation. However, in terms of protection against floating-point vulnerabilities and privacy accounting, secure mode should be viewed as a heuristic rather than as providing a formal guarantee. 9
Gaussian Dithered, ξ = 0.5 Dithered, ξ = 1
56
170
Dithered, ξ = 2
52
Training time (s)
Test accuracy (%)
54
50 48 46
160
Gaussian Secure Gaussian Dithered, ξ = 0.5 Dithered, ξ = 1 Dithered, ξ = 2
150
140
44
130 42 2−1
20
21
22
2−1
23
20
21
22
23
Privacy budget ε
Privacy budget ε
(a) Test accuracy.
(b) Training time.
Figure 5: Comparison of Gaussian and dithered Gaussian mechanisms on CIFAR-10 across privacy budgets ϵ with δ = 10−5 . Solid lines show the mean over three runs, and shaded regions indicate one standard deviation. Plot (a) shows that for ξ = 0.5 and ξ = 1, there is no significant drop in test accuracy, whereas for ξ = 2, the accuracy is substantially lower. Plot (b) shows that using the dithered Gaussian mechanism with cryptographically secure noise generation incurs a runtime increase of only about 30% compared with the standard Opacus implementation of DP-SGD, and about 20% compared with Opacus’s secure mode.
The overhead is indicative of what one can expect in general, though the figure will depend on how much time is spent on randomness generation, which in turn depends on factors such as batch size. For instance, even when using only cryptographically secure noise, much larger overheads were observed in the work of Egan [20], ranging from 74% to over 400%. In that work, a rather small batch size of 32 is used, making the time spent on noise generation relatively larger. It should therefore be expected that, with a much larger batch size, the overhead would drop. Some implementation details: We trained a ConvNet model for 10 epochs with batch size 512 and clipping norm 1. PRV accounting was performed by Opacus, and the learning rates optimized on the validation set for each point. The time was measured on a single A100 GPU with 16 CPU cores; we report the total training time over 10 epochs with error bars computed over 3 runs.
5
Conclusion and Future Directions
We have introduced the dithered Gaussian mechanism, an alternative to previous discrete noise mechanisms, which protects against floating-point vulnerabilities without requiring separate privacy accounting. Instead, it directly inherits the privacy guarantees of the Gaussian mechanism via postprocessing. We prove that it requires fewer random bits than the discrete Gaussian mechanism and only moderately increases the time needed to sample the noise compared with a naive, non-secure implementation. A promising direction for future work is to generalize the proposed dithered Gaussian mechanism to the distributed differential privacy setting by integrating it with secure aggregation in federated learning. The main obstacle is that the dithered Gaussian mechanism is not additive, which prevents its noise from being straightforwardly decomposed across clients. A separate vulnerability, shared by all of the methods considered here, is exposure to timing attacks. We also note that the mechanism would likely benefit from dedicated hardware support to directly represent vectors in discretized form, rather than converting to a floating point representation, and to speed up the sampling step. Conceivably this could make cryptographically secure randomness available in DP-SGD with a truly negligible performance overhead. Acknowledgements. Rasmus Pagh is supported by a Data Science Distinguished Investigator grant from Novo Nordisk Fonden, and is part of BARC, supported by the VILLUM Foundation grant 54451. Nikita Kalinin is supported in part by the Austrian Science Fund (FWF) [10.55776/COE12]. 10
We thank Andreas V. Welsch Zacchi and Christoffer H. Andersen who independently obtained empirical results on DP-SGD supporting our conclusions as part of their BSc thesis at the University of Copenhagen.
References [1] Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In ACM SIGSAC Conference on Computer and Communications Security, pages 308–318, 2016. [2] Naman Agarwal, Peter Kairouz, and Ziyu Liu. The Skellam mechanism for differentially private federated learning. In Advances in Neural Information Processing Systems (NeurIPS), pages 5052–5064, 2021. [3] Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMahan. cpSGD: communication-efficient and differentially-private distributed SGD. In Advances in Neural Information Processing Systems (NeurIPS), pages 7575–7586, 2018. [4] Joel Daniel Andersson, Rasmus Pagh, Teresa Anna Steiner, and Sahel Torkamani. Count on your elders: Laplace vs. Gaussian noise. In Foundations of Responsible Computing (FORC), volume 329 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:24, Dagstuhl, Germany, 2025. [5] Victor Balcer and Salil Vadhan. Differential privacy on finite computers. In Innovations in Theoretical Computer Science Conference (ITCS), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 43:1–43:21, Dagstuhl, Germany, 2018. [6] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: tight analyses via couplings and divergences. In Advances in Neural Information Processing Systems (NeurIPS), pages 6280–6290, 2018. [7] Ergute Bao, Yizheng Zhu, Xiaokui Xiao, Yin Yang, Beng Chin Ooi, Benjamin Hong Meng Tan, and Khin Mi Mi Aung. Skellam mixture mechanism: a novel approach to federated learning with differential privacy. Proc. VLDB Endow., 15(11):2348–2360, 2022. [8] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: efficient algorithms and tight error bounds. In Symposium on Foundations of Computer Science (FOCS), pages 464–473. IEEE, 2014. [9] Clément L. Canonne, Gautam Kamath, and Thomas Steinke. The discrete Gaussian for differential privacy. In Advances in Neural Information Processing Systems (NeurIPS), 2020. [10] Clément L. Canonne, Francis E. Su, and Salil P. Vadhan. The randomness complexity of differential privacy. In 16th Innovations in Theoretical Computer Science Conference (ITCS), volume 325 of LIPIcs, pages 27:1–27:21, 2025. [11] J. Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143–154, 1979. [12] Wei-Ning Chen, Ayfer Ozgur, and Peter Kairouz. The Poisson binomial mechanism for unbiased federated learning with secure aggregation. In International Conference on Machine Learning (ICML), volume 162 of Proceedings of Machine Learning Research, pages 3490–3506, 2022. [13] Tasos C Christofides and Eutichia Vaggelatou. Bounds for the distance between the distributions of sums of absolutely continuous iid convex-ordered random variables with applications. Journal of applied probability, 46(1):255–271, 2009. [14] Lynn Chua, Badih Ghazi, Charlie Harrison, Ethan Leeman, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. Balls-and-bins sampling for DP-SGD. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 258 of Proceedings of Machine Learning Research, pages 946–954, 2025. [15] Thomas M. Cover and Joy A. Thomas. Elements of information theory. Wiley, 2001. 11
[16] Luc Devroye. Non-uniform random variate generation. Springer, New York, 1986. [17] Zeyu Ding, John Durrell, Daniel Kifer, Prottay Protivash, Guanhong Wang, Yuxin Wang, Yingtai Xiao, and Danfeng Zhang. Avoiding floating-point side channels in the report noisy max with gap mechanism. Journal of Privacy and Confidentiality, 15(3), 2025. [18] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: privacy via distributed noise generation. In Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), volume 4004 of Lecture Notes in Computer Science, pages 486–503. Springer, 2006. [19] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211–407, aug 2014. [20] Shannon Egan. High-speed random number generator co-processors for machine learning and AI acceleration. In NeurIPS 2024 Workshop Machine Learning with New Compute Paradigms, 2024. [21] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: from local to central differential privacy via anonymity. In Symposium on Discrete Algorithms (SODA), pages 2468–2479, 2019. [22] Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In Symposium on Foundations of Computer Science (FOCS), pages 954–964. IEEE, 2021. [23] Vitaly Feldman, Audra McMillan, and Kunal Talwar. Stronger privacy amplification by shuffling for Rényi and approximate differential privacy. In Symposium on Discrete Algorithms (SODA), pages 4966–4981. SIAM, 2023. [24] Vitaly Feldman and Moshe Shenfeld. Privacy amplification by random allocation, 2025. arXiv preprint arXiv:2502.08202. [25] Quan Geng and Pramod Viswanath. The optimal noise-adding mechanism in differential privacy. IEEE Transactions on Information Theory, 62(2):925–951, 2016. [26] Surendra Ghentiyala. Efficient derandomization of differentially private counting queries. In Symposium on Simplicity in Algorithms (SOSA), 2026. [27] Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. Universally utility-maximizing privacy mechanisms. In Symposium on Theory of Computing (STOC), pages 351–360, 2009. [28] Samuel Haney, Damien Desfontaines, Luke Hartman, Ruchit Shrestha, and Michael Hay. Precision-based attacks and interval refining: how to break, then fix, differential privacy on finite computers, 2022. arXiv preprint arXiv:2207.13793. [29] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Symposium on Theory of Computing (STOC), pages 705–714, 2010. [30] Naoise Holohan and Stefano Braghin. Secure random sampling in differential privacy. In European Symposium on Research in Computer Security (ESORICS), volume 12973 of Lecture Notes in Computer Science, pages 523–542. Springer, 2021. [31] Naoise Holohan, Stefano Braghin, Pól Mac Aonghusa, and Killian Levacher. Diffprivlib: the IBM differential privacy library. CoRR, abs/1907.02444, jul 2019. [32] Christina Ilvento. Implementing the exponential mechanism with base-2 differential privacy. In Conference on Computer and Communications Security (CCS), pages 717–742, 2020. [33] Jiankai Jin, Eleanor McMurtry, Benjamin IP Rubinstein, and Olga Ohrimenko. Are we there yet? timing and floating-point attacks on differential privacy systems. In Symposium on Security and Privacy (SP), pages 473–488. IEEE, 2022. 12
[34] Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete Gaussian mechanism for federated learning with secure aggregation. In International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pages 5201–5212. PMLR, 2021. [35] Donald E. Knuth and Andrew C. Yao. The complexity of nonuniform random number generation. In Algorithms and Complexity: New Directions and Recent Results, pages 357–428. Academic Press, 1976. [36] Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using FFT. In Conference on Artificial Intelligence and Statistics (AISTATS), volume 108 of Proceedings of Machine Learning Research, pages 2560–2569, 2020. [37] Christian Janos Lebeda, Matthew Regehr, Gautam Kamath, and Thomas Steinke. Avoiding pitfalls for privacy accounting of subsampled mechanisms under composition. In Conference on Secure and Trustworthy Machine Learning (SaTML), 2025. [38] Cong Ling and Jean-Claude Belfiore. Achieving AWGN channel capacity with lattice Gaussian coding. IEEE Transactions on Information Theory, 60(10):5918–5929, 2014. [39] Ilya Mironov. On significance of the least significant bits for differential privacy. In ACM Conference on Computer and Communications Security (CCS), pages 650–661, 2012. [40] Ilya Mironov. Rényi differential privacy. In IEEE Computer Security Foundations Symposium (CSF), pages 263–275. IEEE, 2017. [41] The OpenDP project. https://opendp.org. [42] Tiberiu Popoviciu. Sur les équations algébriques ayant toutes leurs racines réelles. Mathematica, pages 129–145, 1935. [43] Python Software Foundation. secrets – Generate secure random numbers for managing secrets, 2015. https://docs.python.org/3/library/secrets.html. [44] Jan Schuchardt, Mihail Stoian, Arthur Kosmala, and Stephan Günnemann. Unified mechanismspecific amplification by subsampling and group privacy amplification. In Advances in Neural Information Processing Systems (NeurIPS), 2024. [45] Shuang Song, Kamalika Chaudhuri, and Anand D. Sarwate. Stochastic gradient descent with differentially private updates. In IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 245–248, 2013. [46] VaultGemma Team. VaultGemma: a differentially private Gemma model. arXiv preprint arXiv:2510.15001, 2025. Version 2, 22 Oct 2025. [47] Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, and N. V. Vinodchandran. Replicability in learning: geometric partitions and KKM-Sperner lemma. In Advances in Neural Information Processing Systems (NeurIPS), volume 37, 2024. [48] Shaowei Wang, Yun Peng, Jin Li, Zikai Wen, Zhipeng Li, Shiyu Yu, Di Wang, and Wei Yang. Privacy amplification via shuffling: unified, simplified, and tightened. CoRR, abs/2304.05007, 2023. arXiv preprint arXiv:2304.05007. [49] Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, et al. Opacus: user-friendly differential privacy library in PyTorch, 2021. arXiv preprint arXiv:2109.12298. [50] Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 151 of Proceedings of Machine Learning Research, pages 4782–4817. PMLR, 2022.
13
A
Differential Privacy Basics
In this appendix we recall the standard definitions of differential privacy, see [19] for details and a historical overview. We adopt the standard unbounded (add/remove-one) adjacency model: two datasets X, X ′ ⊆ X are said to be neighbors, written X ∼ X ′ , if one can be obtained from the other by either adding or removing a single element. Formally, X ∼ X′
⇐⇒
| X△X ′ | = 1,
where △ denotes the symmetric difference. This model corresponds to protecting the participation of a single individual, and is the default unless otherwise stated. Definition 2 (Pure and approximate differential privacy). Let ε ≥ 0 and δ ∈ [0, 1). A randomized mechanism M with range Y is (ε, δ)-differentially private if for all neighboring datasets X ∼ X ′ and all measurable S ⊆ Y, Pr[M(X) ∈ S] ≤ eε Pr[M(X ′ ) ∈ S] + δ. When δ = 0 we say that M is ε-differentially private (pure differential privacy). Lemma 5 (Post-processing). If a mechanism M : X∗ → Y is (ε, δ)-differentially private and K is any (possibly randomized) mapping K : Y → Z whose internal randomness is independent of the input dataset X, then the composed mechanism K ◦ M is also (ε, δ)-differentially private. Definition 3 (ℓp -sensitivity). For a function f : X∗ → Rd and p ∈ [1, ∞], the ℓp -sensitivity is ∆p (f ) := sup ∥f (X) − f (X ′ )∥p . X∼X ′
Definition 4 (Laplace mechanism). For λ > 0 and a function f : X∗ → Rd , the Laplace mechanism is defined as M(X) = f (X) + y where yi ∼ Laplace(λ) independently for i = 1, . . . , d. We will use the following sufficient conditions for the Laplace mechanism to satisfy pure and approximate differential privacy (see Andersson et al. [4, Theorem 3] for a proof). Lemma 6. (Privacy of the Laplace mechanism). For ε > 0, if λ ≥ ∆1 (f )/εpthe Laplace mechanism satisfies ε-differential privacy. For ε ∈ (0, 1) and δ ∈ (0, 1/2), if λ ≥ 2 ln(1/δ) ∆2 (f )/ε then the Laplace mechanism satisfies (ε, δ)-differential privacy.
14
B
Sampling Algorithm
Algorithm 2 Approximate Dithered Gaussian Sampling Require: f (X)i ∈ R and γi ∈ [0, 1) for i ∈ [d], parameters ξ > 0, σ > 0, truncation level δ ′ ∈ (0, 1), block size t ≥ 1 Ensure: Samples Z1 , . . . Zd 1: Let zδ ′ satisfy Pr[|Y | > σzδ ′ ] ≤ δ ′ for Y ∼ N (0, σ 2 ) 2: for i = 1, . . . , d do 3: ci ← f (X)i /ξ − γi + 21 4: kimin ← ⌊ci − σzδ′ /ξ⌋, kimax ← ⌈ci + σzδ′ /ξ⌉ 5: end for 6: m ← maxi∈[d] (kimax − kimin + 1) ▷ Determine the truncated sampling range 7: for i = 1, . . . , d do 8: for j = 0, . . . , m − 1 do 9: ki,j ← kimin + j 10: if ki,j ≤ kimax then ξ(ki,j + γi + 12 ) − f (X)i ξ(ki,j + γi − 12 ) − f (X)i 11: Pi,j ← Φ −Φ σ σ 12: else 13: Pi,j ← 0 14: end if 15: end for Pm−1 16: Normalize: Pi,· ← Pi,· / j=0 Pi,j Pj−1 17: Ci,0 ← 0, and Ci,j ← ℓ=0 Pi,ℓ for j = 1, . . . , m 18: end for 19: Initialize active set A ← [d]; for each i, no outcome has yet been assigned 20: while A ̸= ∅ do 21: Generate a block Bi ∈ {0, . . . , 2t − 1} of t random bits for each i ∈ A 22: for each i ∈ A do 23: Let Bi,1 be all blocks generated so far for row i P, r.i. . , Bi,ri−ts 24: Li ← s=1 Bi,s 2 , Hi ← Li + 2−tri 25: if there exists j ∈ {0, . . . , m − 1} such that [Li , Hi ) ⊆ [Ci,j , Ci,j+1 ) then 26: Zi ← ki,j 27: Remove i from A 28: end if 29: end for 30: end while 31: return Z1 , . . . , Zd In this section, we present Algorithm 2 for approximate sampling from the dithered Gaussian distribution (6). We present it in a vectorizable form, allowing for efficient implementation. First, we introduce a small probability δ ′ > 0 for truncating the sampling range, so that the probability of obtaining a sample outside this range is smaller than δ ′ . For each coordinate, we compute the range [kimin , kimax ] and pad it so that each range has a fixed length m. We then compute the probability distribution for each coordinate, denoted by Pi,j . For sampling, we invert the cumulative distribution j−1 P function: namely, we compute the partial sums Ci,j = Pi,l . Then, given a sampled uniform l=0
random variable, we return the index of the interval [Ci,j , Ci,j+1 ) that contains its value. Sampling a true uniform random variable requires an infinite number of bits. Therefore, instead, we sample a finite number ri × t of bits, structured into ri blocks of t bits for efficiency, since sampling one extra bit at a time is impractical. This defines a range in which a true uniform random variable would lie if we continued sampling more bits. Once this range is fully contained in one of the intervals [Ci,j , Ci,j+1 ), we output the corresponding index. We maintain a set of indices A for which the sampled value has not yet been determined; we call this the active set. In practice, we choose the block size so that most values are sampled on the first attempt, and additional bits are sampled only for the remaining, smaller active set. 15
C
Lower Bound
Canonne, Su, and Vadhan study the randomness complexity of differentially private mechanisms for the summation problem, where the input X is a dataset of n vectors in [0, 1]d . In this setting, the function has ℓ1 -sensitivity ∆1 (f ) = d. They prove a lower bound on the amount of randomness required by accurate differentially private mechanisms for this problem ([10, Cor. 4.2]). Specifically, for an (ε, δ)-differentially private mechanism with Hamming adjacency and parameters ε ≤ 1/d and δ ≤ 1/(6d2 ), any mechanism that retains nontrivial accuracy (say β ≤ 1/d and α ≤ n/2 − 1 on inputs of length n) has expected randomness complexity E[H(M(X))] ≥ log2 d − O(1).
(13)
This holds even under bounded differential privacy where the data size n is public information. In this section, we show an improved lower bound for approximate differential privacy by separating the public randomness U from the private randomness needed to ensure differential privacy. We consider the following setting. Given a clipping radius C ∈ N, the function we consider is the identity function f (z) = z defined on Z, where integers z and z ′ are neighboring if and only if |z − z ′ | ≤ C, so that the ℓ1 -sensitivity is C. A mechanism for f implies a mechanism for summation of integers in {0, . . . , C}. We upper bound the private entropy of a mechanism M defined on Z by H(M) := sup EU H(MU (f (z))) , z∈Z
where the expectation is over public randomness U and H(MU (f (z))) is the Shannon entropy of the output distribution of M on input f (z) given U . Theorem 4. There are absolute constants c, c0 > 0 such that for ε ∈ (0, 1) and δ ≤ c0 ε the following holds. Suppose MU : Z → Z is an (ε, δ)-differentially private mechanism under sensitivity C, for 1 every fixed value of public randomness U . If, for some α ∈ N and β ∈ (0, 10 ), for every z ∈ Z it holds that PrU,R [|MU (z) − z| > α] ≤ β (where R is the private randomness) then there exists z ∈ Z such that C EU H(MU (z)) ≥ c . εα The proof proceeds by fixing a suitable value of the public randomness and using a graph-theoretic argument based on component stability and barrier structure to derive a lower bound on the achievable accuracy. Proof. Write H = H(M). We also use the standard group-privacy consequence of (ε, δ)-differential privacy: if two inputs are connected by t neighboring steps, then for every event E, t−1 X Pr[MU (z ′ ) ∈ E] ≥ e−tε Pr[MU (z) ∈ E] − δ ejε (14) j=0
for every fixed value U of the public randomness. We first record a simple consequence of accuracy. For a sufficiently small absolute constant a > 0, no mechanism satisfying the hypotheses can have α < aC/ε. Indeed, let z ′ = z + 2α + 1, so the intervals Iz = [z − α, z + α], Iz′ = [z ′ − α, z ′ + α] are disjoint. Accuracy gives EU Pr[MU (z) ∈ Iz ] ≥ 1−β and EU Pr[MU (z ′ ) ∈ Iz′ ] ≥ 1−β. Since Iz ∩ Iz′ = ∅, the second inequality implies EU Pr[MU (z ′ ) ∈ Iz ] ≤ β. On the other hand, averaging (14) over U and using δ ≤ c0 ε, with a and c0 small enough, gives a constant lower bound larger than β on EU Pr[MU (z ′ ) ∈ Iz ] whenever α < aC/ε, a contradiction. Thus, in the non-vacuous case we may assume α ≥ aC/ε. (15) Fix n and write Qn = {1, . . . , n}. Since the mechanism satisfies the stated error guarantee on every input, EU Pr [|MU (z) − z| > α] ≤ β. z∼Qn
16
Also, by the definition of H, EU Ez∼Qn [H(MU (z))] ≤ H. Markov’s inequality therefore gives a value U ∗ such that Pr [|MU ∗ (z) − z| > α] ≤ 2β,
(16)
Ez∼Qn [H(MU ∗ (z))] ≤ 3H.
(17)
z∼Qn
Let S = {z ∈ Qn : H(MU ∗ (z)) ≥ 1/2}. By (17), |S| ≤ 6Hn. For every z ∈ / S, the output distribution of MU ∗ (z) has an atom mz of probability at least 7/8: otherwise its Shannon entropy would be at least the binary entropy h2 (1/8) > 1/2. Choose a sufficiently small absolute constant b > 0, and set k = max{1, ⌊bC/ε⌋}. ′
′
If z, z ∈ / S and |z − z | ≤ k, then mz = mz′ . To see this, let t = ⌈|z − z ′ |/C⌉. By the choice of k, tε ≤ b + ε, and the additive term in (14) is at most an absolute constant that can be made smaller than 1/4 by choosing c0 small enough. Applying (14) to the event {MU ∗ (·) = mz } gives probability greater than 1/8 under input z ′ . Since z ′ ∈ / S, all atoms other than its atom of mass at least 7/8 have probability at most 1/8, so mz = mz′ . Build a graph G whose vertices are Qn \ S, connecting two vertices when their distance is at most k. Each connected component is an interval in the line Qn , and consecutive components are separated by a run of at least k points of S. Moreover, by the stability just proved, all vertices in a component D share a common modal output mD . For a component D, at most 2α + 1 of its vertices satisfy |z − mD | ≤ α. Thus, if |D| > 4α, then for uniformly random z ∈ D, 2α + 1 7 7 1− ≥ . Pr[|MU ∗ (z) − z| > α] ≥ 8 |D| 20 Together with (16), this implies that the total number of vertices lying in components of size larger than 4α is at most 6βn. Consequently the total size of components of size at most 4α is at least (1 − 6β)n − |S|. On the other hand, the barrier property bounds the number of components by |S|/k + 1. Hence the total size of components of size at most 4α is at most 6Hn |S| 4α + 1 ≤ 4α +1 . k k Combining the last two displays and dividing by n, then letting n → ∞, gives 24αH . k By (15) and the definition of k, the ratio α/k is bounded below by an absolute constant. Since β < 1/10, this implies k C H ≥ c′ ≥ c α εα for absolute constants c′ , c > 0. This is the desired lower bound. 1 − 6β ≤ 6H +
D
Properties of the Dithered Gaussian Mechanism
This section contains full proofs of properties of the dithered Gaussian mechanism that were sketched in the main body. Lemma 1. Over the randomness of the shift γi and index Zi , M(f (X))i is identically distributed to f (X)i + yi + ui , where ui ∼ Uniform(−ξ/2, ξ/2) and yi ∼ N (0, σ 2 ) are independent. 17
(7)
Proof. The dithered Gaussian mechanism is defined in (5): 1 f (X)i + yi − γi + + γi , (18) M(f (X))i = ξ ξ 2 where γi = (ia + b) mod 1 with a, b ∼ Uniform([0, 1)2 ) independent of X and y. Consider the value
ui 1 := ti − γi + − ti + γi , ξ 2
ti =
where
f (X)i + yi . ξ
(19)
We will show that uξi is uniformly distributed on [−1/2, 1/2] independently of ti , which is sufficient for the proof of the lemma. Let {·} denote the fractional part. Then 1 1 1 ti − γi + = ti − γi + + ti − γ i + . 2 2 2
(20)
1 1 ui = − ti − γ i + . ξ 2 2
(21)
Therefore,
It remains to show that the fractional part is uniformly distributed on [0, 1) and independent of ti . Fix arbitrary values of ti and a. Conditional on these values, the quantity ti − ia + 1/2 is a constant, while b remains uniform on [0, 1). Hence, for any measurable set U ⊆ [0, 1), Pr
ti − ia +
1 −b 2
∈ U ti , a = λ(U),
(22)
where λ denotes Lebesgue measure on [0, 1). This follows because the map b 7→
1 ti − ia + − b 2
(23)
is a measure-preserving shift and reflection modulo 1. Therefore, ti − γi +
1 2
∼ Uniform([0, 1))
(24)
independently of ti . Proposition 2. Let Gσ ∼ N (0, σ 2 ), and let Uξ ∼ Uniform(−ξ/2, ξ/2) be independent of Gσ . Then 2 ξ dTV (Gσ + Uξ , Gσ ) ≤ 0.0202 . (11) σ Proof. The proof is based on Lemma 2 of [13], together with an explicit computation of ∥ϕ′′ ∥1 and substitution of the variance of the uniform random variable. For completeness, we provide the full proof here. By scaling all random variables by 1/σ, it suffices to compare the standard Gaussian G ∼ N (0, 1) to G + Ur , where Ur ∼ Uniform(−r/2, r/2) and r = ξ/σ. The density of G + Ur is Z 1 x+r/2 Φ(x + r/2) − Φ(x − r/2) qr (x) = ϕ(t) dt = . r x−r/2 r Thus dTV (Gσ + Uξ , Gσ ) =
1 2
Z ∞
Φ(x + r/2) − Φ(x − r/2) − ϕ(x) dx, r −∞ 18
since total variation distance between two distributions with densities is one half of the L1 -distance between the densities. We next prove the bound. Using E[Ur ] = 0, we can write qr (x) − ϕ(x) = E[ϕ(x + Ur ) − ϕ(x) − Ur ϕ′ (x)] . For a fixed v ∈ [−r/2, r/2], Taylor’s formula with integral remainder gives Z v ϕ(x + v) − ϕ(x) − vϕ′ (x) = (v − s)ϕ′′ (x + s) ds. 0
Taking L1 -norms and using translation-invariance of the Lebesgue integral, ∥ϕ(· + v) − ϕ − vϕ′ ∥1 ≤
v 2 ′′ ∥ϕ ∥1 . 2
(25)
Therefore ∥qr − ϕ∥1 ≤
E[Ur2 ] ′′ r2 ′′ ∥ϕ ∥1 = ∥ϕ ∥1 . 2 24
Since ϕ′′ (x) = (x2 − 1)ϕ(x), we have Z ∞ ′′ ∥ϕ ∥1 = |x2 − 1|ϕ(x) dx −∞ Z 1
=2
(1 − x2 )ϕ(x) dx = 4ϕ(1),
(26)
−1
where the last equality follows from (xϕ(x))′ = (1 − x2 )ϕ(x). Thus dTV (G + Ur , G) =
ϕ(1) 2 1 ∥qr − ϕ∥1 ≤ r , 2 12
and ϕ(1)/12 < 0.0202, which gives (11). We remark that the constant ϕ(1)/12 is sharp for a bound of this form. Before proving Lemma 3, we show an auxiliary upper bound on the entropy of an integer-valued random variable in terms of its variance. Lemma 7 (Discrete entropy bound [15, Theorem 9.7.1]). Let Z be an integer-valued random variable with finite variance. Then its Shannon binary entropy satisfies 1 1 . (27) H(Z) ≤ log2 2πe Var(Z) + 2 12 Proof. We provide a more detailed, self-contained proof. Let U ∼ Uniform(−1/2, 1/2] be independent of Z. Then Z + U has density ρ(x) := ρZ+U (x) =
+∞ X
Pr[Z = k]1{k− 12 <x≤k+ 12 } .
(28)
k=−∞
The density ρ is nonnegative and pointwise bounded by maxk Pr[Z = k] ≤ 1. Therefore, if µ denotes the distribution of Z + U , then for every measurable set A, Z µ(A) = ρ(x) dx ≤ λ(A). (29) A
In particular, if λ(A) = 0, then µ(A) = 0. Hence µ is absolutely continuous with respect to the Lebesgue measure λ. Therefore, we can compute the differential entropy of Z + U : 19
Z +∞ h(Z + U ) = −
ρ(x) log2 ρ(x) dx = −∞
=
+∞ X
Z k+ 12 −
k=−∞
k− 12
ρ(x) log2 ρ(x) dx
(30)
Z k+ 21 −
k=−∞ +∞ X
=−
+∞ X
Pr[Z = k] log2 Pr[Z = k] dx
(31)
Pr[Z = k] log2 Pr[Z = k] = H(Z).
(32)
k− 12
k=−∞
Thus, the differential entropy of Z + U coincides with the discrete entropy of Z. Since the Gaussian distribution maximizes differential entropy among all absolutely continuous random variables with fixed variance, 1 h(Z + U ) ≤ log2 (2πe Var(Z + U )) . (33) 2 Using independence of Z and U , Var(Z + U ) = Var(Z) + Var(U ) = Var(Z) +
1 . 12
(34)
Combining the above identities yields H(Z) ≤
1 1 log2 2πe Var(Z) + , 2 12
(35)
which completes the proof. Lemma 3. The worst-case private binary entropy of the dithered Gaussian mechanism is bounded by " #! 2 σ 1 1 d + + . (12) H(Z | γ) ≤ log2 2πe 2 ξ 2 12
Proof. Recall from (6) that, conditionally on γi and f (X)i , the distribution of Zi is given by ξ 1 f (X)i ξ 1 f (X)i Pr[Zi = k] = Φ k + γi + − −Φ k + γi − − . σ 2 ξ σ 2 ξ
(36)
Given the grid γ, the random variables Zi are independent. Therefore, H(Z | γ) =
d X
H(Zi | γ).
(37)
i=1
By Lemma 7, for each coordinate we have 1 1 H(Zi | γ) ≤ log2 2πe Var(Zi | γ) + . 2 12
(38)
2 i − γi , σξ2 . Then Zi can be obtained by rounding Now consider the random variable Yi ∼ N f (X) ξ Yi to the nearest integer, since 1 1 Pr k − ≤ Yi ≤ k + = Pr[Zi = k]. (39) 2 2 Using the Cauchy-Schwarz inequality, we get Var(Zi | γi ) = Var (Yi + (Zi − Yi ) | γi ) ≤
p
20
Var(Yi | γi ) +
2 p Var(Zi − Yi | γi ) .
(40)
Since Var(Yi | γi ) = σ 2 /ξ 2 and |Zi − Yi | ≤ 1/2, Popoviciu’s inequality [42] gives Var(Zi − Yi | γi ) ≤
1 . 4
Hence Var(Zi | γi ) ≤
σ 1 + ξ 2
(41)
2 .
(42)
Combining the above inequalities, we obtain d H(Z | γ) ≤ log2 2
" 2πe
σ 1 + ξ 2
2
1 + 12
#! .
(43)
The right-hand side does not depend on γ, so taking expectation over γ does not change the bound.
E
Dithered Laplace Mechanism
The proposed scheme can be generalized to other types of additive-noise mechanisms. In this section, we discuss the implications of our dithering scheme for the Laplace mechanism. In a recent paper, Canonne, Su, and Vadhan [10] showed that the randomness complexity of differentially private mechanisms for vector summation can be drastically reduced. When the statistic f has ℓ1 sensitivity ∆1 (f ), there exists an ε-differentially private mechanism that for α = Ω(∆1 (f ) log(d)/ε) is (α, poly(1/d))-accurate with expected randomness complexity Corollary 8. Let ε > 0, β ∈ (0, 1), and suppose the accuracy target α satisfies ∆1 (f ) log(2d/β) ε for a sufficiently large universal constant C0 . Then there exists an ε-differentially private mechanism M that is (α, β)-accurate and whose expected randomness complexity is αε d ∆1 (f ) · log(d) · log + log d . R(M) = O αε ∆1 (f ) log d α ≥ C0
Choosing error parameter α = d2 log2 (d)/ε minimizes randomness complexity to O(log d) bits. At the other end of the trade-off, error α = O(∆1 (f ) log(d)/ε) is asymptotically optimal [29, 25] among ε-differentially private algorithms for β = 1/poly(d) and results in randomness complexity E[H(M(f (X)))] = O(d) bits. While the mechanism of [10] is not computationally efficient, recent work by Ghentiyala [26] provides a computationally efficient alternative (with slightly higher randomness complexity). By replacing the cumulative distribution function in the dithered Gaussian algorithm with that of the Laplace distribution with parameter λ (which controls the privacy level), we obtain the dithered Laplace mechanism; see Algorithm 3. On the upper bound side we show an improvement over the bound of Canonne, Su, and Vadhan [10] in the following theorem. Theorem 9. Suppose f : X∗ → Rd has sensitivity ∆1 (f ). For every ε > 0, β ∈ (0, 1), and α>
2∆1 (f ) log(d/β) , ε
there exists a random variable U and mechanisms MU : X∗ → Rd , defined by post-processing the Laplace mechanism on f (X), that are ε-differentially private for every fixed value of U . Moreover, MU (f (X)) is an (α, β)-accurate approximation of f (X), and its expected private randomness complexity satisfies d ∆1 (f ) αε EU H(MU (f (X))) = O log . αε ∆1 (f ) Compared with Corollary 8, our bound removes the additive log(d) term and improves the leading term by a factor of log(d). For error tolerance α = ω(d∆1 (f ) log(d)/ε), the private randomness com plexity becomes EU H(MU (f (X))) = o(1) independent of X. That is, the mechanism requires 21
Algorithm 3 Dithered Laplace Mechanism Require: Function value f (X) ∈ Rd , parameters ξ > 0, λ > 0 1: Sample public randomness (a, b) ∼ Uniform([0, 1)2 ) 2: for i = 1, . . . , d do 3: γi ← (a · i + b) mod 1 4: Sample an integer Zi ∈ Z such that, for every k ∈ Z, 1 1 Pr[Zi = k] = Fλ ξ k + γi + − f (X)i − Fλ ξ k + γi − − f (X)i , 2 2 (1 et/λ , t < 0, where Fλ (t) = 2 1 −t/λ 1 − 2e , t ≥ 0, 5: M(f (X))i ← ξ(Zi + γi ) 6: end for 7: return M(f (X))
only a negligible amount of fresh, private randomness to run. For error α = Θ(∆1 (f ) log(d/β)/ε), matching the ℓ∞ -error of the standard Laplace mechanism, the private randomness complexity is EU H(MU (f (X))) = O(d log log(d)/ log d) which is o(d). The mechanism’s public randomness U can be sampled using O(log(d)) random bits with high probability, matching the lower bound (13) on total randomness. We prove Theorem 9, together with a bound on public randomness complexity, in the following lemma. Lemma 10. Let f : X∗ → Rd have ℓ1 -sensitivity ∆1 (f ). Consider the dithered Laplace mechanism M defined in Algorithm 3 with parameters ξ > 0, λ > 0, and public randomness U = (a, b). Fix β ∈ (0, 1). The mechanism satisfies: (a) Pure differential privacy: For every choice of ε > 0, if λ = ∆1 (f )/ε, then M is εdifferentially private and (ξ, β)-accurate with ξ = 2 ∆1 (f ) log(d/β)/ε. (b) Private randomness complexity: The mechanism has expected private entropy dλ ξ EU H(MU (f (X))) = O log . ξ λ (c) Public randomness complexity: If relaxed to output a special value ⊥ with probability at most β, the mechanism can be implemented using O(log(d/β)) bits of public randomness. (d) Distributional properties: If relaxed to use an unbounded number of public random bits, the mechanism can be implemented such that it uses O(log(d/β)) public random bits with probability 1 − β and so that • it is unbiased, E[M(f (X))] = f (X), and • its coordinates are pairwise independent, Cov(M(f (X))i , M(f (X))j ) = 0 for all i ̸= j. Proof. We split the proof in five parts, covering privacy, error, private randomness complexity, public randomness complexity, and distributional properties, respectively. Privacy. Conceptually the mechanism ensures ε-differential privacy by adding independent Laplace noise y ∼ Laplace(∆1 (f )/ε)d to the value f (X). The ℓ1 sensitivity of f is ∆1 (f ), so Laplace noise with scale λ = ∆1 (f )/ε ensures the required privacy guarantee for f (X) + y. The subsequent rounding step maps the noisy result to the nearest point on an ξ-spaced grid shifted by the public offsets ξ γi with γi = (ai + b) mod 1 and (a, b) ∼ Uniform([0, 1)2 ). The public randomness (a, b) is independent of the data, so post-processing preserves privacy for every fixed choice of (a, b). 22
Error bound. As for the error incurred by the mechanism we note that ∥M(f (X)) − f (X)∥∞ ≤ ∥y∥∞ + ξ/2, since the error in each coordinate is bounded by the sum of the perturbation given by y and the rounding to the nearest grid point which changes the value by at most ξ/2. By a union bound over the coordinates, the probability that the noise exceeds ξ/2 is: ξ/2 , Pr[∥y∥∞ > ξ/2] ≤ d exp − λ which is less than β when ξ ≥ 2λ log(d/β). Thus, with probability at least 1 − β the total error is bounded by ξ. Substituting λ = ∆1 (f )/ϵ completes the computation. Private randomness complexity. Fix an arbitrary shift vector γ ∈ Rd and condition on γ throughout this part; we only use its distribution at the end. For a given input z = f (X), define the (deterministic) baseline output k j z − γ + 12 + γ , Mγ,0 (z) := ξ · ξ obtained by setting the noise to zero. Let Y = (Y1 , . . . , Yd ) ∼ Laplace(λ)d . The private entropy for this input and shift is H(Mγ,Y (z)), where γ is the public randomness. Since the coordinates of Y are independent and rounding is coordinate-wise, Mγ,Y (z) is a deterministic function of independent integer “step counters” Ki ∈ Z defined by Mγ,Y (z)i = Mγ,0 (z)i + Ki ξ. Hence H(Mγ,Y (z)) ≤ H(K1 , . . . , Kd | γ, z) =
d X
H(Ki | γ, z),
(44)
i=1
where the last equality uses independence of Y . For i ∈ [d] let τi = τi (γ, z) ∈ [0, ξ/2] be the distance from zi to the nearest boundary of the randomly shifted grid on the ith coordinate. That is, τi := min{|zi − ξ(k + γi + 1/2)|}. k∈Z
For p0,i (γ, z) := 1 − e−τi /λ we have the following lower bound on the probability of Ki = 0: Pr[ Ki = 0 | γ, z ] ≥ Pr[ |Yi | < τi ] = p0,i (γ, z). For k ≥ 1, crossing k grid boundaries requires |Yi | ≥ τi + (k − 1)ξ, so the one-sided tail satisfies Pr[ |Ki | ≥ k | γ, z ] ≤ e−(τi +(k−1)ξ)/λ = e−τi /λ q k−1 , where q := e−ξ/λ . Thus |Ki | is stochastically dominated by a geometric distribution on {1, 2, . . .} with ratio q, and the signed tail {Ki = ±k : k ≥ 1} by a two-sided geometric (discrete Laplace) with the same ratio. Let q h2 be the binary entropy function, and let Hgeo (q) := − log2 (1 − q) − 1−q log2 q be the entropy of a geometric (1 − q) distribution on {1, 2, . . .}. Encoding first the event {Ki = 0} and then the signed magnitude gives H(Ki | γ, z) ≤ h2 p0,i (γ, z) + 1 − p0,i (γ, z) 1 + Hgeo (q) . (45) Combining (45) over i with (44) yields a per-input, per-shift entropy bound. Averaging over the shift. In our implementation the public shift is per-coordinate: ξ γi with γi = (ai + b) mod 1 and (a, b) ∼ Uniform([0, 1)2 ). For each fixed input z and coordinate i, the marginal γi ∼ Uniform([0, 1)) is independent of Yi , so the remainder (zi − ξγi )/ξ mod 1 is uniform on [0, 1). Consequently, the distance τi (γ, z) from zi to the nearest half-integer boundary is uniform on [0, ξ/2]. Hence 2λ p0 := Eγ [ p0,i (γ, z) ] = ET ∼Uniform([0,ξ/2]) [ 1 − e−T /λ ] = 1 − 1 − e−ξ/(2λ) , ξ independent of i and z. By concavity of h2 and linearity of expectation, Eγ H(Ki | γ, z) ≤ h2 (p0 ) + (1 − p0 ) 1 + Hgeo (q) , 23
q = e−ξ/λ .
(46)
Finally, h i EU H(MU (z)) ≤ d h2 (p0 ) + (1 − p0 ) 1 + Hgeo (q) ,
(47)
−ξ/(2λ) with p0 = 1 − 2λ ) and q = e−ξ/λ . Combining the above, we obtain an explicit ξ (1 − e
asymptotic bound on the expected private entropy. Under the accuracy condition ξ ≥ 2λ log(d/β) −ξ/λ established above (implying ξ/λ ≫ 1 in the regimes of interest), the geometrice ratio q = e 2λ −ξ/(2λ) satisfies q ≪ 1, and 1 − p0 = ξ 1 + O(e ) . Using h2 (1 − x) ≤ x log2 ( x ) and Hgeo (q) = Θ(q log 1q ) for small q, inequality (47) yields EU [H(MU (z))] ≤ C d ·
λ ξ log2 ξ λ
for some absolute constant C > 0. This establishes the claimed bound in part (b). Public randomness complexity (for part (c)). Fix f (X) and the private noise y. The output changes only when, for some coordinate i ∈ [d], the function γi 7→
f (X)i + yi f (X)i + yi − γi + 12 = − (a · i + b) mod 1 + 12 ξ ξ
crosses an integer. Equivalently, (a, b) ∈ [0, 1)2 lies in a set where (ai + b) mod 1 is within distance η of a (fixed) boundary point ri ∈ [0, 1) determined by f (X)i and yi . For a precision parameter η ∈ (0, 1), let Bη :=
d n o [ (a, b) ∈ [0, 1)2 : dist (ai + b) mod 1, ri ≤ η . i=1
Each set inside the union is the preimage (under the map (a, b) 7→ (ai + b) mod 1) of an interval of length 2η in [0, 1), so its total area in [0, 1)2 is at most 2η. By the union bound, the probability mass of Bη is at most 2d η. Now choose η := β/(2d). Then µ(Bη ) ≤ β. If we quantize a, b to m bits each with 4d2 m = log2 , β then the rounded pair (ã, b̃) satisfies dist (ãi + b̃) mod 1, (ai + b) mod 1 ≤ (i + 1)2−m ≤ η for every i ∈ [d]. Thus, for every (a, b) ∈ / Bη , the rounded pair (ã, b̃) determines the same output as (a, b). Therefore, an implementation that outputs ⊥ whenever (a, b) ∈ Bη uses at most 2m = O(log(d/β)) public bits and triggers ⊥ with probability at most β. This proves part (c). Public randomness complexity and distributional properties (for part (d)). If we allow unbounded public randomness, we can reveal the bits of (a, b) incrementally until (a, b) ∈ / Bη is certified; with probability at least 1 − β this occurs by m = ⌈log2 (4d2 /β)⌉ bits per parameter, so with probability 1 − β the public randomness used is O(log(d/β)) bits (and on the rare event we reveal more bits). Since (a, b) are uniform on [0, 1)2 , the induced shifts γi = (ai + b) mod 1 satisfy: (i) for each i, γi ∼ Uniform([0, 1)); and (ii) for i ̸= j, the pair (γi , γj ) is uniform on [0, 1)2 . This pairwise independence property is a variant of classical constructions of pairwise independent hash functions [11], see Lemma 11 in Appendix F for a proof. Consequently, with the round-to-nearest construction, the per-coordinate quantization errors Ei = M(f (X))i − (f (X)i + yi ) are pairwise independent and uniform on [−ξ/2, ξ/2], independent of (f (X), y), and in particular have mean zero. This proves part (d).
F
Pairwise Independence of Affine Shifts
We now show the pairwise independence of the shift values γ in the dithered rounding scheme. The proof is analogous to Carter and Wegman’s classical proof of pairwise independence of random linear functions over finite fields [11]; we include it for completeness. 24
Lemma 11. Let a, b ∼ Uniform([0, 1)) be independent, and for each integer t define γt := (at + b) mod 1 ∈ [0, 1). Then for every t we have γt ∼ Uniform([0, 1)), and for distinct integers t ̸= s the pair (γt , γs ) is uniform on [0, 1)2 . In particular, γt and γs are (pairwise) independent. Proof. We work on the unit interval [0, 1) with addition taken modulo 1. Write {x} for the fractional part of a real x. Throughout, a, b are independent and uniform on [0, 1). Uniform marginal. Fix an integer t. For any measurable set I ⊆ [0, 1) and any fixed a ∈ [0, 1), Pr γt ∈ I a = Pr {ta + b} ∈ I = Pr b ∈ I − {ta} = |I|, b
b
b
since b 7→ {b + c} is a shift on the circle and preserves the total length of sets in [0, 1). Averaging over a gives Pr[γt ∈ I] = |I|, i.e., γt ∼ Unif[0, 1). Pairwise independence. Let t ̸= s be integers, and let I, J ⊆ [0, 1) be measurable. We show Pr γt ∈ I, γs ∈ J = |I| |J|. Condition on a. For fixed a, using b uniform and the shift argument as above, Pr γt ∈ I, γs ∈ J a = Pr frac(b + ta) ∈ I and frac(b + sa) ∈ J b
b
= (I − frac(ta)) ∩ (J − frac(sa)) . Set δ := frac((t − s)a) ∈ [0, 1) and note that (I − frac(ta)) ∩ (J − frac(sa)) = (J) ∩ (I − δ) up to a common shift, hence the length above equals ϕ(δ) := | J ∩ (I − δ) |. Therefore Pr γt ∈ I, γs ∈ J = Ea ϕ({(t − s)a}) . We claim that {(t − s)a} is uniform on [0, 1) when a is uniform (for any nonzero integer t − s). Indeed, partition [0, 1) into |t − s| intervals of length 1/|t − s|; multiplication by |t − s| maps each interval linearly onto [0, 1), so for any measurable B ⊆ [0, 1) the preimage {a : {(t − s)a} ∈ B} has size |B|. Hence {(t − s)a} ∼ Unif[0, 1). It remains to compute the average of ϕ(δ) over uniform δ. By averaging over all possible shifts and using that translating a set within [0,1) does not change its total length, Z 1 Z 1Z 1 Z 1 Z 1 ϕ(δ) dδ = 1J (x) 1I (x+δ) dx dδ = 1J (x) 1I (x+δ) dδ dx = |J|·|I|. 0
0
0
0
0
Therefore Ea [ϕ({(t − s)a})] = |I| |J|, and the desired equality follows. Since this holds for all measurable I, J, the pair (γt , γs ) is uniform on [0, 1)2 , and in particular γt and γs are independent.
25