PaperlayerView exact revision on arXiv

Source-linked AI summary

Revisiting Continuous Noise Sampling for Multi-Party Differential Privacy

Yucheng Fu, Tianhao Wang

arXiv:2608.27766v1cs.CR

TL;DR

Finite-precision sample-and-scale protocols for continuous DP noise can leak dataset information because scaling restricts outputs to sparse grid values, while existing sampling is costly. The paper replaces this approach with secure discrete-grid sampling, achieving comparable utility and substantial efficiency improvements.

  • Problem

    Finite-precision arithmetic leaves the security of sample-and-scale continuous-noise protocols uncertain, while their transcendental-function circuits are costly for MPC.

  • Method

    The paper samples discrete Laplace or Gaussian noise directly on the fixed-point grid using biased-bit protocols, proves security, and optimizes implementation efficiency.

  • Results

    Scaling confines released queries to sparse publicly known sets, yielding almost 100% attack success for s ≥2; the proposed sampler matches ideal-mechanism utility and improves efficiency.

  • Takeaways & Limitations

    Secure discrete-grid sampling removes the scaling-induced sparsity while providing a practical alternative to insecure sample-and-scale protocols.

  • Takeaways & Limitations

    Direct repairs to the vulnerability either coarsen the output grid and lose utility or add ⌈log2 s⌉ guard bits and increase sampler cost.

Abstract

from arXiv · show

Combining secure multi-party computation (MPC) with differential privacy (DP) enables multiple parties to release aggregate statistics without a trusted curator, and the core primitive is the protocol to sample noise from a continuous distribution under finite-precision arithmetic. In this paper, we revisit the continuous noise sampling protocols and present several improvements in both security and efficiency. We start by identifying a vulnerability in widely used sample-and-scale constructions. We demonstrate that the scaling operation in arithmetic circuits confines the noise to a sparse, publicly known set of values, so that an adversary can observe the released noisy queries and decide which dataset produced them. As concrete demonstrations, we instantiate attacks on two systems employing such ``flawed'' sampling protocols: Orchard (OSDI'20) for DP secure aggregation and DP-BREM$^+$ (USENIX Sec'25) for DP federated learning. We report a near-$100\%$ attack success rate on both systems, under any noise scaler $s\geq 2$ used in practice. The leakage we reveal is intrinsic to the scaling operation, and direct repairs either substantially sacrifice utility or add significant precision bits to make the sampling more expensive. To address the security and efficiency issues together, we turn to discrete sampling at the granularity of individual biased bits. We make several optimizations to the sampler and prove its security. Our implementation achieves $4\times \sim 612\times$ speedup over existing secure discrete samplers and orders-of-magnitude speedup over the insecure sample-and-scale paradigm, with negligible utility loss compared to the ideal continuous mechanism.

1 Introduction

MPC can provide centralized-model utility for DP without trusted servers, but finite-precision continuous noise sampling creates security and efficiency challenges. This paper exposes a sample-and-scale vulnerability and introduces a secure, efficient discrete-grid sampler.

  • MPC can simulate centralized DP while revealing only noisy aggregate outputs, avoiding trusted servers and the utility degradation of local and shuffled models.
  • Finite-precision arithmetic makes continuous Laplace and Gaussian sampling difficult, while floating-point transcendental-function evaluation has caused DP failures.
  • 19 seconds for Laplace and 61 seconds for Gaussian: sample-and-scale noise generation is impractical at s = 10 with l = 16 fractional bits.
  • Scaling a fixed-point standard sample confines noise to a sparse, publicly known subset of grid points, enabling attacks on sample-and-scale protocols.
  • Almost 100% attack success occurs once s ≥2, even when neighboring queries differ in a single bit, completely breaking the DP guarantee.
  • Direct repairs either lose utility through query-grid coarsening or add ⌈log2 s⌉ guard bits and increase sampler cost.
  • The proposed sampler draws discrete Laplace or Gaussian noise directly on the fixed-point grid, proves security, and achieves large speedups with utility comparable to the ideal continuous mechanism.

2 Preliminaries

The paper defines fixed-point MPC representations, differential privacy primitives, and the distributed system in which users secret-share data to untrusted servers that release noisy queries.

  • Fixed-point values use n integer bits and l fractional bits, with integer encoding X = 2^l x and grid step 2^-l.
  • MPC lets parties jointly evaluate functions on private inputs while learning only the output and information inferable from it.
  • Secret-sharing protocols distribute each input into shares, jointly compute shared outputs, and reconstruct the plaintext result through Reveal.
  • Neighboring datasets differ by one record, and query sensitivity is the maximum output change over such neighboring pairs.
  • Differential privacy requires neighboring datasets to induce similar output probabilities for every possible output set.
  • The Laplace mechanism adds noise with scale parameter b = ∆f, while the Gaussian mechanism adds noise calibrated to sensitivity and privacy parameters.
  • Users secret-share records to N servers, which jointly compute queries, generate noise, add it, reconstruct the noisy query, and send it to an analyst.

