Discrete Gaussian Mechanism

Unlike the standard Gaussian mechanism, the Discrete Gaussian Mechanism samples noise from a discrete Gaussian distribution defined over the integers. This ensures that queries on integer-valued data—such as counts, sums, or histogram bins—produce exact integer outputs without rounding errors.

• Eliminates floating-point arithmetic vulnerabilities
• Preserves the integrality of count queries and contingency tables
• Essential for cryptographic protocols that require exact arithmetic over finite fields

Continuous noise mechanisms implemented in IEEE 754 floating-point arithmetic are vulnerable to covert channel attacks and privacy leakage due to the non-uniform spacing of representable numbers. The Discrete Gaussian Mechanism avoids this entirely by operating on a finite, exact integer lattice.

• Prevents the Mironov attack that exploits floating-point rounding to break differential privacy guarantees
• Ensures reproducibility across different hardware architectures
• Removes the need for secure floating-point libraries in sensitive deployments

Efficient sampling from the discrete Gaussian distribution is achieved using rejection sampling techniques, such as the Karney algorithm or Knuth-Yao sampling. These methods generate exact samples without resorting to continuous approximations.

• Karney's algorithm: Uses a base sampler with a uniform random integer and a rejection step based on Bernoulli trials
• Achieves constant expected time independent of the distribution's center
• Suitable for hardware implementations and constant-time cryptographic code

The Discrete Gaussian Mechanism satisfies the relaxed approximate differential privacy guarantee, parameterized by ε and δ. It is also naturally analyzed under Rényi Differential Privacy (RDP), which provides tighter composition bounds for iterative algorithms.

• Privacy loss scales with the L2 sensitivity of the query
• Supports privacy amplification by subsampling when combined with Poisson sampling
• Directly applicable as a drop-in replacement for the continuous Gaussian in DP-SGD when gradients are quantized

Because the Discrete Gaussian Mechanism operates on integers, it integrates seamlessly with lattice-based cryptography and secure multi-party computation (MPC) protocols that require arithmetic over finite rings or fields.

• Used in homomorphic encryption schemes where ciphertexts encode integer plaintexts
• Enables distributed differential privacy where multiple parties jointly sample discrete noise
• Foundational to secure aggregation protocols that sum integer-valued model updates with privacy guarantees

The discrete Gaussian distribution retains the sub-Gaussian tail bound of its continuous counterpart, ensuring that the probability of adding large noise values decays exponentially. This provides strong concentration guarantees for the utility of the mechanism.

• Variance is identical to the continuous Gaussian with the same scale parameter σ²
• For a query with L2 sensitivity Δ₂, adding noise with scale σ ≥ Δ₂√(2 log(1.25/δ))/ε satisfies (ε, δ)-DP
• The discrete tail bound ensures that the probability of exceeding t·σ is at most exp(-t²/2)

Smartphone keyboards and voice assistants use on-device federated learning to improve next-word prediction and speech recognition. The Discrete Gaussian Mechanism is essential here because it generates integer noise that can be efficiently computed on mobile processors and transmitted as compact bit strings. Unlike floating-point noise, discrete noise avoids cross-platform rounding inconsistencies that could leak information when updates from millions of devices are aggregated. Apple and Google leverage discrete noise in their production federated learning systems to ensure that individual typing patterns remain indistinguishable within the aggregated model update.

National statistical agencies, including the U.S. Census Bureau, require integer outputs for population counts and tabulations. The Discrete Gaussian Mechanism enables the release of exact, privacy-protected counts without the floating-point vulnerabilities that plagued earlier mechanisms. In the 2020 Decennial Census, the Census Bureau adopted a discrete noise framework to inject calibrated randomness directly into integer counts, ensuring that published tables are both statistically accurate and provably private. This prevents reconstruction-abstraction attacks that could re-identify individuals from multiple cross-tabulated queries.

In Secure Multi-Party Computation (MPC) protocols, multiple organizations collaboratively compute analytics without revealing their raw inputs. The Discrete Gaussian Mechanism is the natural choice for adding noise within these protocols because MPC operates natively over integer rings and finite fields. Adding floating-point noise inside an MPC circuit would require expensive floating-point emulation. Discrete noise integrates seamlessly with arithmetic secret sharing, enabling efficient, privacy-preserving sums, averages, and histograms across competing banks or hospitals without exposing individual transaction or patient records.

Trusted Execution Environments (TEEs) like Intel SGX and ARM TrustZone execute code in isolated hardware enclaves. When an enclave performs differentially private queries, it must prove to a remote party that it correctly sampled noise. The Discrete Gaussian Mechanism enables efficient sampling verification because discrete distributions have exact, verifiable probability mass functions. A remote auditor can confirm that the enclave's output distribution matches the claimed discrete Gaussian without needing to trust the enclave's floating-point unit, which is a known side-channel attack vector.

Systems like Google's ZetaSQL and OpenDP integrate differential privacy directly into SQL queries. When an analyst runs SELECT COUNT(*) GROUP BY category, the engine must inject noise into each bin count. The Discrete Gaussian Mechanism is preferred because SQL integer types are exact, and adding floating-point noise would produce non-integer counts that break downstream integer-typed operations. Discrete noise preserves type integrity throughout the query pipeline, ensuring that privacy-protected views remain compatible with existing business intelligence tools and integer-based constraints.

When serving predictions from a model trained with DP-SGD, the final inference output may still leak membership information. Applying the Discrete Gaussian Mechanism to the model's output logits or predicted class labels provides a final layer of protection. For classification tasks, discrete noise can be added directly to the integer class scores before the argmax operation, ensuring that the released label is differentially private. This is particularly valuable in medical diagnosis APIs where the mere fact that a model returns a specific rare disease code could reveal a patient's presence in the training set.