Source-linked AI summary
Distributed Private Data Analysis: On Simultaneously Solving How and What
Amos Beimel, Kobbi Nissim, Eran Omri
TL;DR
The paper asks whether distributed private-data analyses should choose what to compute and how to compute it separately or simultaneously. It studies this question through SFE, differential privacy, and lower-bound techniques for binary sum and related tasks. For binary sum, simultaneous design gives no benefit below square-root-scale error with constant rounds, but can improve efficiency at that scale for symmetric functions; the work also identifies computational and local-versus-global separations.
Problem
SFE can compute a chosen function privately, but choosing a function that preserves individual privacy and choosing its protocol may be suboptimal when done separately.
Method
The paper compares separate and simultaneous choices of differentially private analyses and their distributed protocols, using information-theoretic lower bounds and distributed-to-local transformations.
Results
For binary sum, simultaneous design offers no gain for error o(sqrt(n)) with few rounds, but yields more efficient protocols around O(sqrt(n)) error for symmetric approximations.
Takeaways & Limitations
The benefit of simultaneous design depends on the required accuracy and function class, while computational hardness can improve efficiency in the studied privacy setting.
Takeaways & Limitations
The results include an efficiency caveat for techniques that hide sums while maintaining a constant number of rounds, and a limitation for non-symmetric functions.
Abstract
from arXiv · showhide
We examine the combination of two directions in the field of privacy concerning computations over distributed private inputs - secure function evaluation (SFE) and differential privacy. While in both the goal is to privately evaluate some function of the individual inputs, the privacy requirements are significantly different. The general feasibility results for SFE suggest a natural paradigm for implementing differentially private analyses distributively: First choose what to compute, i.e., a differentially private analysis; Then decide how to compute it, i.e., construct an SFE protocol for this analysis. We initiate an examination whether there are advantages to a paradigm where both decisions are made simultaneously. In particular, we investigate under which accuracy requirements it is beneficial to adapt this paradigm for computing a collection of functions including binary sum, gap threshold, and approximate median queries. Our results imply that when computing the binary sum of $n$ distributed inputs then: * When we require that the error is $o(\sqrt{n})$ and the number of rounds is constant, there is no benefit in the new paradigm. * When we allow an error of $O(\sqrt{n})$, the new paradigm yields more efficient protocols when we consider protocols that compute symmetric functions. Our results also yield new separations between the local and global models of computations for private data analysis.
1 Introduction
The paper studies whether differential privacy and secure function evaluation should be designed separately or simultaneously for distributed private-data analyses. For binary sum, simultaneous design offers no benefit below roughly square-root error under constant-round constraints, but can improve efficiency at that error scale for symmetric approximations.
- Motivation: SFE protects inputs beyond the computed outcome, but this alone is insufficient when the chosen function itself leaks individual information.Differential privacy addresses this by concealing any single individual’s contribution through carefully chosen random noise.
- Natural and simultaneous paradigms: The natural paradigm first chooses a differentially private approximation and then constructs an SFE protocol to compute it.This separates the analysis-design question from the protocol-design question.
- Natural and simultaneous paradigms: The simultaneous paradigm is motivated by a mismatch between privacy requirements: differential privacy tracks changes to few inputs, whereas SFE protects views under larger changes that preserve the outcome.The paper therefore investigates choosing the analysis and its distributed implementation together.
- Models and scope: The study considers honest-but-curious parties, coalition privacy, and local protocols in which parties communicate only with a curator.Results are presented information-theoretically, enabling lower bounds for SFE and comparisons with computational-hardness-based constructions.
- Binary-sum results: At additive error approximately sqrt(n), symmetric approximations can yield substantially more efficient differentially private protocols than any SFE protocol in that class.These protocols can protect coalitions of up to t=n−1 parties and need not rely on secure channels.
- Lower bounds and techniques: The paper derives local-model lower bounds and transformations from distributed protocols, including impossibility results for non-interactive and sufficiently low-round local protocols.The transformation for gap threshold reduces certain distributed protocols to local interactive protocols, while local lower bounds extend through round decomposition and composition.
- Binary-sum results: At error o(sqrt(n)) with a small number of rounds, simultaneous design provides no gain over differentially private approximations computed using SFE.The natural construction achieves O(1) additive error with O(nt) messages, while the paper proves matching efficiency limitations in the relevant regime.
- Computational versus information-theoretic privacy: Computational hardness assumptions can produce provably more efficient differentially private protocols than information-theoretic constructions in the studied setting.The observed phase transition at theta(sqrt(n)/epsilon) additive error does not hold computationally.
2 Preliminaries
The preliminaries define differential privacy for randomized analyses and distributed protocols, distinguish information-theoretic from computational privacy, and establish communication and lower-bound foundations.
- Differential Privacy: Differential privacy limits how much changing one individual input can alter outcome distributions.The definition quantifies over neighboring inputs and all outcome sets, with probability taken over the function's randomness.
- Differential Privacy: Global sensitivity calibrates Laplace noise to the largest output change between neighboring inputs.For binary SUM, sensitivity is 1, yielding an O(1)-error differentially private approximation.
- Distributed Protocols: The model uses honest-but-curious parties and, for lower-bound analysis, fixed communication patterns in synchronous point-to-point networks.Oblivious protocols make each channel either active in every run or never used.
- Distributed Protocols: Distributed differential privacy requires privacy against every coalition of at most t parties when a non-coalition input changes.Coalition views include their inputs, randomness, and received messages; computational privacy restricts distinguishers to probabilistic polynomial-time algorithms.
- Consequences: Computational privacy can substantially improve communication efficiency over information-theoretic privacy for distributed SUM.A computationally private protocol achieves O(log n/ε) additive error with O(n) messages, whereas information-theoretic privacy with o(√n) error and constant rounds requires Ω(n^2) messages.
3 Motivating Examples
The motivating examples show that choosing the analysis and its distributed protocol together can improve efficiency or simplicity, including for SUM and DISTα.
- Motivation: Choosing what and how together can produce more efficient or simpler differentially private protocols.The examples explicitly contrast this simultaneous paradigm with the natural sequential construction.
- Binary Sum: O(√n/ε) error is obtained for a simple SUM approximation using randomized noise and aggregation.The alternative local-model construction uses randomized response and translates to a two-round distributed protocol with 2n messages.
- Binary Sum: Symmetric SUM approximations use O(n) messages, while efficient SFE protocols for such functions do not exist.Symmetry means the output distribution depends only on SUM(x), not on the particular assignment of bits.
- Distance from a Long Subsequence of 0’s: ˜O(n^α/3/ε) additive error is achieved by a 3-round protocol for DISTα when 2t < n.The protocol partitions the input into disjoint intervals, adds normally distributed noise, secret-shares interval sums, and releases the minimum.
- Distance from a Long Subsequence of 0’s: The DISTα protocol reduces communication by approximating only subsequences beginning at interval boundaries, while p1 learns intermediate sums beyond the output.This explicitly demonstrates the efficiency and leakage trade-off of jointly choosing the analysis and protocol.
4 Lowerbounds on the Error of Binary Sum and Gap-Threshold in the Local Model
The section proves lower bounds for locally differentially private protocols computing gap-threshold and binary sum. The bounds show that constant-round local protocols cannot achieve errors substantially below the square-root scale.
- Assumptions: The analysis assumes 0 < ε ≤ 1, although the condition can be relaxed to any constant ε0 ≥ 1 with altered constants.The paper also analyzes protocols using 2ε-privacy to simplify notation.
- Proof strategy: For inputs sampled from A, the curator’s view is, with constant probability, similar under A and the all-zero input.The likelihood ratio r(c) remains bounded for a constant-probability set of views.
- Proof strategy: Each interactive local protocol is decomposed into ℓ non-interactive protocols, each preserving 2ε-differential privacy.This permits applying the non-interactive analysis round by round.
- Gap-threshold: Ω(√n/˜O(ℓ)) threshold is required for ℓ-round local protocols computing GAP-TR0,τ.The theorem establishes constant-probability error when τ is below this scale.
- Binary sum: δ√n error occurs with probability at least p for any ℓ-round ε-differentially private local protocol computing SUMn.Corollary 4.13 derives the binary-sum lower bound from the gap-threshold result.
5 Lowerbounds for Binary Sum and Gap-Threshold in the Distributed Model
This section transfers distributed-protocol lower bounds to the local model by exploiting parties with few communication neighbors. The resulting bounds show that sparse, constant-round protocols cannot obtain substantially sub-square-root error for binary sum.
- Lower bound: Ω(nt) messages are necessary for fixed-communication distributed protocols computing binary sum with error below √n/˜O(ℓ).The argument applies to ℓ-round (t, ε)-differentially private protocols.
- From distributed to local: A distributed protocol with at most n(t + 1)/4 messages yields an (ℓ + 1)-round local protocol for SUMn/2 with the same approximation parameters.The transformation preserves ε-differential privacy for the reduced local computation.
- Proof intuition: Lonely parties cannot affect the protocol’s output by too much because their neighbors must not learn too much about their inputs.This information-theoretic constraint produces large approximation error when many parties are lonely.
- From distributed to local: At least n/2 parties are lonely when the protocol sends at most n(t + 1)/4 messages.A lonely party communicates with at most t other parties, allowing the protocol to be transformed into a local protocol.
- Lower bound: Theorem 5.2 gives constant-probability error of at least δ√n under the stated message bound.The contradiction follows by applying the local-model lower bound to the transformed protocol.
6 SFE for Symmetric Approximations of Binary-Sum
The section studies SFE protocols for symmetric randomized approximations of binary sum. It shows that symmetry imposes a strong communication requirement, contrasting efficient differentially private protocols with inefficient SFE implementations.
- Communication lower bound: Any SFE protocol using fewer than nt/4 messages has error magnitude Ω(n) for a symmetric approximation of SUMn.The proof identifies at least n/2 lonely parties and shows that their inputs cannot substantially affect the computation.
- Symmetry: Symmetry means that permuting input coordinates leaves the randomized output distribution unchanged.This property lets the proof compare input vectors with equal sums but different coordinates.
- Communication lower bound: Ω(nt) messages are necessary for SFE protocols computing symmetric approximations of SUMn with small additive error.The lower bound holds even when differential privacy is not required.
- Scope: The symmetric-function lower bound does not extend to non-symmetric functions.A modified bit-flip protocol provides a non-symmetric counterexample with the same message count, though message lengths differ.
- Proof strategy: The proof uses equal-sum inputs and t-security to show that a coalition’s view has the same distribution in both executions.This yields equality of transcript probabilities for the lonely party’s two possible inputs.