3 Threat Model

The threat model gives an honest-but-curious analyst the released noisy output and knowledge of two neighboring datasets, but not the protocol’s randomness.

  • The adversary corrupts the analyst and observes the protocol’s DP-protected output.
  • The adversary knows neighboring datasets differing in one record and guesses which dataset produced the released noisy query.
  • The adversary knows the protocol implementation but not its randomness.
  • Knowing both neighboring datasets is part of the DP definition, because DP requires their output distributions to remain (ε,δ)-indistinguishable.

4 Vulnerability in Sample-and-scale

Existing sample-and-scale protocols can leak which neighboring dataset produced a noisy query because fixed-point scaling restricts noise to a sparse, publicly known output set. The paper formalizes an efficient membership test that exploits this structure and explains why the leakage persists for general scalers s ≥ 2.

  • Existing sample-and-scale workflow: Existing continuous samplers use secret-shared uniform randomness, a nonlinear transformation into standard Laplace or Gaussian noise, public scaling, and query perturbation.The workflow scales a standard sample r by s before adding it to the secret-shared query and revealing the result.
  • General scaler: For every s ≥ 2, scaled noise lies in a sparse set Λs whose neighboring values differ by ⌊s⌋ or ⌈s⌉, leaving out at least half of the integers.Examples include Λ3 = {0,3,6,9,...} and Λ2.5 = {0,2,5,7,10,12,...}.
  • General scaler: Adding sparse scaled noise to neighboring queries produces distinguishable reachable output sets, which can be disjoint and reveal the generating dataset.Figure 2 illustrates disjoint reachable sets for s = 3; an output of 11 rules out D1.
  • Fixed-point attack: The attack subtracts each candidate query from the released output, tests membership in Λs, and falls back to maximum likelihood when both candidates pass.The true candidate always passes; when the wrong candidate also passes, the method chooses the candidate whose derived noise has smaller magnitude.
  • Attack effectiveness: Near-100% success occurs because the wrong candidate rarely passes the sparse-set membership test, while the leakage stems from fixed-point scaling rather than cryptographic failure.The success rate depends on s and the fixed-point query gap d, and remains even when neighboring queries differ in a single bit.

5 Experiments: Attacking Secure Aggregation

Experiments apply the reachability attack to Orchard’s Laplace-based k-means query and DP-BREM+’s Gaussian federated-learning release, comparing it with maximum likelihood. The attack reaches near-certain success under practical scaling, including settings where baseline performance depends on query gaps or noise magnitude.

  • Orchard: Orchard’s five-round k-means query releases 45 noisy values, with scaler s = 1/ε and total budget 15ε.Each round releases nine values from three clusters: x-sum, y-sum, and count.
  • Orchard: Smaller ε strengthens the Orchard attack because the larger scaler skips more fixed-point noise values.Once s drops below 2, reachability becomes nearly complete again and the attack falls back to the maximum-likelihood baseline; TruncPr loses its edge for ε > 0.5.
  • Orchard: Repeated Orchard observations drive the attack toward certainty by the fifth round, while maximum likelihood remains far behind.At tight budgets, one round can already decide the candidate, but later rounds provide more values for ruling candidates out.
  • Floating-point variant: With PrivaDA’s floating-point sampler, the attack stays above 99% across ε = 0.1 to ε = 20 and reaches 100% versus a 54.3% baseline at ε = 0.1.Its gain closes beyond ε ≈3 because the baseline itself reaches 100%.
  • DP-BREM+: On DP-BREM+, the attack stays above 87% everywhere and reaches 100% for every s ≥ 2 across R ∈ {5,10,20,50}.The 26,010-dimensional release enables thousands of one-sided tests; increasing R moves s from 1.5 to 3 and 7.5 while the total privacy budget remains ε ≈1.
  • Robustness: Across different-label, same-distribution, and removed-record neighboring pairs, the attack remains at 100% while maximum likelihood declines as pairs become closer.The attack fails only if candidate output differences are exact multiples of the grid step in every one of 26,010 coordinates.

6 Securing Continuous Sampling Protocols

