Secure Multi-party Differential Privacy

Peter Kairouz, Sewoong Oh, Pramod ViswanathNeurIPS 2015 · OpenReview

Introduction

In a world where multiple parties want to compute a function on their private data, it is natural to assume that complex, back-and-forth "interactive" protocols are necessary to achieve the best results. However, for binary data, the opposite is true. This paper demonstrates that a simple, non-interactive "randomized response" (essentially flipping a biased coin) is the mathematically optimal way to balance privacy and accuracy, regardless of the function being computed.

Multi-party computation (MPC) allows a group of individuals to compute a result based on their collective data without any single person seeing everyone else's raw inputs. Traditionally, researchers used Secure Function Evaluation (SFE) to ensure the computation process was private. However, SFE has a major limitation: even if the process is secure, the final output of the function might reveal too much about the individuals. For instance, knowing the average salary of a three-person office and your own salary allows you to deduce significant information about the other two.

To mitigate this, Differential Privacy (DP) is employed, adding noise to the data to ensure no single individual's input can be pinpointed. The core challenge addressed in this research is the "privacy-utility tradeoff": how can information be exchanged to maximize accuracy while strictly adhering to differential privacy constraints? Specifically, does interactive communication yield a more accurate answer than simply broadcasting noisy versions of the data once?

Methodology

The authors focus on a scenario where $k$ parties each possess a single private bit (0 or 1). They aim to compute various functions, such as a majority vote or an XOR, while maintaining $\epsilon$-differential privacy. Because this is a theoretical paper focused on fundamental limits, the results are derived through rigorous mathematical proofs rather than experimental benchmarking on empirical datasets.

To find the optimal protocol, the authors employed a sophisticated geometric and optimization-based approach:

  • Tensor Representation: They modeled the probability of any given communication "transcript" as a $k$-dimensional tensor.
  • Protocol Compatibility: They proved that any valid interactive protocol must result in a "rank-1" tensor. This significant constraint limits how "clever" an interactive protocol can actually be.
  • Infinite-Dimensional Linear Programming: To find the best possible protocol among all candidates, the problem was transformed into a massive, infinite-dimensional linear program.
  • Geometric Analysis: By analyzing the "corner points" (extremal points) of the set of all possible private protocols, they discovered that these points correspond exactly to non-interactive randomized response.

Key Insights and Results

The most surprising revelation of this work is that for parties holding single bits, interactive protocols provide zero accuracy gain over non-interactive ones. In the realm of privacy, this represents a massive simplification.

The "randomized response" protocol is universally optimal. It is not just effective for one specific task; it is simultaneously optimal for any function, any cost metric (how error is measured), and for both average-case and worst-case accuracy. Because the optimal protocol is non-interactive and universal, "data release" and "decision making" are naturally separated. Each party can simply privatize their bit once, and then anyone can use those noisy bits to compute any function as accurately as possible.

Formally, Theorem 3.1 establishes that for any desired privacy level $\epsilon$, the randomized response protocol achieves the maximum possible accuracy among all possible interactive protocols. The technical "secret sauce" behind this theorem is the realization that the independent nature of the parties' bits, combined with the structure of interactive communication, forces the mathematics into a specific geometric shape (rank-1 tensors) that prevents interaction from offering any advantage.

The authors provide a concrete example using the XOR function. They show that as the number of parties $k$ increases, the accuracy of computing the XOR privately drops exponentially. For the XOR case, the optimal way to compute the result is simply to take the XOR of all the noisy bits received—no complex post-processing is required.

Limitations and Future Work

While the findings provide a robust theoretical foundation for single-bit multi-party differential privacy, several open challenges remain:

  • Multiple Bits: The authors explicitly note that if each party has multiple bits of information, interaction might actually help. Proving the limits for the multi-bit case remains an open challenge.
  • Approximate Differential Privacy: The paper focuses on "pure" differential privacy ($\epsilon$-DP). Extending these proofs to "approximate" differential privacy ($(\epsilon, \delta)$-DP), which allows for a tiny probability of privacy failure, is significantly more complex because the linear programming approach used here does not easily translate.
  • Correlated Data: The proof relies on the assumption that the parties' bits are statistically independent. If the data is correlated (e.g., neighbors having similar opinions), the rank-1 tensor structure breaks down, and the optimality of non-interactive protocols may no longer hold.

Summary updated

Abstract

We study the problem of multi-party interactive function computation under differential privacy. In this setting, each party is interested in computing a function on its private bit and all the other parties' bits. The function to be computed can vary from one party to the other. Moreover, there could be a central observer who is interested in computing a separate function on all the parties' bits. Differential privacy ensures that there remains an uncertainty in any party's bit even when given the transcript of interactions and all other parties' bits. Performance at each party is measured via the accuracy of the function to be computed. We allow for an arbitrary cost metric to measure the distortion between the true and the computed function values. Our main result is the optimality of a simple non-interactive protocol: each party randomizes its bit (sufficiently) and shares the privatized version with the other parties. This optimality result is very general: it holds for all types of functions, heterogeneous privacy conditions on the parties, all types of cost metrics, and both average and worst-case (over the inputs) measures of accuracy.
BibTeX
@inproceedings{kairouz2015secure,
  author = {Peter Kairouz and Sewoong Oh and Pramod Viswanath},
  title = {{Secure Multi-party Differential Privacy}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=r1bpkuWOWr},
}
Figure