- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper proposed a dithered Gaussian mechanism, which is an alternative to the discrete Gaussian mechanism for differential privacy and is randomness-efficient. Separating the needed randomness enables the use of cryptographically secure randomness without substantial performance loss, and empiricaly validation on DP-SGD has been shown.
Critical strengths
The paper is well structured and nicely written. The presentation is clear and the contribution is clear as well and sufficient. The math looks reasonably correct. The empirical evidence on DP-SGD looks comprehensive.
Critical weaknesses
My major concern is the motivation and contribution, especially on how the authors concince me that they improve the randomness complexity. Please refer to the next section "Questions For Authors".
Questions for authors
I do not use AI-tools to review, so it is likely I miss some of the details and have grammar mistakes since I am not a native speaker. If so, please just indicate what I miss or where I am wrong. Thank you.
Some question that I wish the authors can clarify:
- The authors say the drop-in replacement for the Gaussian mechanism is "time-efficient", does this just mean "randomness (required to sample Gaussian noise)-efficient", or a consequence of it? I see, e.g., in table 6, there is a modest runtime overhead; I agree the overhead is modest, but why it is called "time-efficient"? Is it because of comparing to other baselines that I miss?
- The authors said 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", so how much does it change the distribution?
- Is the runtime overhead of about 3% − 7% the only sacrifice by using the authors' method?
- I am a bit confused that, I agree the authors' method should be randomness-efficient, but why in experiments the authors put a lot of effort in measuing the runtime? Are the directly coorelated?
- My background in mainly differential privacy in a theory perspective, and I was not very familiar with the "randomness complexity". The authors motivated the study of the "randomness complexity" by saying, e.g., "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 (VaultGemma Team, 2025)", then can the authors method be applied to significantly help on this scenario?
- Is the runtime overhead due to the dithering or the use of "cryptographically secure randomness" from the Python 'secrets' module? Also, the authors should clarify more on the use of "cryptographically secure randomness" in their method.
3 comments
Thank you for your detailed responses. I appreciate the authors' efforts, and several of my original concerns have been addressed.
I have carefully considered based on the authors' responses and discussions with other reviewers. I still have reservations regarding the overall contribution and practical significance of the proposed method. One thing I concern is the TV guarantee is only for the marginal distribution rather than the joint, and it could be unclear to what extent the proposed method can significantly benefit large-scale models, which was an important motivation.
I also share Reviewer 5fpw's remaining concerns regarding the numerical accuracy assumptions and the lack of fully certified guarantees for the practical implementation.
Considering these remaining concerns, I would prefer to maintain my original score and let AC decide. Thank you.
Thanks for the follow-up. We would like to comment on two aspects.
1. Total variation distance guarantee We would like to emphasize that if the shifts are chosen uniformly at random rather than using pairwise independence, we do get a bound on total variation distance for the whole output vector. Since the shifts can be chosen using cheap, public randomness this is arguably not even at a significant cost in practice, even though the total randomness complexity will increase.
2. Numerical accuracy assumptions Though reducing reliance on guarantees of underlying libraries will be a meaningful improvement of our work, we feel that the discussion so far has overlooked an aspect of the bigger picture:
Existing practical DP-SGD implementations rely on a questionable assumption, namely A0: A standard, fast pseudorandom generator is sufficient to defend against attacks on privacy.
Our work shows that this assumption can be replaced, at low cost, with a much more believable and tested assumption namely A0*: A cryptographically secure pseudorandom generator is sufficient to defend against attacks on privacy. Even under additional assumptions A1-A3 we argue that the guarantees provided are significantly stronger than for past implementations.
Thanks for good questions! We comment on each below.
W1 (motivation and contribution). The discrete Gaussian needs about log2(σΔ~/h)+2 bits per coordinate (equation 4), resulting in 40 bytes in the practical JAX_privacy implementation; the dithered Gaussian needs at most 2.66 bits at ξ=σ independent of σ and d (Lemma 3), allowing us to use only 2 bytes in our PyTorch implementation. The discrepancy in the exact number of random bits is due to computational trade-offs (e.g. sampling a single bit is not cheaper than sampling a single byte of randomness, as calling the random number generator is expensive). We hope that this and our answers to specific questions below address your concern.
Q1 (meaning of “time-efficient”). This is in relation to other methods that avoid floating point vulnerabilities and use cryptographically secure randomness generators. Tables 1-4 show speedups of 2x to 500x. In the context of DP-SGD, this reduces the overhead relative to implementing the Gaussian mechanism with non-secure randomness to 4-7%, while using the discrete Gaussian incurs overheads of 45-220%. We will rephrase to make this more clear.
Q2 (change of distribution). Lemma 1 gives the exact noise distribution for every input. Proposition 2 bounds the total variation distance from Gaussian noise, e.g. 0.02 for ξ=σ, see Figure 2 for the dependency on ξ/σ.
Q3 (what is sacrificed). There are three main sacrifices, all relatively minor: 1) The runtime overhead you note, 2) A slight increase in noise at the same privacy level, e.g. 4% standard deviation for ξ=σ, resulting in a slight degradation in accuracy (Tables 8 and 9), and 3) Noise is not additive across parties, so it cannot directly be combined with secure aggregation in federated settings.
Q4 (runtime). They are related but not the same. Randomness complexity matters because cryptographically secure random bits are relatively expensive to generate. Tables 1-4 show the cost of applying cryptographically secure random bits compared to using cheaper pseudorandomness, showing that noise generation is a bottleneck in the former.
Q5 (help in practical scenarios). In principle, yes. Our method replaces the noise addition step in DP-SGD and uses the same privacy accountant so the efficiency results apply at any scale, making use of cryptographically secure generators (and hence computational DP) feasible. However, we have not run at VaultGemma d≈109 scale, our largest experiment is on BERT-Base with d≈108.
Q6 (source of overhead). On GPU the sampling arithmetic is cheap, and in large dimension most time usage is for generating secure bytes on the CPU and transferring to the GPU (3.1 ms with non-secure vs 74 ms with secure randomness at d=107, see Tables 2 and 4). At d=105 the two parts are comparable (1.4 vs 2.3 ms). Both could be reduced with improved hardware support for secure random generation on the GPU. We use the secrets module only for sampling the Zi, the dither comes from cheap, public randomness.