The paper replaces vulnerable sample-and-scale noise generation with direct discrete sampling on the fixed-point grid, while proving security and optimizing MPC execution. Direct fixes either coarsen the query grid, add guard bits, or retain unresolved assumptions about continuous sampling.

  • Pyrrhic fixes: The two direct fixes close the reachability gap from opposite sides but trade utility or efficiency, and neither is currently proven secure under approximate nonlinear sampling.Rounding the query adds O(s2^-l) error, whereas guard bits widen arithmetic values.
  • Discrete sampler: Directly sampling discrete noise on the fixed-point grid removes both the scaling gap and the need for transcendental functions.The resulting sampler produces noise directly in F_n,l rather than scaling a rounded standard sample.
  • Discrete sampler: A discrete Laplace sample is represented as η = 2^-lZ with integer scale t = 2^ls, matching Laplace noise read on the grid.Truncation limits Z to a finite range for finite-precision protocols.
  • Accuracy: The discrete mechanism incurs O(2^-l) grid-rounding error and O(e^-2^κ/(2^ls)) statistical distance from tail truncation.Both errors decrease geometrically as fractional precision l and truncation length κ increase.
  • Security: Algorithm 3 securely realizes the fixed-point Laplace functionality against a semi-honest adversary corrupting up to N − 1 parties.The construction uses secret-shared biased coins to build the truncated geometric component and then forms two-sided noise.
  • Efficiency: Parallel evaluation reduces the sampler to O(T) online communication rounds, which is important when WAN latency dominates runtime.B(κ + l) independent coin flips still require O(TB(κ + l)) communication.

7 Experiments: Secured Sampler

Experiments evaluate runtime, communication, rounds, distributional correctness, and federated-learning utility on fixed-point grids. The proposed sampler is substantially faster than baselines, matches the intended discrete distributions, and overlaps the centralized mechanism in the reported MNIST case study.

  • Efficiency: Up to 1,300× speedup for Laplace and 550× for Gaussian is achieved over insecure sample-and-scale as precision increases.Against secure baselines, the sampler is 2×–10× faster than garbled circuits and 217×–706× faster than binary secret sharing.
  • Efficiency: The sampler cuts online rounds by two to three orders of magnitude while keeping communication close to binary secret sharing.Garbled circuits use four to six times more communication, whereas the proposed method balances rounds and communication.
  • Efficiency: The sampler is 1.5×–53× faster than the secure lookup-table sampler on LAN and matches it on WAN.It sends less data at two and four parties, but more at sixteen parties.
  • Utility: In the MNIST federated-learning case study with N = 16 parties, the proposed sampler overlaps the centralized mechanism, while distributed noise generation loses utility as H decreases.The comparison varies the number of honest parties H and privacy budget ε.
  • Correctness: The Kolmogorov–Smirnov tests never reject the sampler against the ideal discrete distributions at the 0.05 level.The p-values remain near 0.5 across the tested precisions.
  • Correctness: At l = 16, the proposed sampler assigns probability to every grid point, unlike sample-and-scale, which reaches only multiples of s.The comparison is shown in the [0,60]·2^-l window with probabilities normalized to unit mass.

8 Related Work

Related work addresses finite-representation vulnerabilities, discrete DP mechanisms, and secure MPC sampling. Prior protocols include secret-sharing, biased-coin, discrete Gaussian, and secure lookup-table approaches.

  • Finite representations: Prior work identifies information leakage in floating-point Laplace and Gaussian implementations, including least-significant-bit and timing side channels.Discretized Laplace and Gaussian mechanisms were proposed to address floating-point vulnerabilities.
  • MPC sampling: Secure MPC sampling research progresses from secret-shared discrete noise to biased Bernoulli coins, discrete Gaussian extensions, and secure lookup tables.The paper builds on these bitwise and lookup-table approaches for fixed-point noise sampling.

9 Conclusion

The conclusion identifies sparse fixed-point outputs as the sample-and-scale vulnerability and replaces costly repairs with secure, parallel biased-coin sampling. The resulting sampler matches the ideal continuous mechanism’s utility while improving efficiency.

  • Conclusion: Scaling on the fixed-point grid confines released queries to a sparse, publicly known set.This is the central vulnerability identified in the sample-and-scale paradigm.
  • Conclusion: The paper samples noise directly on the grid with parallel biased coins, proves security, and reports improved efficiency with negligible utility loss.The resulting sampler matches the utility of the ideal continuous mechanism.

A Proof of Lemma 1

