Pith. sign in

REVIEW 3 major objections 8 minor 51 references

Reviewed by Pith at T0; open to challenge.

T0 means a machine referee read the full paper against a public rubric. The mark states how deep the mechanical check went, never who wrote it. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · glm-5.2

Rounding Gaussian Noise to a Grid Cuts Private Randomness to a Constant

2026-07-08 09:50 UTC pith:UNKUATXT

load-bearing objection Core idea is genuinely new and the theory for the idealized mechanism is sound; the gap between the idealized sampler and the practical Algorithm 2 is real but addressable. the 3 major comments →

arxiv 2607.06320 v1 pith:UNKUATXT submitted 2026-07-07 cs.CR cs.LG

Dithered Gaussian Mechanism for Randomness-Efficient Differential Privacy

Nikita P. Kalinin , Rasmus Pagh This is my paper
classification cs.CR cs.LG
keywords mechanismgaussianprivacynoiserandomnessachievedcryptographicallydifferential
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The dithered Gaussian mechanism is a method for releasing differentially private statistics that produces discrete outputs while inheriting the privacy guarantees of the continuous Gaussian mechanism. The core idea is to take the output of the standard Gaussian mechanism—adding Gaussian noise to a sensitive value—and round it to a randomly shifted grid. Because this rounding is a post-processing step applied after the noise has already been added, the privacy guarantee carries over automatically, with no need for a separate privacy analysis. The random grid shift (the dither) is generated from public randomness and can be revealed to an adversary without compromising privacy. The key insight is that, conditioned on the public dither, the discrete output can be sampled directly from an explicit distribution over grid points, rather than first sampling a continuous Gaussian value and then rounding it. This direct sampling requires only a constant number of private random bits per coordinate, independent of the noise scale sigma, because the grid spacing can be chosen comparable to the noise scale without significantly distorting the output distribution. The paper proves an upper bound on the private entropy per coordinate and a matching lower bound showing that the ratio of the privacy noise scale to the accuracy scale governs the minimum private randomness required. Applied to differentially private stochastic gradient descent, the mechanism provides cryptographically secure noise generation with roughly 20-30% runtime overhead compared to standard implementations, while eliminating floating-point vulnerabilities that arise when continuous noise is naively discretized by a computer's floating-point representation.

Core claim

The central object is the dithered Gaussian mechanism, defined by adding Gaussian noise to a sensitive value, adding a public random offset, rounding to a grid, and then subtracting the offset. The mechanism's discrete output distribution, conditioned on the public dither, can be written in closed form as a difference of Gaussian cumulative distribution function values, enabling direct sampling from the discrete distribution without generating intermediate continuous Gaussian noise. This yields a private entropy bound of (d/2) log_2(2*pi*e*((sigma/xi + 1/2)^2 + 1/12)) bits, which is constant per coordinate when the grid spacing xi is chosen comparable to the noise scale sigma. The privacyguа

What carries the argument

The mechanism works by observing that the event of rounding the Gaussian-perturbed value to a particular grid point k is equivalent to the Gaussian noise falling in a specific interval, whose probability is a difference of Gaussian CDF values. This gives an explicit discrete distribution that can be sampled directly. The public dither gamma_i = (a*i + b) mod 1, generated from just two uniform random numbers a and b, provides pairwise-independent per-coordinate grid shifts. The entropy bound uses the fact that the discrete output Z_i can be viewed as a rounded version of a Gaussian random variable, and applies a discrete maximum entropy bound (Lemma 7) combined with a variance bound obtained

Load-bearing premise

The privacy guarantee rests on the claim that the discrete output can be sampled exactly from the distribution defined by differences of Gaussian CDF values. In practice, the paper uses an approximate sampler that truncates the sampling range with small probability delta', and if the truncation or precision of this approximate sampler introduces errors that depend on the sensitive input, the clean post-processing argument that inherits Gaussian privacy may not fully apply to,

What would settle it