The proof characterizes when scaled, rounded samples cover the full b-bit grid and when they collapse onto a sparse sublattice. It then describes a vectorized guessing algorithm that tests coordinate reachability and falls back to maximum likelihood when both candidates remain.

  • Proof of Lemma 1: l′ ≥ b+⌈log2 s⌉ is necessary and sufficient for scaled samples to hit every point of the b-bit grid.The proof derives this from the step size s2^−(l′−b) being at most one grid unit.
  • Proof of Lemma 1: When l′ < b+⌈log2 s⌉, the rounded noise lies on a sublattice whose shifted coset depends on f(D), enabling the Section 4 leakage attack.The sublattice density is 2^(l′−b)/s < 1.
  • Vectorized Guessing Algorithm: Algorithm 4 applies the reachability test independently to every released-vector coordinate and retains a candidate only if all coordinates are reachable.The encoded output is compared against each candidate dataset coordinate-wise.
  • Vectorized Guessing Algorithm: If exactly one candidate remains reachable, Algorithm 4 returns it; if both survive, it selects the candidate minimizing the specified distance.The distance is ℓ1 for Laplace noise and ℓ2 for Gaussian noise.

C Security of the Discrete Sampler

The security proof constructs a simulator using only corrupted parties’ output shares and shows that every protocol step can be simulated without revealing additional secrets. Correctness follows because the reconstructed sample matches FLap’s coin-to-Laplace output.

  • Security Simulation: The simulator reproduces the corrupted parties’ view of Algorithm 3 from only their shares of FLap’s output.It simulates fresh Fcoin shares, local operations, public multiplications, scaling, and Beaver-triple openings.
  • Security Simulation: Fcoin calls reveal only fresh-bit shares, while local linear operations and public multiplications send no messages.The final 2^−l scaling is also local.
  • Security Simulation: The simulator’s output view is identically distributed to the real view because opened Beaver-triple values are uniform given corrupted shares.No protocol step reveals secrets beyond the shares already held by the corrupted set.
  • Security Simulation: The reconstructed sample equals FLap’s output by correctness of the coin-to-Laplace map.This establishes the claimed secure realization in the stated simulation argument.

D Comparison with the Secure Lookup Table

The paper compares its discrete sampler with a secure lookup-table construction and reports faster LAN performance with matched WAN performance. The comparison excludes lookup tables from precision analysis because their support grows rapidly on the fixed-point grid.

  • Comparison with the Secure Lookup Table: Franzese et al. use λ encrypted lookup tables covering the target distribution’s support, with one-hot-vector evaluation that parallelizes across parties.Their construction is generic over discrete distributions and targets the same semi-honest, all-but-one corruption setting.
  • Comparison with the Secure Lookup Table: Our sampler is strictly faster on a LAN and matches the lookup-table sampler on a WAN.The lookup construction is computation-bound, whereas this sampler is communication-round-bound.
  • Comparison with the Secure Lookup Table: 689 online rounds remain for the Gaussian sampler after the Section 6.3 optimizations, making WAN latency dominant.This explains why the two samplers have similar WAN performance.
  • Comparison with the Secure Lookup Table: The precision comparison fixes one distribution and omits the lookup table because its table must cover the fixed-point support.A support requiring 216 entries in the reported evaluation needs roughly 224 entries at l = 16 and 240 at l = 32.
  • Comparison with the Secure Lookup Table: The sampler draws discrete Gaussian noise by generating an integer-scale sample, converting it to η = 2^−lZ, and secret-sharing the result.Algorithm 5 is identified as the discrete Gaussian sampler in the Fcoin-hybrid.

E Discrete Gaussian Sampler

The discrete Gaussian sampler reuses the discrete Laplace proposal mechanism and adds rejection sampling with parallel proposals and oblivious selection. Its security follows from the same Fcoin-based simulation structure, and the paper states secure realization against up to N −1 corrupted parties.

  • Discrete Gaussian Sampler: The Gaussian sampler targets truncated discrete Gaussian noise read on the fixed-point grid.Its functionality is denoted FGauss.
  • Discrete Gaussian Sampler: The protocol reuses Algorithm 3 to draw a discrete Laplace proposal at integer scale t, then accepts it using the prescribed rejection probability.The acceptance test decomposes a secret integer into bits and evaluates e^−X/D as a product over those bits.
  • Discrete Gaussian Sampler: M proposals are generated in parallel and the first accepted proposal is selected obliviously to prevent trial-count leakage through running time.M is chosen so that all proposals fail with probability at most δ.
  • Discrete Gaussian Sampler: Theorem E.1 states that the sampler securely realizes FGauss against a semi-honest adversary corrupting up to N −1 parties.The proof uses the Fcoin-hybrid model.
  • Discrete Gaussian Sampler: Security follows because acceptance and arithmetic compose Fcoin calls with local Boolean gates, allowing the earlier simulation argument to apply.The simulator reproduces coin outputs, opened Beaver-triple values, and public gates while preserving the truncated functionality.
Loading 2608.27766v1…