If the approximate sampling procedure (Algorithm 2) introduces distributional errors that depend on f(X) in a way that cannot be bounded by the truncation parameter delta', the privacy guarantee could be compromised. A concrete test would be to construct neighboring datasets X and X' where the truncation boundaries fall differently relative to f(X) and f(X'), and verify whether the output distributions satisfy the (epsilon, delta)-differential privacy inequality.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The dithered approach can serve as a drop-in replacement for the Gaussian mechanism in any system that already uses Gaussian-based privacy accounting, including composition theorems and subsampling amplification, without requiring re-derivation of privacy bounds.
  • The separation of public and private randomness suggests a practical architecture where fast public pseudorandom generators supply the dither while slower cryptographic generators handle only the low-entropy private sampling step, reducing the cost of cryptographically secure noise in large-scale private machine learning.
  • The same dithering construction extends to the Laplace mechanism, where the paper shows improved randomness complexity bounds over prior work, suggesting the technique is broadly applicable to additive-noise privacy mechanisms beyond the Gaussian case.
  • The lower bound (Theorem 4) establishes that the ratio of noise scale to accuracy scale fundamentally governs private randomness requirements, providing a benchmark against which any future randomness-efficient private mechanism can be measured.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 8 minor

Summary. The paper introduces the 'dithered Gaussian mechanism,' a method for differential privacy that discretizes the output of the Gaussian mechanism rather than the noise distribution. The key idea is that rounding a Gaussian-perturbed value to a randomly shifted grid constitutes post-processing of the standard Gaussian mechanism, thereby directly inheriting its $(ε,δ)$-DP guarantee. The authors show that this approach requires only $O(d)$ private random bits with per-coordinate entropy independent of the noise scale $σ$ (Lemma 3), by separating randomness into a public dither and a private sampling step. A lower bound on private entropy for any DP mechanism is established (Theorem 4). Experiments on CIFAR-10 demonstrate that the mechanism can be used in DP-SGD with cryptographically secure noise generation at modest overhead (~30%) compared to standard implementations.

Significance. The paper addresses a genuine practical gap: the mismatch between idealized continuous Gaussian noise and finite-precision implementations, and the high cost of cryptographically secure randomness at scale. The post-processing argument for privacy is clean and correct for the idealized mechanism (Algorithm 1): since $Z_i$ is a deterministic function of $f(X)_i + y_i$, the output is a post-processing of the Gaussian mechanism (Lemma 5). The entropy bound (Lemma 3) is derived from first principles using a standard discrete entropy inequality (Lemma 7) and a Cauchy-Schwarz variance bound, and is parameter-free in the sense that it depends only on the ratio $σ/ξ$. The lower bound (Theorem 4) provides a matching scale for private entropy. The DP-SGD experiments provide a falsifiable practical benchmark. These are substantive contributions to the theory and practice of differential privacy.

major comments (3)
  1. §3, Algorithm 2 and Appendix B: The central claim that the mechanism 'directly inherits the privacy guarantees of the standard Gaussian mechanism' via post-processing (Lemma 5) is correct for the idealized Algorithm 1 with exact sampling. However, the practical Algorithm 2 used in all experiments (Figure 5) does not sample from the exact distribution in Eq. (6). Algorithm 2 truncates the sampling range to $[k^{min}_i, k^{max}_i]$ where $k^{min}_i = ⌊c_i - σz_{δ'}/ξ⌋$, $k^{max}_i = ⌈c_i + σz_{δ'}/ξ⌉$, and $c_i = f(X)_i/ξ - γ_i + 1/2$. Since $c_i$ depends on $f(X)_i$, the truncation range is data-dependent. The algorithm then renormalizes probabilities within this range (line 16: $P_{i,·} ← P_{i,·} / Σ P_{i,j}$). The renormalization factor $1/(1 - p_{tail})$ depends on $f(X)_i$ because the tail mass $p_{tail}$ outside the range depends on where the range is centered relative to the discret
  2. distribution. This means the output of Algorithm 2 is NOT a deterministic function of $f(X) + y$; it is a different distribution whose relationship to the Gaussian mechanism is not formally established. The paper does not prove that Algorithm 2 satisfies $(ε, δ + δ')$-DP or any variant. The tail probability is bounded by $δ'$ uniformly over $f(X)$ (by construction of $z_{δ'}$), so a standard TV-distance argument would likely yield $(ε, δ + 2δ')$-DP, but this is not stated or proved. Since all experimental results (Figure 5) use Algorithm 2, the practical privacy guarantee for the implemented mechanism is not formally established. This is a load-bearing gap: the paper's motivation emphasizes avoiding floating-point vulnerabilities and inheriting Gaussian privacy, but the actually implemented mechanism lacks a formal privacy proof. The fix is likely straightforward (a TV-distance argument或
  3. a coupling argument showing the approximate sampler is within $δ'$ of the exact sampler), but it must be stated explicitly.
minor comments (8)
  1. Abstract: 'thedithered' — missing space. Also appears in §1 ('thedithered Gaussian mechanism').
  2. §3, Eq. (6): The notation $Pr[Z_i = k]$ uses $f(X)_i$ but the conditioning on $γ_i$ is implicit. Making the conditioning explicit (e.g., $Pr[Z_i = k | γ_i]$) would improve clarity.
  3. §3, Figure 2: The caption references $N(0, 2)$ but the figure labels show $σ=1, 2, 4$. It would help to clarify the relationship between the figure parameters and the caption.
  4. §4, Figure 4: The discrete Gaussian comparison uses discretization levels $h ∈ {0.5/√d, 1/√d, 2/√d}$, but the text in §2 discusses sensitivity increases from discretization. It would be helpful to note whether the RMSE comparison accounts for the sensitivity increase of the discrete Gaussian.
  5. Appendix B, Algorithm 2, line 16: The normalization step uses $P_{i,·}$ notation that is not defined elsewhere. Clarifying that this refers to the vector $(P_{i,0}, ..., P_{i,m-1})$ would help.
  6. §3.1: The comparison to Ghentiyala [26] is useful but the claim that Ghentiyala's variance in random bits is 'much higher' could benefit from quantitative support.
  7. Appendix C, proof of Theorem 4: The constant $a$ is introduced as 'a sufficiently small absolute constant' but its relationship to $c_0$ is not fully specified. A brief remark on the required relative sizes would help reproducibility.
  8. §4: The experiments use batch size 512, which is noted as affecting the overhead. It would strengthen the paper to include at least one data point with a smaller batch size to show how overhead scales, given that the paper cites Egan [20] on overheads at batch size 32.

Simulated Author's Rebuttal

2 responses · 0 unresolved

The referee correctly identifies that Algorithm 2 (the practical implementation) lacks a formal privacy proof, because the data-dependent truncation and renormalization break the direct post-processing argument that applies to the idealized Algorithm 1. We agree this is a load-bearing gap and will add a formal proof. The fix is indeed a TV-distance argument: per coordinate, the truncated-and-renormalized distribution is within δ' in TV distance of the exact distribution (since the tail mass is at most δ' by construction), giving an overall (ε, δ + d·δ')-DP guarantee for Algorithm 2. We will state and prove this explicitly in the revision.

read point-by-point responses

  1. Referee: Algorithm 2 truncates the sampling range data-dependently and renormalizes, so its output is NOT a deterministic function of f(X)+y. The relationship to the Gaussian mechanism is not formally established. The paper does not prove Algorithm 2 satisfies (ε, δ+δ')-DP or any variant. Since all experiments use Algorithm 2, the practical privacy guarantee is not formally established.

    Authors: The referee is correct on all counts. Algorithm 2's truncation range depends on c_i = f(X)_i/ξ - γ_i + 1/2, which depends on the data, and the renormalization on line 16 changes the distribution so that the output is no longer a deterministic post-processing of f(X) + y. The post-processing argument (Lemma 5) applies only to the idealized Algorithm 1. We will add a formal privacy proof for Algorithm 2 in the revision. revision: yes

  2. Referee: The fix is likely straightforward (a TV-distance argument or coupling argument showing the approximate sampler is within δ' of the exact sampler), but it must be stated explicitly.

    Authors: We agree and will include the following argument explicitly in the revision. For each coordinate i, let P denote the exact distribution of Z_i (from Algorithm 1 / Eq. 6) and let Q denote the truncated-and-renormalized distribution (from Algorithm 2). By construction, the truncation range [k_i^min, k_i^max] is centered at c_i and has half-width σ·z_{δ'}/ξ, so the tail mass p_tail = Pr_{P}[Z_i ∉ [k_i^min, k_i^max]] ≤ δ' uniformly over all f(X)_i (by the choice of z_{δ'}). A direct calculation shows that dTV(P, Q) = p_tail ≤ δ' per coordinate: for k in the range, |P(k) - Q(k)| = P(k)·p_tail/(1-p_tail), and for k outside the range, |P(k) - Q(k)| = P(k), so dTV(P,Q) = (1/2)[(1-p_tail)·p_tail/(1-p_tail) + p_tail] = p_tail. Since the d coordinates are independent, the TV distance between the joint distributions is at most d·δ' (by a standard coupling/union bound). By the standard result that if P satisfies (ε,δ)-DP and dTV(P,Q) ≤ η then Q satisfies (ε, δ+η)-DP, Algorithm 2 satisfies (ε, δ + d·δ')-DP. In the experiments, δ' can be set to δ/(2d) (or smaller) so that the additional privacy loss d·δ' is at most δ/2, which is negligible relative to the target δ. We will state this bound as a theorem, verify that the experimental parameters satisfy it, and clarify in the experimental section that the reported privacy budgets account for this additional term. We thank the referee for identifying this gap. revision: yes

Circularity Check

0 steps flagged

No significant circularity found; derivation is self-contained using standard tools.

full rationale

The paper's central privacy claim follows from the standard post-processing lemma (Lemma 5) applied to the Gaussian mechanism: M(f(X)) is a deterministic function of f(X)+y, so it inherits (ε,δ)-DP. This is a textbook argument, not circular. The entropy bound (Lemma 3) is derived from first principles: it applies the discrete entropy inequality (Lemma 7, attributed to Cover & Thomas [15]) combined with variance bounds via Cauchy-Schwarz and Popoviciu's inequality — no fitted parameters are renamed as predictions. The lower bound (Theorem 4) is proved independently via a graph-theoretic argument. The TV-distance bound (Proposition 2) uses an external result [13]. The noise distribution characterization (Lemma 1) is proved directly. The only self-citation is to [4] (Andersson, Pagh, Steiner, Torkamani) for the privacy of the Laplace mechanism (Lemma 6), which is a standard result and not load-bearing for the paper's central claims. The gap between the idealized Algorithm 1 (exact sampling, clean post-processing argument) and the approximate Algorithm 2 (truncation-based, used in experiments) is a correctness/completeness concern, not a circularity issue — the paper is transparent that Algorithm 2's formal privacy guarantee is not established. No step in the derivation chain reduces to its own inputs by construction.

Axiom & Free-Parameter Ledger

4 free parameters · 4 axioms · 0 invented entities

The paper introduces no new mathematical objects beyond the mechanism itself. The dither γ, the grid spacing ξ, and the discrete output Z are all defined in terms of standard constructs (Gaussian noise, uniform random variables, rounding). The mechanism is a composition of known operations. The key innovation is the observation that this composition inherits Gaussian privacy and has low private entropy.

free parameters (4)
  • ξ (grid spacing) = chosen as σ/2, σ, or 2σ in experiments
    Controls the trade-off between discretization error and entropy. Not fitted to data but selected by the practitioner; the paper recommends ξ ≈ σ.
  • σ (noise scale) = determined by privacy budget (ε, δ)
    Standard Gaussian mechanism parameter; not a free parameter of this paper's construction per se, but required as input.
  • δ' (truncation level in Algorithm 2) = not specified numerically
    Controls the tail truncation probability in the approximate sampler. Affects the gap between theoretical exact sampling and practical implementation.
  • t (block size in Algorithm 2) = not specified numerically
    Controls how many random bits are sampled per round in the arithmetic coding scheme. An implementation parameter.
axioms (4)
  • standard math Post-processing preserves differential privacy (Lemma 5)
    Standard result in DP theory; invoked in Section 3 to establish that the dithered Gaussian mechanism inherits Gaussian privacy.
  • standard math The standard Gaussian mechanism with noise scale σ satisfies (ε,δ)-DP for ℓ2-sensitivity Δ2(f)
    Classical result; the dithered mechanism is defined as post-processing of this mechanism.
  • standard math Shannon entropy bounds the expected number of random bits for sampling (up to additive constant)
    Invoked in Section 2 (Randomness complexity) following Canonne-Su-Vadhan [10]; links the entropy bound (Lemma 3) to randomness complexity.
  • ad hoc to paper The approximate sampling procedure (Algorithm 2) with truncation level δ' preserves the (ε,δ)-DP guarantee
    The paper proves privacy for exact sampling (Section 3) but uses approximate sampling (Algorithm 2, Appendix B) in practice. The formal connection between δ' and the privacy guarantee δ is not explicitly proved; the paper states the truncation probability is δ' but does not formally show it translates to a δ'-addition to the privacy failure probability.

pith-pipeline@v1.1.0-glm · 26463 in / 3077 out tokens · 625078 ms · 2026-07-08T09:50:06.627046+00:00 · methodology

0 comments
read the original 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.

Figures

Figures reproduced from arXiv: 2607.06320 by Nikita P. Kalinin, Rasmus Pagh.

Figure 1
Figure 1. Figure 1: From a privacy perspective, the dithered Gaussian mechanism can be thought of as mapping [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Density and cumulative distribution function of the noise distribution of the dithered [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The expected and maximum entropy (a) and normalized RMSE of the dithered Gaussian [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Comparison of the dithered and discrete Gaussian mechanisms as a function of the noise [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Comparison of Gaussian and dithered Gaussian mechanisms on CIFAR-10 across privacy [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

51 extracted references · 51 canonical work pages · 4 internal anchors

  1. [1]

    Goodfellow, H

    Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. InACM SIGSAC Conference on Computer and Communications Security, pages 308–318, 2016

    work page 2016

  2. [2]

    The Skellam mechanism for differentially private federated learning

    Naman Agarwal, Peter Kairouz, and Ziyu Liu. The Skellam mechanism for differentially private federated learning. InAdvances in Neural Information Processing Systems (NeurIPS), pages 5052–5064, 2021

    work page 2021

  3. [3]

    cpSGD: communication-efficient and differentially-private distributed SGD

    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

    work page 2018

  4. [4]

    Count on your elders: Laplace vs

    Joel Daniel Andersson, Rasmus Pagh, Teresa Anna Steiner, and Sahel Torkamani. Count on your elders: Laplace vs. Gaussian noise. InFoundations of Responsible Computing (FORC), volume 329 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:24, Dagstuhl, Germany, 2025

    work page 2025

  5. [5]

    Differential privacy on finite computers

    Victor Balcer and Salil Vadhan. Differential privacy on finite computers. InInnovations in Theoretical Computer Science Conference (ITCS), volume 94 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 43:1–43:21, Dagstuhl, Germany, 2018

    work page 2018

  6. [6]

    Privacy amplification by subsampling: tight analyses via couplings and divergences

    Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: tight analyses via couplings and divergences. InAdvances in Neural Information Processing Systems (NeurIPS), pages 6280–6290, 2018

    work page 2018

  7. [7]

    Skellam mixture mechanism: a novel approach to federated learning with differential privacy.Proc

    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

    work page 2022

  8. [8]

    Private empirical risk minimization: efficient algorithms and tight error bounds

    Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: efficient algorithms and tight error bounds. InSymposium on Foundations of Computer Science (FOCS), pages 464–473. IEEE, 2014

    work page 2014

  9. [9]

    Canonne, Gautam Kamath, and Thomas Steinke

    Clément L. Canonne, Gautam Kamath, and Thomas Steinke. The discrete Gaussian for differential privacy. InAdvances in Neural Information Processing Systems (NeurIPS), 2020

    work page 2020

  10. [10]

    Canonne, Francis E

    Clément L. Canonne, Francis E. Su, and Salil P. Vadhan. The randomness complexity of differential privacy. In16th Innovations in Theoretical Computer Science Conference (ITCS), volume 325 ofLIPIcs, pages 27:1–27:21, 2025

    work page 2025

  11. [11]

    Lawrence Carter and Mark N

    J. Lawrence Carter and Mark N. Wegman. Universal classes of hash functions.Journal of Computer and System Sciences, 18(2):143–154, 1979

    work page 1979

  12. [12]

    The Poisson binomial mechanism for unbiased federated learning with secure aggregation

    Wei-Ning Chen, Ayfer Ozgur, and Peter Kairouz. The Poisson binomial mechanism for unbiased federated learning with secure aggregation. InInternational Conference on Machine Learning (ICML), volume 162 ofProceedings of Machine Learning Research, pages 3490–3506, 2022

    work page 2022

  13. [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

    work page 2009

  14. [14]

    Balls-and-bins sampling for DP-SGD

    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

    work page 2025

  15. [15]

    Cover and Joy A

    Thomas M. Cover and Joy A. Thomas.Elements of information theory. Wiley, 2001. 11

    work page 2001

  16. [16]

    Springer, New York, 1986

    Luc Devroye.Non-uniform random variate generation. Springer, New York, 1986

    work page 1986

  17. [17]

    Avoiding floating-point side channels in the report noisy max with gap mechanism.Journal of Privacy and Confidentiality, 15(3), 2025

    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

    work page 2025

  18. [18]

    Our data, ourselves: privacy via distributed noise generation

    Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: privacy via distributed noise generation. InConference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), volume 4004 ofLecture Notes in Computer Science, pages 486–503. Springer, 2006

    work page 2006

  19. [19]

    The algorithmic foundations of differential privacy.Found

    Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy.Found. Trends Theor. Comput. Sci., 9(3-4):211–407, aug 2014

    work page 2014

  20. [20]

    High-speed random number generator co-processors for machine learning and AI acceleration

    Shannon Egan. High-speed random number generator co-processors for machine learning and AI acceleration. InNeurIPS 2024 Workshop Machine Learning with New Compute Paradigms, 2024

    work page 2024

  21. [21]

    Amplification by shuffling: from local to central differential privacy via anonymity

    Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: from local to central differential privacy via anonymity. InSymposium on Discrete Algorithms (SODA), pages 2468–2479, 2019

    work page 2019

  22. [22]

    Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling

    Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. InSymposium on Foundations of Computer Science (FOCS), pages 954–964. IEEE, 2021

    work page 2021

  23. [23]

    Stronger privacy amplification by shuffling for Rényi and approximate differential privacy

    Vitaly Feldman, Audra McMillan, and Kunal Talwar. Stronger privacy amplification by shuffling for Rényi and approximate differential privacy. InSymposium on Discrete Algorithms (SODA), pages 4966–4981. SIAM, 2023

    work page 2023

  24. [24]

    Privacy amplification by random allocation, 2025

    Vitaly Feldman and Moshe Shenfeld. Privacy amplification by random allocation, 2025. arXiv preprint arXiv:2502.08202

    work page arXiv 2025

  25. [25]

    The optimal noise-adding mechanism in differential privacy

    Quan Geng and Pramod Viswanath. The optimal noise-adding mechanism in differential privacy. IEEE Transactions on Information Theory, 62(2):925–951, 2016

    work page 2016

  26. [26]

    Efficient derandomization of differentially private counting queries

    Surendra Ghentiyala. Efficient derandomization of differentially private counting queries. In Symposium on Simplicity in Algorithms (SOSA), 2026

    work page 2026

  27. [27]

    Universally utility-maximizing privacy mechanisms

    Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. Universally utility-maximizing privacy mechanisms. InSymposium on Theory of Computing (STOC), pages 351–360, 2009

    work page 2009

  28. [28]

    Precision-based attacks and interval refining: how to break, then fix, differential privacy on finite computers

    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

    work page internal anchor Pith review Pith/arXiv arXiv 2022

  29. [29]

    On the geometry of differential privacy

    Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. InSymposium on Theory of Computing (STOC), pages 705–714, 2010

    work page 2010

  30. [30]

    Secure random sampling in differential privacy

    Naoise Holohan and Stefano Braghin. Secure random sampling in differential privacy. In European Symposium on Research in Computer Security (ESORICS), volume 12973 ofLecture Notes in Computer Science, pages 523–542. Springer, 2021

    work page 2021

  31. [31]

    Diffprivlib: The IBM Differential Privacy Library

    Naoise Holohan, Stefano Braghin, Pól Mac Aonghusa, and Killian Levacher. Diffprivlib: the IBM differential privacy library.CoRR, abs/1907.02444, jul 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1907

  32. [32]

    Implementing the exponential mechanism with base-2 differential privacy

    Christina Ilvento. Implementing the exponential mechanism with base-2 differential privacy. In Conference on Computer and Communications Security (CCS), pages 717–742, 2020

    work page 2020

  33. [33]

    Are we there yet? timing and floating-point attacks on differential privacy systems

    Jiankai Jin, Eleanor McMurtry, Benjamin IP Rubinstein, and Olga Ohrimenko. Are we there yet? timing and floating-point attacks on differential privacy systems. InSymposium on Security and Privacy (SP), pages 473–488. IEEE, 2022. 12

    work page 2022

  34. [34]

    The distributed discrete Gaussian mechanism for federated learning with secure aggregation

    Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete Gaussian mechanism for federated learning with secure aggregation. InInternational Conference on Machine Learning (ICML), volume 139 ofProceedings of Machine Learning Research, pages 5201–5212. PMLR, 2021

    work page 2021

  35. [35]

    Knuth and Andrew C

    Donald E. Knuth and Andrew C. Yao. The complexity of nonuniform random number generation. InAlgorithms and Complexity: New Directions and Recent Results, pages 357–428. Academic Press, 1976

    work page 1976

  36. [36]

    Computing tight differential privacy guarantees using FFT

    Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using FFT. InConference on Artificial Intelligence and Statistics (AISTATS), volume 108 of Proceedings of Machine Learning Research, pages 2560–2569, 2020

    work page 2020

  37. [37]

    Avoiding pitfalls for privacy accounting of subsampled mechanisms under composition

    Christian Janos Lebeda, Matthew Regehr, Gautam Kamath, and Thomas Steinke. Avoiding pitfalls for privacy accounting of subsampled mechanisms under composition. InConference on Secure and Trustworthy Machine Learning (SaTML), 2025

    work page 2025

  38. [38]

    Achieving AWGN channel capacity with lattice Gaussian coding.IEEE Transactions on Information Theory, 60(10):5918–5929, 2014

    Cong Ling and Jean-Claude Belfiore. Achieving AWGN channel capacity with lattice Gaussian coding.IEEE Transactions on Information Theory, 60(10):5918–5929, 2014

    work page 2014

  39. [39]

    On significance of the least significant bits for differential privacy

    Ilya Mironov. On significance of the least significant bits for differential privacy. InACM Conference on Computer and Communications Security (CCS), pages 650–661, 2012

    work page 2012

  40. [40]

    Rényi differential privacy

    Ilya Mironov. Rényi differential privacy. InIEEE Computer Security Foundations Symposium (CSF), pages 263–275. IEEE, 2017

    work page 2017

  41. [41]

    https://opendp.org

    The OpenDP project. https://opendp.org

    work page

  42. [42]

    Sur les équations algébriques ayant toutes leurs racines réelles.Mathematica, pages 129–145, 1935

    Tiberiu Popoviciu. Sur les équations algébriques ayant toutes leurs racines réelles.Mathematica, pages 129–145, 1935

    work page 1935

  43. [43]

    Python Software Foundation.secrets – Generate secure random numbers for managing secrets,

    work page

  44. [44]

    https://docs.python.org/3/library/secrets.html

    work page

  45. [45]

    Unified mechanism- specific amplification by subsampling and group privacy amplification

    Jan Schuchardt, Mihail Stoian, Arthur Kosmala, and Stephan Günnemann. Unified mechanism- specific amplification by subsampling and group privacy amplification. InAdvances in Neural Information Processing Systems (NeurIPS), 2024

    work page 2024

  46. [46]

    Shuang Song, Kamalika Chaudhuri, and Anand D. Sarwate. Stochastic gradient descent with differentially private updates. InIEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 245–248, 2013

    work page 2013

  47. [47]

    VaultGemma: a differentially private Gemma model.arXiv preprint arXiv:2510.15001, 2025

    VaultGemma Team. VaultGemma: a differentially private Gemma model.arXiv preprint arXiv:2510.15001, 2025. Version 2, 22 Oct 2025

    work page arXiv 2025

  48. [48]

    Pavan, Jamie Radcliffe, and N

    Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, and N. V . Vinodchandran. Replicability in learning: geometric partitions and KKM-Sperner lemma. InAdvances in Neural Information Processing Systems (NeurIPS), volume 37, 2024

    work page 2024

  49. [50]

    arXiv preprint arXiv:2304.05007

    work page internal anchor Pith review Pith/arXiv arXiv

  50. [51]

    Opacus: User-Friendly Differential Privacy Library in PyTorch

    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

    work page internal anchor Pith review Pith/arXiv arXiv 2021

  51. [52]

    step counters

    Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. InInternational Conference on Artificial Intelligence and Statistics (AISTATS), volume 151 ofProceedings of Machine Learning Research, pages 4782–4817. PMLR, 2022. 13 A Differential Privacy Basics In this appendix we recall the standard def...

    work page 2022